The question is let $\{m_1, m_2, m_3, \dots \}$ be a sequence of numbers where $m_k\geq 0$ for every $k \geq 1$.

Let $$M_n = \sum_{k=1}^n m_k $$ when $n \geq 1$ is an integer.

Show that if $$\prod_{k=1}^{n-1}{(M_k+1)\choose(M_k)}= \frac{(m_1+m_2+\cdots+m_n)!}{(m_1!m_2!\cdots m_n!)}$$

When I try I get an expansion that is for example the first term and I choose a random letter in this case 2 for $m_1$ the number $2!+1\over 2!(2+1-2)!$.

Is this the correct way to expand this series?

Thanks in advance. Let me know if anything should be clarified.

  • $\begingroup$ Is it ${(M_k + 1) \choose (M_k)}$ as you wrote or ${(M_{k+1}) \choose (M_k)}$? And what should be read after "Show that if''? Right now, your sentence does not make much sense. $\endgroup$ – laurent Jul 10 '15 at 9:13

A straight proof

So, let us fix some integer $k$.

What is the difference between $M_{k+1}$ and $M_k$? Unsurprisingly, it is $m_{k+1}$.

Now what is the value of ${M_{k+1} \choose M_k}$? Thanks to our first remark, we may write it as ${M_k + m_{k+1} \choose M_k}$. Therefore we may write,

$${M_{k+1} \choose M_k} = \frac{(M_k + m_{k+1})!}{M_k!m_{k+1}!} = \frac{(M_k + 1)(M_k + 2) \cdots (M_{k+1} - 1)M_{k+1}}{m_{k+1}!}.$$

Put all these terms together and you'll be fine!

More specifically,

$$ (m_1 + m_2 + \cdots + m_n)! = 1 \cdot 2 \cdot \cdots \cdot m_1 \cdot (m_1+1) \cdot \cdots (m_1 + m_2) \cdots (m_1 + m_2 + m_3) \cdots (m_1 + m_2 + \cdots + m_n)$$

Since $M_k = \sum_{i=1}^k m_i$, this huge product can be seen as

$$ \prod_{k=0}^n \left[(M_k+1)(M_k+2) \cdots (M_{k+1}-1)M_{k+1}\right]$$

  • $\begingroup$ I really dont understand, how do you get the terms together? I suppose it is very simple. $\endgroup$ – addde Jul 10 '15 at 13:32

A proof with double counting argument

The term on the right is the number of ways of partitioning a set of size $M_n$ into $n$ sets of sizes $m_1,m_2, \ldots, m_n$.

You may see this process as picking $m_n$ elements among the set of size $M_n$ which is possible in ${ M_n \choose m_n} = {M_n \choose M_{n-1}}$ ways. And then you need to pick $m_{n-1}$ elements among the $M_{n-1}$ remaining elements. Multiplying all these terms, you obtain the left side of your equation.

Since we counted twice the same quantity, both terms should be equal.

Aigner and Zeigler wrote a nice chapter [1, Chapter 25] about double counting in their celebrated book "Proofs from the Book"

[1] Martin Aigner and Günter M. Ziegler, Proofs from the Book (4th edition), Springer, 2010.


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.