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?

$\endgroup$
  • $\begingroup$ Can I suggest a different combinatorial argument? $\endgroup$ – Shitikanth Apr 29 '12 at 6:41
  • 2
    $\begingroup$ 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. $\endgroup$ – Shitikanth Apr 29 '12 at 6:48
  • $\begingroup$ This is very beautiful. Thanks a lot. $\endgroup$ – TheNeo Apr 29 '12 at 7:39
6
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ nice explanation Shitikanth........ $\endgroup$ – juantheron Dec 10 '13 at 2:48
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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