Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Can I suggest a different combinatorial argument? –  Shitikanth Apr 29 '12 at 6:41
2  
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
add comment

2 Answers

up vote 5 down vote accepted

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)

share|improve this answer
    
nice explanation Shitikanth........ –  juantheron Dec 10 '13 at 2:48
add comment

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.

share|improve this answer
    
Thank you so much. –  TheNeo Apr 29 '12 at 7:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.