3
$\begingroup$

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?

1 Answers 1

3

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.

  • 0
    Fine, thanks for help :)2012-08-27