There are different notions of "ordered" and "unordered" that can arise in relation to set partitions.
- An unordered set of unordered sets,
- An unordered set of ordered sets,
- An ordered set of unordered sets,
- An ordered set of ordered sets,
all of which are counted differently.
In how many ways 15 different books can be divided five heaps of equal number of books ?
An example of what is counted here is:
{{1,3,8},{2,14,15},{4,5,7},{6,12,13},{9,10,11}}
is an unordered set of unordered sets. This is what the answer to the first question suggests it's counting. [Although, the question itself does not resolve the question of order within the heaps.]
There are three copies, each of four different books. In how many ways they can be arranged on a self ?
An example of what is counted here is:
1 2 3 1 4 1 3 3 2 2 4 4
which we can interpret as a set partition counting problem -- place the i-th element in the s(i)-th set, where s(i) denotes the element in the i-th position. So the above example gives rise to:
({1,4,6},{2,9,10},{3,7,8},{5,11,12})
which is an ordered set of unordered sets.
To highlight the difference between these two situations, for the first question:
{{1,3,8},{2,14,15},{4,5,7},{6,12,13},{9,10,11}}
{{2,14,15},{1,3,8},{4,5,7},{6,12,13},{9,10,11}}
should be considered the same (this is the same as swapping the positions of the first two heaps), whereas in the second question:
({1,4,6},{2,9,10},{3,7,8},{5,11,12})
({2,9,10},{1,4,6},{3,7,8},{5,11,12})
should be considered different (this is the same as swapping all the books labelled 1 with all the books labelled 2).
Best Answer
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.