0
$\begingroup$

I'm having a very unpleasant time with trying to figure out how to think combinatorially about all kinds of identities, where the summation over some index involves the index itself as a coefficient as well. I'm posting two problems I'm stuck on, in hopes somebody can explain what the general approach to these should be. (I think I understand, more or less, stuff like this.)

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

For what it's worth, the first one looks tempting to "integrate", but I don't know what this means for sequences and series.

At any rate, I would like help with identifying the combinatorial meaning of the RHS, and of the LHS, in particular, the factors of $k$ and $k^2$.

$\endgroup$
2
$\begingroup$

To some extent it’s an art that one acquires with practice. What I can do is talk you through my own thoughts on encountering these two problems.

The first one looks as if we’re choosing something out of $[n]$. Specifically, the general term looks as if we’re choosing $k$ things and then designating two of them (because the $k$ is squared) as special. For instance, we might have a pool of $n$ candidates from which we want to choose a committee of $k$, make one member of the committee the chairperson, and make one member, possibly the same one, the secretary. We’re summing over all possible $k$, so we should get the number of ways to pick a committee of arbitrary size from our pool of $n$ candidates, choose a chairperson, and choose a secretary (who might be the same as the chairperson). Can we interpret the righthand side as counting the same thing more directly?

The first term is clearly the number of ways to pick the chairperson, pick a different person as secretary, and then fill out the committee with any subset of the remaining $n-2$ people: $n(n-1)2^{n-2}$ is the number of committees whose chairperson and secretary are different. The second term is the number of ways to pick one of the $n$ people to be both chairperson and secretary and then to pad out the committee with any subset of the remaining $n-1$ people: there are $n2^{n-1}$ possible committees on which the chairperson and the secretary are the same person. These two subsets of the committes are exhaustive and don’t overlap, so their sum, $n(n-1)2^{n-2}+n2^{n-1}$ is indeed the total number of possible committees, and the identity is established.

Let’s see if a similar approach works on the second identity. If it were $2n\binom{2n-1}{n-1}$, we could interpret it as the number of ways of picking a captain from a pool of $2n$ players and then filling out a team of $n$ by picking $n-1$ more players from the remaining $2n-1$. We have only half of this, so perhaps we’re picking the captain from a sub-pool of $n$ of the players. Let’s say that we have $n$ women and $n$ men, and we want to know in how many ways we can pick a team of $n$ that has a woman as captain. There are $n$ ways to choose the captain from the pool of $n$ women, and there are then $\binom{2n-1}{n-1}$ ways to choose the rest of the team, so $n\binom{2n-1}{n-1}$ does indeed give the correct count. Now the challenge is to interpret the lefthand side as counting the same thing.

For each $k$ we seem to be choosing $k$ members of one set of $n$ (one factor of $\binom{n}k$), $k$ members of another set of $n$ (another factor of $\binom{n}k$), and then singling one of (say) the first $k$ members (the factor of $k$). For instance, we might be choosing $k$ of the $n$ women and $k$ of the $n$ men and then picking one of the $k$ chosen women to be captain. The problem is that this gives us a team of $2k$ people, not a team of $n$. But we do get a team of $n$ if we interpret $\binom{n}k^2$ as the number of ways to choose $k$ women to be on the team and $k$ men who will not be on the team: the remaining $n-k$ men will be on the team, and we’ll have a team of $n$. (In more algebraic terms we’re just noticing that $\binom{n}k^2=\binom{n}k\binom{n}{n-k}$.) Thus, the $k$ term on the lefthand side is the number of ways to choose a team of $n$ that has $k$ women, one of whom is the captain. Summing over $k$ clearly gives the desired result.

$\endgroup$
  • $\begingroup$ You make things look so easy! Could you help me interpret the simpler identity $\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$? The RHS looks to me like the number of pairs $(x,S)$ with $x\notin S\subset [n]$. The LHS doesn't look like the same thing though, since $k\binom{n}{k}$ is the number of pairs $(x,S)$ with $x\in S\subset [n]$ and $|S|=k$. So the LHS overall is all the possible ways to choose $(x,S)$ with $x\in S\subset [n]$... $\endgroup$ – combinarcotics Sep 10 '16 at 20:56
  • $\begingroup$ Ah, actually, the RHS may be easily interpreted as the number of pairs $(x,S)$ with $x\in S$ - pick a number from $[n]$, and then add some subset of $[n-1]$. My original idea was to pick a number from $[n]$, take its complement as a singleton, and look at the subsets of the complement. How are these approaches equivalent? $\endgroup$ – combinarcotics Sep 10 '16 at 21:00
  • $\begingroup$ @combinarcotics: Think of picking a team of arbitrary size from a pool or $n$ players and designating one of them to be captain. The lefthand side breaks up the computation according to the size $k$ of the team. The $S$ in your interpretation of the lefthand side corresponds to $\{x\}\cup S$ in your interpretation of the righthand side. $\endgroup$ – Brian M. Scott Sep 10 '16 at 21:00
  • $\begingroup$ @BrianM.Scott okay. Am I right in saying the interpretations with $x\in S$ and $x\notin S$ are equivalent by symmetry? It's just the one with $x\in S$ is more convenient to think of? $\endgroup$ – combinarcotics Sep 10 '16 at 21:03
  • $\begingroup$ @combinarcotics: Yes, if you mean approaching the righthand side as counting either the pairs $\langle x,S\rangle$ with $x\in S\subseteq[n]$ or the pairs $\langle x,S\rangle$ with $x\in[n]$ and $S\subseteq[n]\setminus\{x\}$. $\endgroup$ – Brian M. Scott Sep 10 '16 at 21:06

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.