Come si calcola il numero totale di tutti i possibili sottoinsiemi unici da un insieme con repliche?

Question

Dato un insieme S ** contenente elementi duplicati, come si può determinare il numero totale tutte le possibili sottoinsiemi di S, dove ogni sottoinsieme è unico.

Per esempio, diciamo S = {A, B, B} e sia K l'insieme di tutti i sottoinsiemi, allora K = {{}, {A}, {B}, {A, B}, {B, B}, {A, B, B}} e quindi | K | = 6.

Un altro esempio sarebbe se S = {A, A, B, B}, allora K = {{}, {A}, {B}, {A, B}, {A, A}, {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} e loro | K | = 9

E 'facile vedere che se S è un vero e proprio set, avendo solo gli elementi unici, allora | K | = 2 ^ | S |.

Che cosa è una formula per calcolare questo valore | K | dato un "set" S (con i duplicati), senza generare tutti i sottoinsiemi?

** Non tecnicamente un set.

Answer 1

Prendere il prodotto di tutte le frequenze (+ 1).

Per esempio, in {A, B, B}, la risposta è (1 + 1) [il numero di As] * (2 + 1) [il numero di Bs] = 6.

Nel secondo esempio, contare (A) = 2 e contate (B) = 2. Pertanto la risposta è (2 + 1) * (2 + 1) = 9.

Il motivo per cui funziona è che si può definire qualsiasi sottoinsieme come un vettore di conta - per {A, B, B}, i sottoinsiemi può essere descritto come {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1,0}, {1,1}, {1,2}.

Per ciascun numero conteggi [] esistono (frequenze di quell'oggetto + 1) valori possibili. (0..frequencies)

Pertanto, il numero totale di possiblities è il prodotto di tutte le frequenze (+ 1).

Il "tutto unico" caso può anche essere spiegato in questo modo - c'è un'occorrenza di ogni oggetto, quindi la risposta è (1 + 1) ^ | S | = 2 ^ | S |.

Answer 2

Io sostengo che questo problema è semplice da risolvere, se visti in modo corretto. Lei non si cura di ordine degli elementi, anche se non figurano solo in un sottogruppo di no.

Contare il numero di volte in cui ogni elemento appare nel set. Per il set un elemento {A}, quanti sottoinsiemi ci sono? Chiaramente ci sono solo due set. Supponiamo ora abbiamo aggiunto un altro elemento, B, che è distinto da A, per formare l'insieme {A, B}. Siamo in grado di formare l'elenco di tutti i set molto facilmente. Prendete tutti i set che abbiamo formato utilizzando solo una, e aggiungere in zero o una copia di B. In effetti, raddoppiamo il numero di set. Chiaramente possiamo usare induzione per dimostrare che per n elementi distinti, il numero totale di set è solo 2 ^ N.

Si supponga che alcuni elementi appaiono più volte? Si consideri il set con tre copie di A. Così {A, A, A}. Quanti sottoinsiemi si può formare? Di nuovo, questo è semplice. Possiamo avere 0, 1, 2, o 3 copie di A, quindi il numero totale di sottoinsiemi è di 4 poiché l'ordine non importa.

In generale, per N copie dell'elemento A, finiremo con N + 1 possibili sottoinsiemi. Ora, espandere questo con l'aggiunta di qualche numero, M, di copie di B. Quindi abbiamo N copie di A e M copie di B. Quanti sottoinsiemi totale ci sono? Sì, questo sembra chiaro anche. Per ogni possibile sottoinsieme con solo un in esso (c'erano N + 1 di loro) possiamo aggiungere tra 0 e M copie di B.

Quindi, il numero totale di sottoinsiemi quando abbiamo N copie di A e M copie di B è semplice. Deve essere (N + 1) * (M + 1). Ancora una volta, si può usare un argomento induttivo per mostrare che il numero totale di sottoinsiemi è il prodotto di tali termini. Semplicemente contare il numero totale di repliche per ogni elemento distinto, aggiungere 1, e prendere il prodotto.

vedere cosa succede con l'insieme {A, B, B}. Otteniamo 2 * 3 = 6.

Per l'insieme {A, A, B, B}, otteniamo 3 * 3 = 9.