# An inequality involving Stirling numbers of the second kind

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.

Partitions of $nm$ elements in $n$ blocks $\geq$ Partitions of $nm$ elements in $n$ blocks with $m$ elements each.
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. – Quintofron Aug 27 '12 at 12:41