The task is to prove the following inequality:

$\begin{Bmatrix} mn\\ n \end{Bmatrix} \geqslant \frac{(mn)!}{(m!)^nn!}$ , where $m, n \in \mathbb{N_+}$

and to determine when the equality holds.

A simple substitution shows that the two sides are equal for $(m, n) = (1, 1) \wedge (m, n) = (1, n)$, but this observation doesn't bring me closer to the solution. The identities I know (which could help simplify any side of the inequality) don't seem of much use here (at least I don't see how to apply them), nor can I think of a good combinatorial approach.

Any idea how to tackle this problem?


Okay, let's take a look at what the inequality means combinatorically. The Stirling term asks us the following question

In how many ways can we partition $n\cdot m$ elements into $n$ blocks?

Now let's go ahead and try a particularly easy way of partitioning, namely by letting each block have exactly $m$ elements. So we shuffle all elements in $(nm)!$ ways and arrange these in blocks of $m$. However as ordering in the partition doesn't matter, we've created indistinguishable partitions.

For example $\{\{1,2,3,4\},\{5,6,7,8\}\}$ and $\{\{8,7,5,6\},\{4,3,1,2\}\}$ are identical partitions of $2\cdot 4$ elements so we only need to count those once! We can permute each $m$-block as we wish, and we've got $n$ of these. Finally, we can permute the $n$ blocks themselves as we wish. Now look what term you get.

The combinatorical version of your inequality thus reads

Partitions of $nm$ elements in $n$ blocks $\geq$ Partitions of $nm$ elements in $n$ blocks with $m$ elements each.

  • $\begingroup$ Indeed, combinatorial interpretation works like a charm here. So basically the RHS represents partitioning with an additional restriction. Moving on to the second part of the problem, I see it this way: LHS = RHS iff the only way to partition $nm$ elements is to arrange them into blocks of $m$. This is the case either if $mn=n$ or $n=1$ (thus $(m=1\wedge n\in\mathbb{N_+}) \vee (m\in\mathbb{N_+}\wedge n=1)$). It should suffice to say that otherwise (for $m, n > 1$) we can put $m-1$ elements to each of the $n$ blocks and add the remaining $n$ elements to any one of them. $\endgroup$ – Quintofron Aug 27 '12 at 12:41
  • $\begingroup$ Right, works indeed :) $\endgroup$ – Dario Aug 27 '12 at 18:57
  • $\begingroup$ Fine, thanks for help :) $\endgroup$ – Quintofron Aug 27 '12 at 19:05

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.