5
$\begingroup$

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?

  • 0
    This is very beautiful. Thanks a lot.2012-04-29

2 Answers 2

6

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} $

(Note: I had already pointed this out in the comments, but thought it would be helpful to write it out as an answer)

  • 0
    nice explanation Shitikanth........2013-12-10
4

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.