¿Cómo se calcula el número total de todos los subconjuntos únicos posibles de un conjunto con repeticiones?

Question

Dado un conjunto ** S que contiene elementos duplicados, ¿cómo se puede determinar el número total de todos los subconjuntos posibles de S, donde cada subconjunto es único?

Por ejemplo, supongamos que S = {A, B, B} y que K sea el conjunto de todos los subconjuntos, luego K = {{}, {A}, {B}, {A, B}, {B , B}, {A, B, B}} y por lo tanto | K | = 6.

Otro ejemplo sería si S = {A, A, B, B}, luego K = {{}, {A}, {B}, {A, B}, {A, A} , {B, B}, {A, B, B}, {A, A, B}, {A, A, B, B}} y por eso | K | = 9

Es fácil ver que si S es un conjunto real, que tiene solo elementos únicos, entonces | K | = 2^| S |.

¿Cuál es la fórmula para calcular este valor | K | dado un "set" S (con duplicados), sin generar todos los subconjuntos?

** No es técnicamente un conjunto.

Answer 1

Tome el producto de todas las (frecuencias + 1).

Por ejemplo, en {A, B, B}, la respuesta es (1 + 1) [el número de Como] * (2 + 1) [el número de BS] = 6.

En el segundo ejemplo, recuento (A) = 2 y recuento (B) = 2. Por lo tanto, la respuesta es (2 + 1) * (2 + 1) = 9.

La razón de esto funciona es que puede definir cualquier subconjunto como un vector de recuentos - para {A, B, B}, los subconjuntos pueden describirse como {A = 0, B = 0}, {A = 0, B = 1}, {0,2}, {1 , 0}, {1,1}, {1,2}.

Para cada número en conteos [] hay (frecuencias de ese objeto + 1) valores posibles. (0..frequencies)

Por lo tanto, el número total de posibilidades es el producto de todas (frecuencias + 1).

El caso "todo único" también se puede explicar de esta manera: hay una ocurrencia de cada objeto, por lo que la respuesta es (1 + 1)^| S | = 2^| S |.

Answer 2

Voy a argumentar que este problema es simple de resolver, cuando se ve de la manera correcta. No le importa el orden de los elementos, solo si aparecen en un subconjunto de no.

Cuente el número de veces que aparece cada elemento en el conjunto. Para el conjunto de un elemento {A}, ¿cuántos subconjuntos hay? Claramente solo hay dos conjuntos. Ahora supongamos que agregamos otro elemento, B, que es distinto de A, para formar el conjunto {A, B}. Podemos formar la lista de todos los conjuntos muy fácilmente. Tome todos los conjuntos que formamos utilizando solo A, y agregue cero o una copia de B. En efecto, duplicamos el número de conjuntos. Claramente podemos usar inducción para mostrar que para N elementos distintos, el número total de conjuntos es solo 2^N.

Supongamos que algunos elementos aparecen varias veces? Considere el conjunto con tres copias de A. Así {A, A, A}. ¿Cuántos subconjuntos puedes formar? Nuevamente, esto es simple. Podemos tener 0, 1, 2 o 3 copias de A, por lo que la cantidad total de subconjuntos es 4 ya que el orden no importa.

En general, para N copias del elemento A, terminaremos con N + 1 subconjuntos posibles. Ahora, expanda esto agregando un número, M, de copias de B. Entonces, tenemos N copias de las copias A y M de B. ¿Cuántos subconjuntos totales hay? Sí, esto parece claro también. Para cada subconjunto posible con solo A en él (había N + 1 de ellos) podemos agregar entre 0 y M copias de B.

Así que el número total de subconjuntos cuando tenemos N copias de copias A y M de B es simple. Debe ser (N + 1) * (M + 1). Nuevamente, podemos usar un argumento inductivo para mostrar que el número total de subconjuntos es el producto de dichos términos. Simplemente cuente el número total de repeticiones para cada elemento distinto, agregue 1 y tome el producto.

Vea lo que ocurre con el conjunto {A, B, B}. Obtenemos 2 * 3 = 6.

Para el conjunto {A, A, B, B}, obtenemos 3 * 3 = 9.