Demostrar que $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$
No encuentro interpretaciones de conteo para ninguna de las partes. Una pista de "si $S$ es un subconjunto de $\{1, . . . , n\}$ y $S^\prime$ es su complemento, entonces $|S| + |S^\prime| = n$ " también se dio, pero todavía no sé cómo empezar.
Podemos interpretarlo combinatoriamente como el número de maneras de formar un comité (de cualquier tamaño) con un presidente de un grupo de $n$ personas.
Desde $n$ la gente elige primero un comité de tamaño $i$ y elija uno de los siguientes $i$ miembros del comité para ser el presidente. Hay ${n \choose i}$ opciones para los miembros de la comisión, después de lo cual hay $i$ opciones para el presidente. Si sumamos todas $i$ de $1$ a $n$ que abarca comités de todos los tamaños posibles (no nulos). Así, tenemos $\sum_{i=1}^n {n \choose i}i$ .
Por otro lado, podríamos elegir primero a una persona del $n$ personas para ser el presidente. A continuación, para cada uno de los restantes no elegidos $n-1$ personas, pueden estar dentro o fuera del comité. Eso es $2^{n-1}$ posibilidades. Así, tenemos $n2^{n-1}$ .
Una pista: considere el conjunto de todos los subconjuntos de $\{1,2,\dots,n\}$ (de los cuales hay $2^n$ ) y tratar de encontrar la suma total de los tamaños de los subconjuntos de dos maneras diferentes. Por ejemplo, los posibles subconjuntos de $\{1,2\}$ son $\{\},\{1\},\{2\},\{1,2\}$ . A continuación, sumando los tamaños de cada subconjunto se obtiene $0+1+1+2 = 4$ .
Más explícitamente, si sumamos los tamaños de todos los posibles subconjuntos de $[n]=\{1,2,\dots,n\}$ podemos:
$1)$ Tenga en cuenta que hay $\binom{n}{i}$ subconjuntos de tamaño $i$ lo que da que la suma total de tamaños es
$$\sum_{i=1}^{n}\binom{n}{i}i$$
$2)$ Obsérvese que cada elemento está en $2^{n-1}$ subconjuntos, y así contribuye $2^{n-1}$ a la suma total. Así, la suma es igual a
$$n2^{n-1}$$
El valor de la suma no cambia independientemente de cómo lo hagamos, por lo que las expresiones deben ser las mismas.
Esto no es realmente una respuesta a la pregunta (ya se han dado muy buenas), sino al desafío más desalentador de encontrar una manera de utilizar realmente la pista dada en la pregunta (de una manera interesante).
El lado izquierdo $L=\sum_{i=0}^n\binom nii$ da la suma de los tamaños de todos los subconjuntos de un $n$ -agrupando el conjunto de elementos $\binom ni$ subconjuntos de tamaño $~i$ . Obsérvese que he introducido el conjunto vacío, lo que no supone ninguna diferencia para esta suma, pero hace que el número de subconjuntos sumados sea igual a $2^n$ . Como al tomar el complemento de todos los subconjuntos se obtiene cada subconjunto exactamente una vez (la operación es una involución), $L$ también da la suma de los tamaños de los complementos de todos los subconjuntos de un $n$ -de un conjunto de elementos. Pero si un conjunto tiene tamaño $i$ entonces su complemento tiene un tamaño $n-i$ (¡aquí es donde se utiliza la pista!) por lo que esto significa que $L=\sum_{i=0}^n\binom ni(n-i)$ . Si se suman los dos sumandos se obtiene $$ 2L=\sum_{i=0}^n\binom ni(n+(n-i))=n\sum_{i=0}^n\binom ni=n2^n. $$ Dividiendo ambos lados por $~2$ da la ecuación deseada $\sum_{i=0}^n\binom nii=L=n2^{n-1}$ .
Considere una ordenada $n+1-tuple$ de números, asignados a cada subconjunto del conjunto $S=\{1,2,3,...n,n+1\}$ , cuyo $i$ Esta coordenada es $1$ o $0$ en consecuencia como el $i$ El objeto se elige o no se elige, respectivamente. Es evidente que el lado izquierdo de la ecuación da el número total de $1$ en todos los posibles $n+1-tuple$ s. De nuevo para cada $k$ pertenecientes a S un total de $2^n$ $1$ s se aportan en esos $n+1-tuple$ s para $k$ .por lo tanto, el número total de $1$ s contribuido para todos $n+1$ números es $(n+1)2^n$ .por lo tanto $\mathrm{LHS=RHS}$ Probado.
Otra posible interpretación es a través del número esperado de cabezas en $n$ lanza de una moneda justa que es $n/2$ .
Es decir, tendremos $$ {n \over 2} = \sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n} \right)} {i\left( \matrix{ n \cr i \cr} \right)\left( {{1 \over 2}} \right)^{\,i} \left( {{1 \over 2}} \right)^{\,n - i} } = {1 \over {2^{\,n} }}\sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n} \right)} {i\left( \matrix{ n \cr i \cr} \right)} $$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
