# Combinatorial reasoning for linear binomial identity

I have the following equation:

$$m^4 = Z{m\choose 4}+Y{m\choose 3}+X{m\choose 2}+W{m\choose 1}$$

I iteratively took $m=1$ to $m=4$ to solve for the coefficients. I got the following values:

$Z=24$, $Y=36$, $X=14$ and $W=1$.

I then checked the equation with $m=5$ and "verified" the identity.

However, what is the interpretation of these values? I am looking for a combinatorial argument of this equation. What do the values of W, X, Y, and Z mean here? I do not see any similarities/patterns between W, X, Y, and Z.

1. What is the combinatorially interpretation of these values
2. Is there a better way to look at this problem or enumerate?
3. What else can I try?

All help is greatly appreciated!

-

These are the numbers of ways in which you can form $4$-tuples of $m$ different items with $4$, $3$, $2$ and $1$ different entries, respectively. With $1$ entry, you only have $1$ choice, so $W=1$. With $2$ different entries, you can either have $1$ of one and $3$ of the other ($4$ possibilities), $2$ of both ($6$ possibilities) or $3$ of one and $1$ of the other (another $4$ possibilities), for a total of $X=14$ possibilities. With $3$ different entries, you necessarily have $2$ of one and $1$ of each of the other two; you have $3$ choices for which one to have $2$ of, and then $12$ ways to arrange them, so $Y=3\cdot12=36$; and with $4$ different entries you have $4!=24$ ways to arrange them. There are $m^4$ $4$-tuples in total, and $\binom mk$ ways to choose $k$ different items.

Also, note that the Stirling numbers of the second kind satisfy the identity

$$\sum_{k=0}^n\left\{n\atop k\right\}(x)_k=x^n\;,$$

where $(x)_k$ is the Pochhammer symbol,

$$(x)_k=x(x-1)(x-2)\cdots(x-k+1)=k!\binom xk\;,$$

so we have

$$\sum_{k=0}^nk!\left\{n\atop k\right\}\binom xk=x^n\;,$$

so your coefficients are given by $\displaystyle k!\left\{4\atop k\right\}$ for $k=1,\dotsc,4$.

These two viewpoints are related in that the Stirling numbers of the second kind count the number of partitions of $n$ items into $k$ sets, and for each such partition you can choose $k$ out of the $m$ items and assign them to the sets of the partition in $k!$ different ways.

-
Can you give me a few examples of what is being counted as a 4-tuple in each entry? I think I am missing the idea of what is being counted. – CodeKingPlusPlus Feb 10 '13 at 20:56
@CodeKing: With $1$ entry $a$, there is $1$ $4$-tuple, $(a,a,a,a)$. With two entries $a$ and $b$, there are $14$ $4$-tuples, $(a,a,a,b)$, $(a,a,b,a)$, $(a,b,a,a)$, $(b,a,a,a)$ (that's $4$), $(a,a,b,b)$, $(a,b,a,b)$, $(a,b,b,a)$, $(b,a,a,b)$, $(b,a,b,a)$, $(b,b,a,a)$ (that's $6$ more), $(a,b,b,b)$, $(b,a,b,b)$, $(b,b,a,b)$, $(b,b,b,a)$ (that's $4$ more). – joriki Feb 10 '13 at 21:03
Any ideas for finding a closed form for $\sum\limits_{k=1}^n k^4$ using the above? How would I derive such a formula with all of the summation notation? – CodeKingPlusPlus Feb 10 '13 at 21:45
@CodeKing: $$\sum_{x=1}^nx^4=\sum_{x=1}^n\sum_{k=1}^4k!\left\{4\atop k\right\}\binom xk=\sum_{k=1}^4k!\left\{4\atop k\right\}\sum_{x=1}^n\binom xk=\sum_{k=1}^4k!\left\{4\atop k\right\}\binom{n+1}{k+1}\;.$$ – joriki Feb 11 '13 at 0:04