Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following equation:

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

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!

share|improve this question

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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