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

Can you please give a combinatorial argument for the argument below?

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

From RHS, I drew the following argument: There are $n+1$ people. In how many ways, can we pick $n-1$ people and divide them into $2$ distinct committees say $C_1$ and $C_2$. I cannot get the same argument from LHS. Can you help me?

• Can I suggest a different combinatorial argument? – Shitikanth Apr 29 '12 at 6:41
• Both RHS and LHS are equal to the number of ways of selecting a committee from $n$ people with either one chair or two distinct chairs. – Shitikanth Apr 29 '12 at 6:48
• This is very beautiful. Thanks a lot. – TheNeo Apr 29 '12 at 7:39

Here is another way of looking at this equation.

Consider the number of ways $P$ of selecting a committee from $n$ candidates with either one chair or two distinct chairs. This can be done in two ways

1) Select the chair(s) first and pick any subset of the remaining candidates. $$P = n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$$ 2) Select a $k$ member team and then choose the chair(s) amongst them. $$P = \sum_{k=0}^{n} {n \choose k} \left( k(k-1) + k\right) = \sum_{k=0}^nk^2{n \choose k}$$

• nice explanation Shitikanth........ – juantheron Dec 10 '13 at 2:48

Let $M=(m_{ij})$ be a $n \times n$ matrix of variables. Then this number counts the number of "rooted" submatrices whose row indices match the column indices. By "rooted" I mean there is a distinguished element in the submatrix.

Left hand side. Since the row and column indices must match, there are $n \choose k$ submatrices with dimensions $k \times k$, each of which could have exactly $k^2$ roots. Summing this over $k$ gives $\sum_{k=0}^n k^2 {n \choose k}$ as the number of rooted matrices with matching row and column indices.

Right hand side. Now, lets re-do this count, but first choose the root cell $(i,j)$:

• There are $n^2-n$ pairs $(i,j)$ for the root cell such that $i \neq j$. Once this is chosen, it belongs to $2^{n-2}$ submatrices with matching row and column indices.

• There are $n$ pairs $(i,j)$ for the root cell such that $i=j$. Once this is chosen, it belongs to $2^{n-1}$ submatrices with matching row and column indices.

Hence, in total there are $(n^2-n) \cdot 2^{n-2}+n \cdot 2^{n-1}=n(n+1)2^{n-2}$ rooted matrices with matching row and column indices.