Combinatorial proof: ${n \choose 1}+6{n \choose 2}+6{n \choose 3} = n^3 $

Question

Prove $${n \choose 1}+6{n \choose 2}+6{n \choose 3} = n^3$$ without algebra.

I've been trying to think of it in terms of the volume of a cube, and also as the set $\{(x,y,z)|x,y,z \in \mathbb{N}, 1 \leq x,y,z \leq n\}$ (is this correct syntax?), but that's as far as I've gotten.

Answer 1

The general case of this formula is \begin{align*} n^k &= \left\{{k \atop 1}\right\}n + \left\{{k \atop 2}\right\} n(n-1) + \dots + \left\{{k \atop k}\right\}n(n-1)(n-2)\dotsb(n-k+1) \\ &= 1! \left\{{k \atop 1}\right\} \binom{n}{1} + 2! \left\{{k \atop 2}\right\} \binom n2 + \dots + k! \left\{{k \atop k}\right\} \binom nk. \end{align*} (To allow for the $k=0$ case we should include a $0! \left\{{k \atop 0}\right\}n^0$ term as well, I guess.)

Here, $\left\{{a \atop b}\right\}$ denotes the Stirling numbers of the second kind, which count the number of partitions of an $a$-element set into indistinguishable $b$ subsets. In particular, $b! \left\{{a \atop b}\right\}$ is a very commonly-encountered expression in which we partition an $a$-element set into $b$ distinguishable subsets. Equivalently, $b! \left\{{a \atop b}\right\}$ counts the number of surjective functions from $\{1,2,\dots,a\}$ onto $\{1,2,\dots,b\}$.

A word-problem proof of this identity is: if a bar has $n$ brands of beer available, in how many ways can $k$ people order beer? On the one hand, the answer is just $n^k$, because each person can choose a brand independently. On the other hand, we can count the answer in the following way:

• For each value of $i$ between $1$ and $n$, we can consider the case where $i$ different brands actually get ordered.
• We can choose which $i$ brands get ordered in $\binom ni$ ways.
• Once we've fixed the $i$ brands, there are $i! \left\{{k \atop i}\right\}$ surjections from $\{1,2,\dots, k\}$ to $\{1,2,\dots,i\}$: the number of ways for $k$ people to choose from those $i$ brands while ensuring that each brand is picked at least once.
• Finally, we sum over each value of $i$.

---

For the special case of $k=3$, we can count the surjections manually. Here, a minister, a priest, and a rabbi walk into a bar. There are $n$ brands of beer available. In how many ways can all three order beer?

On the one hand, there are clearly $n^3$ ways for them to make independent decisions. On the other hand, we can do casework:

• There are $\binom n1$ ways for all three of them to order the same brand of beer.
• There are $6 \binom n2$ ways for all three of them to order two brands: we choose which two brands in $\binom n2$ ways, choose which brand gets ordered by two people in $2$ ways, and choose which pair of people order the same brand in $3$ ways.
• There are $6 \binom n3$ ways for all three of them to order three different brands: we choose which three brands in $\binom n3$ ways, and match people up to brands of beer in $3! = 6$ ways.

The two ways of counting are equivalent, so $$n^3 = \binom n1 + 6\binom n2 + 6\binom n3.$$

Answer 2

Take the set that you have written, and divide them into three groups based on how many distinct components you have. For example, $\binom{n}{1}$ counts the number of elements of the form $(x,x,x)$. The second term counts elements with two distinct components, and the third counts the elements with three distinct components.

Answer 3

Suppose you have a class with $n$ students, and you hold a spelling bee, a geography bee, and a history bee. How many different ways can there be winners of the three bees? On the one hands it's $n\times n\times n=n^3$, since there are $n$ possibilities for each bee. On the other hand, there are $n\choose1$ ways a single student could win all three bees, $n\choose2$ ways two students could be winners, with $2$ choices for which of those two students wins just one bee and $3$ choices for which bee that student wins, for a total of $6{n\choose2}$ possibilities, and, finally, $n\choose3$ ways the three bees could each be won by a different student, with $3\times2\times1=6$ ways to decide which student won which bee, for a total again of $6{n\choose3}$ possibilities.