Grouping items into groups
This is a chug-plug formula given in my book :
1.The number of ways in which mn different items can be divided equally int m groups, each containing n objects and the order of the groups is not important,is : $\frac {(mn)!}{(n!)^m} \frac {1}{m!} $
2.The number of ways in which mn different items can be divided equally int m groups, each containing n objects and the order of the groups is important,is : $\frac {(mn)!}{(n!)^m} \frac {1}{m!} * (m!) $
I am having some troubles in understanding the above two formulas and hence making mistakes while solving problems based on the same, so I am very inquisitive to know the proof.
Solution 1:
-
Imagine first that both the order of the groups and the order within the groups is important. You have $mn$ items; one way to divide them into $m$ groups of $n$ objects each is to simply list the items. Items 1 through $n$ will go into the first group; items $n+1$ through $2n$ will go into the second group; etc. There are $(mn)!$ ways of listing the items.
But in fact, you don't care about the order in which the groups appear on the list: if you take the same list you have, and now list items $n+1$ through $2n$ first, then, say, times $4n+1$ through $5n$, then items $1$ through $n$, etc., you will still get the same division of objects into the same groupings. So any shuffling of the blocks in your list will yield the same distribution of items into the groups. Each distribution into groups can then be described in $m!$ ways, one for each ordering of the $m$ groups. So you have counted each distribution $m!$ times, and you need to divide $(mn)!$ by $m!$.
You are still not done, though, because you also don't care about the order within each group. Again, say you have a listing: if you take the first $n$ items in the list, and you list them in a different order (say, from last to first) while keeping them in the first $n$ slots, then in the end you will have the same elements separated into the same groups: you don't care who goes into group $1$ first or last, just that they end up in that group. So you have also overcounted by as many ways as there are to list the members of each group in order. In each group, you have $n$ objects, which can be listed in $n!$ different ways. There are $m$ such groups, so each listing of the elements in the groups can be done in $(n!)^m$ ways; so you have also, separately, overcounted the lists by $(n!)^m$, forcing you to also divide by $(n!)^m$. Putting these two overcount factors together gives you the first formula.
Try to adapt the explanation above to see how to obtain this formula; note that a simpler way of writing it is just as $\frac{(mn)!}{(n!)^m}$, since the two $m!$ will cancel out.