Combinatorial proof: ${n \choose 1}+6{n \choose 2}+6{n \choose 3} = n^3 $ 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.
 A: 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.$$
A: 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.
A: 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.
