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

Question

Dato un set ** S contenente elementi duplicati, come è possibile determinare il numero totale di tutti i possibili sottoinsiemi di S, dove ogni sottoinsieme è univoco.

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

Un altro esempio potrebbe essere se S = {A, A, B, B}, quindi K = {{}, {A}, {B}, {A, B}, {A, A} , {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} e quindi | K | = 9

È facile vedere che se S è un set reale, con solo elementi univoci, allora | K | = 2^| S |.

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

** Non tecnicamente un set.

Answer 1

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

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

In il secondo esempio, count (A) = 2 e count (B) = 2. Quindi la risposta è (2 + 1) * (2 + 1) = 9.

Il motivo per cui questo funziona è che è possibile definire qualsiasi sottoinsieme come vettore di conteggi - per {A, B, B}, i sottoinsiemi possono essere descritti come {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1 , 0}, {1,1}, {1,2}.

Per ogni numero in conteggi [] ci sono (frequenze di quell'oggetto + 1) valori possibili. (0..frequenze)

Pertanto, il numero totale di possibilità è il prodotto di tutti (frequenze + 1).

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

Answer 2

Discuterò che questo problema è semplice da risolvere, se visualizzato nel modo corretto. Non ti interessa l'ordine degli elementi, solo se compaiono in un sottoinsieme di no.

Contare il numero di volte in cui ciascun elemento viene visualizzato nel set. Per il set di un elemento {A}, quanti sottoinsi ci sono? Chiaramente ci sono solo due set. Supponiamo ora di aggiungere un altro elemento, B, distinto da A, per formare l'insieme {A, B}. Possiamo formare la lista di tutte le serie molto facilmente. Prendi tutti gli insiemi che abbiamo formato usando solo A, e aggiungi zero o una copia di B. In effetti, raddoppiamo il numero di serie. Chiaramente possiamo usare l'induzione per mostrare che per N elementi distinti, il numero totale di serie è solo 2^N.

Supponiamo che alcuni elementi appaiano più volte? Considera l'insieme con tre copie di A. Quindi {A, A, A}. Quanti sottoinsiemi puoi formare? Di nuovo, questo è semplice. Possiamo avere 0, 1, 2 o 3 copie di A, quindi il numero totale di sottoinsiemi è 4 poiché l'ordine non ha importanza.

In generale, per N copie dell'elemento A, ci ritroveremo con N + 1 possibili sottoinsiemi. Ora, espandi questo aggiungendo un numero, M, di copie di B. Quindi abbiamo N copie di A e M copie di B. Quanti sottoinsiemi totali ci sono? Sì, anche questo sembra chiaro. A tutti i possibili sottoinsiemi con solo A in esso (ce ne sono stati N + 1) possiamo aggiungere tra 0 e M copie di B.

Quindi il numero totale di sottoinsiemi quando abbiamo copie N di copie A e M di B è semplice. Deve essere (N + 1) * (M + 1). Di nuovo, possiamo usare un argomento induttivo per dimostrare che il numero totale di sottoinsiemi è il prodotto di tali termini. Basta contare il numero totale di repliche per ciascun elemento distinto, aggiungere 1 e prendere il prodotto.

Vedere cosa succede con il set {A, B, B}. Otteniamo 2 * 3 = 6.

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