Argumento de combinatoria para $\sum_{k=0}^n k^2 \binom{n}{k} = n(n+1)2^{n-2}$

Question

¿Puede por favor dar una discusión combinatoria para el argumento a continuación?

$$\sum_{k=0}^n k^2 \binom{n}{k} = n(n+1)2^{n-2}$$

Del lado derecho, saqué el siguiente argumento: hay $n+1$ de las personas. De cuántas maneras, podemos elegir %#% de #% las personas y dividirlas en $n-1$ distintos comités decir $2$ y $C_1$. No consigo el mismo argumento de LHS. ¿Me puedes ayudar?

Answer 1

Deje $M=(m_{ij})$ $n \times n$ matriz de variables. A continuación, este número cuenta el número de "raíz" submatrices cuyo fila índices coinciden con los índices de columna. Por "raíz" quiero decir que es un elemento distinguido en la submatriz.

Lado izquierdo. Dado que los índices de fila y columna deben coincidir, hay $n \choose k$ submatrices con dimensiones de $k \times k$, cada uno de los cuales podría tener exactamente $k^2$ raíces. Sumando esto a través de $k$ da $\sum_{k=0}^n k^2 {n \choose k}$ como el número de arraigada matrices con la correspondiente fila y columna de los índices.

Lado derecho. Ahora, vamos a volver a hacer este recuento, pero en primer lugar elija el celular raíz $(i,j)$:

• Hay $n^2-n$ pares de $(i,j)$ de la raíz de la celda, de tal forma que $i \neq j$. Una vez elegido, pertenece a $2^{n-2}$ submatrices con la correspondiente fila y columna de los índices.

• Hay $n$ pares de $(i,j)$ de la raíz de la celda, de tal forma que $i=j$. Una vez elegido, pertenece a $2^{n-1}$ submatrices con la correspondiente fila y columna de los índices.

Por lo tanto, en total hay $(n^2-n) \cdot 2^{n-2}+n \cdot 2^{n-1}=n(n+1)2^{n-2}$ arraigada matrices con la correspondiente fila y columna de los índices.

Answer 2

Aquí es otra forma de ver esta ecuación.

Considerar el número de maneras en $P$ de la selección de un comité de $n$ de los candidatos con una silla o dos sillas. Esto se puede hacer de dos maneras

1) Seleccione la silla(s) y elegir cualquier subconjunto de los restantes candidatos. $$ P = n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2} $$ 2) Seleccione un $k$ de los miembros del equipo y, a continuación, elija la silla(s) entre ellos. $$ P = \sum_{k=0}^{n} {n \choose k} \left( k(k-1) + k\right) = \sum_{k=0}^nk^2{n \choose k} $$

(Nota: yo ya había señalado en los comentarios, pero pensé que sería de ayuda para que los escriban como una respuesta)