looking for a combinatorial interpretation

81 Views Asked by At

given positive integers $n,m$ does the fraction

$$ \frac{(nm)!}{n!^mm!} $$

count something? Namely does it correspond to the number of possibilities to do something?

3

There are 3 best solutions below

0
On BEST ANSWER

This counts the number of partions of $nm$ items into $m$ groups of $n$ items.

$$\frac{(nm)!}{(n!)^m}=\binom{nm}{n,n,\dots,n}$$

is the number of ordered partitions of $nm$ elements into $m$ sets of $n$ elements. Dividing by $m!$ the counts unordered partitions of this sort.

1
On

Yes, it counts in how many ways that you can divide mn-elements set into m sets each with n elements. For example we have got mn kids and they want to buy candies. But in the shop could be only n childs together (childrens are in n-elements groups). In how many ways childrens can be in the queue to the shop?

2
On

Yes, there is a simple possibility to show this by counting the cosets of certain symmetric groups.

Consider the symmetric group of $n$ elements $S_n$. Since $S_n ≀ S_m$ can obviously interpreted as a subgroup of $S_{nm}$, you see that $\frac{(nm)!}{n!^m m!}$ is the number of cosets of $S_n ≀ S_m$ in $S_{nm}$.