Si A={x1,x2,x3,…,xn}A={x1,x2,x3,…,xn}A= \{ x_1 , x_2 , x_3 , \ldots , x_n \}. ¿Cuántos subconjuntos hay?

No estoy de acuerdo. Por ejemplo, el número de subconjuntos de tamaño 2 es

Es un hecho bien conocido que la respuesta es$2^n$. Prueba por inducción:

• $A_1 = \{x_1\}$tiene dos subconjuntos:$\emptyset,A_1$.
• Supóngase cierto hasta$n$. los subconjuntos de$A_{n+1} = \{x_1,\dots,x_{n+1}\}$son los subconjuntos de$A_n = \{x_1,\dots,x_n\}$más los subconjuntos de$A_n$Unión$\{x_{n+1}\}$.

¿Por qué crees que habrá$n-(k-1)$subconjuntos de tamaño$k$?

Digamos que tienes un conjunto de$25$elementos,$\{1,2,3,....., 25\}$y lo que quieres es ver cuántos subconjuntos de tamaño$2$hay.

Tu puedes tener$\{1,2\}, \{1,3\}......, \{2, 25\}$. Eso es$24 = n- 1$. Pero esos son todos con el elemento.$1$. ¿Qué pasa con los subconjuntos sin el elemento?$1$.

$\{2,3\}...... , \{2,25\}$es$23$y$\{3,4\}...\{3,25\}$es$23$. y así sucesivamente hasta llegar a$\{24,25\}$ser$1$.

Así que sumando los que tenemos$24 + 23 + 22 + ... + 1 = 300$.

Pero ¿qué pasa con los subconjuntos de tamaño$3$.$\{1,2,3\} ... \{1,2,25\}$es$23$y$\{1,3,4\}$a$\{1,3,25\}$es$22$y$\{1,2,3\}...\{1,24,25\}$es$23 + 22 + ... + 1 = 276$y$\{2,3,4\}...\{2,24,25\}$es$22 + .... + 1 = 253$. y así sucesivamente todos los subconjuntos de tamaño$3$= \sum_{m=1}^{23} \sum_{i=1}^mi = \sum_{m=1}^{23} \frac {m(m+1)}2$.

Y luego hacer subconjuntos de tamaño.$4$obtenemos... bueno, un dolor de cabeza.

Un poco de reflexión es que elegir$k$elementos de$25$(o$n$) es, literalmente, elegir$k$elementos de$25$(o$n$). Así que el número de subconjuntos de tamaño$k$es${n \choose k}$. Literalmente.

[Esto implicaría que${n \choose 3} = \sum_{i=1}^{n-2}\frac {i(i+1)}2$. ¿Lo hace?]

Entonces, de todos modos, el número de subconjuntos adecuados sería:$\sum_{i=1}^{n-1} {n\choose i}$.

Pero... ¿se puede simplificar eso? Deberías jugar con eso durante unas 14 horas más o menos.

$n =2\implies \sum{n\choose i} = 2$

$n = 3\implies \sum{n\choose i} = {3\choose 1 } + {3\choose 2} = 6$.

$n = 4 \implies \sum{n\choose i} = {4\choose 1} + {4\choose 2} + {4\choose 3} = 4 + 6 + 4 = 14$.

¿Notas algo?

Bueno, aquí hay una sugerencia. Trate de calcular el número de todos los subconjuntos, incluidos los dos subconjuntos impropiamente ,$\emptyset$y$A$.

Entonces la solución es$\sum_{i=0}^n{n\choose i}$.

Entonces el número de todos los subconjuntos es

$n = 2; \sum {n\choose i} = {2 \choose 0} + {2\choose 1} + {2\choose 2} = 1+2+1 = 4$.

$n =3; \sum {n\choose i} = {3\choose 0}+ {3 \choose 1} + {3\choose 2} + {3\choose 3} = 1 + 3 + 3 + 1 = 8$.

Y$n= 4; \sum {n\choose i} = {4\choose 0} + {4\choose 1} + {4\choose 2} + {4 \choose 3} + {4\choose 4} = 1 + 4 +6+ 4 + 1 = 16$.

Note cualquier cosa.

Parece que el número de todos los subconjuntos es$2^n$.

¿Por qué sería eso? Probablemente podríamos probar$\sum_{i=0}^n{n\choose i} = 2^n$por inducción.... Pero, ¿qué significa ?

bueno, considere esta sola oración:

para cualquiera de los$n$elementos de$A$, el elemento está o no está en un subconjunto específico de$A$.

Piénsalo. Si lo hubiéramos considerado desde el principio, probablemente todo hubiera sido más fácil.

Hay