Combinatoria prueba de suma de $\sum_{k = 1}^{n-1} {n \choose k}= 2^1 + 2^2 + 2^3 +\ldots+ 2^{n-1}$

Question

Estoy buscando una combinatoria de la prueba. Sé cómo demostrarlo matemáticamente. La expansión de $(1+x)^n$ y la sustitución de $x$ $1$ me va a dar el resultado, pero no soy capaz de explicarlo de forma combinatoria.

Nota: Esta no es una tarea cuestión. Yo sólo soy curioso.

Answer 1

Como de costumbre $[n]=\{1,\ldots,n\}$. $\sum_{k=1}^{n-1}\binom{n}k$ es claramente el número de no-vacío, adecuada subconjuntos de a $[n]$, ya que el $\binom{n}k$ es el número de subconjuntos de tamaño $k$. Ahora vamos a $A_k$ el número de subconjuntos de a $[n]$ con un máximo del elemento $k$; claramente $|A_k|=2^{k-1}$, ya que el resto de $A_k$ puede ser cualquier subconjunto de a $[k-1]$. Por lo tanto,

$$\left|\bigcup_{k=1}^nA_k\right|=\sum_{k=1}^n2^{k-1}=1+\sum_{k=1}^{n-1}2^k\;.\tag{1}$$

Por otro lado, $\bigcup_{k=1}^nA_k$ es claramente el conjunto de no vacía de subconjuntos de a $[n]$, lo $(1)$ cuenta a todos los no-vacío, adecuada subconjuntos de a $[n]$ más que el conjunto de $[n]$ sí. Restando $1$ para el conjunto de $[n]$ deja el resultado deseado: tanto en $\sum_{k=1}^{n-1}\binom{n}k$ $\sum_{k=1}^{n-1}2^k$ recuento de la no-vacío, adecuada subconjuntos de a $[n]$, y por lo tanto, deben ser iguales.

Answer 2

Considerar el conjunto de $n$ bits enteros.

De un lado, el grupo de ellos por el número de unidades. Los tamaños de los grupos son $\dbinom nm$.

$$0000\|0001\ 0010\ 0100\ 1000\|0011\ 0101\ 1001\ 1100\ 1010\ 1100\|1110\ 1101\ 1011\ 0111\|1111$$

Por otro lado, el grupo de ellos por el prefijo hecho de $n-m-1$ ceros seguidos por uno solo (excepto para el primer grupo). Los tamaños de los grupos son $1$$2^m$.

$$\color{blue}{0000}\|\color{verde}{0001}\| \color{verde}{001}0\ \color{verde}{001}1\| \color{verde}{01}00\ \color{verde}{01}01\ \color{verde}{01}10\ \color{verde}{01}11\| \color{verde}{1}000\ \color{verde}{1}001\ \color{verde}{1}010\ \color{verde}{1}011\ \color{verde}{1}100\ \color{verde}{1}101\ \color{verde}{1}110\ \color{verde}{1}111$$

Answer 3

Primero en el lado derecho observar que $2^1+\dots+2^{n-1}=2^n-2$.

Ahora, en el lado izquierdo se están expandiendo $(1+1)^n$ y quitando el primer y último términos, a saber,${n\choose 0}$${n\choose n}$. Ambos términos son iguales a$1$, lo que hace que el lado izquierdo $2^n-2$ que es igual para el lado derecho.

Answer 4

Una variación de Brian M. Scott respuesta.

Se proporciona un conjunto a de n elementos. Ahora estamos interesados en todos los posibles subconjuntos de la misma y en el número total de subconjuntos.

Observar primero: Un elemento arbitrario $ x \in A $ es en un subconjunto o no está en uno. (Ley del medio excluido) y da, por tanto, en total $2^n$ posibles subconjuntos.

Pero esto también tiene que ser el mismo como: $\sum\limits_{i=0}^n A_i$ $A_i $ que indica el número de conjuntos con exactamente $i$ elementos, que por supuesto es: $A_i = \binom{n}{i}$, lo que le da la deseada igualdad de $\sum\limits_{i=0}^n \binom{n}{i}= 2^n $ .