9
$\begingroup$

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.

  • 0
    Maybe you could come up with a more descriptive title? The current one applies to a good two thirds of the questions on the site!2010-10-23
  • 0
    In which book did you find these formulas?2018-10-22

3 Answers 3

8
  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.

  2. 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.

  • 0
    Could please add a line what does it really mean by order of the group ? I am not sure whether I am understanding it properly or not :)2010-10-23
  • 0
    @Debanjan: I just tried to be more explicit in both paragraphs 2 and 3; see if that helps.2010-10-23
  • 0
    Now I got your point,actually now I understood that it's easy to derive the second one before and the first one.2010-10-23
  • 0
    @Debanjan: I would agree with that, yes.2010-10-23
  • 0
    I understood what you were saying but I am confused at the mn! part......why isn't it $(n!)^m$ instead of (mn)! when we are concerned with the items going into m groups instead of just randomly arranging them2018-04-24
  • 0
    @harambe: I do not understand your question. What are you trying to count with the expression $(n!)^m$? That would be the count of number of ways of selecting $m$ items out of $n! possibilities, with repetitions allowed. what are your $n!$ items, and why are you selecting $m$ of them, allowing repetitions? (And it's rather hard for me to try to figure out what you are talking about seven and a half years after the fact, especially if you aren't clear)2018-04-24
  • 0
    I had difficulty understanding this process at the start so yeah I posted a very bad question.After analysing it,I get most of it but I have doubt in one thing.In your first para,why are the groups already created by you when this question was about grouping them.and then the derivation is based on these groups?Will deciding the groups and going removing duplication is the basic idea here2018-04-24
  • 0
    @harambe: What I did was first count the number of ways of making the groups if the order of the groups and the order *within* the groups all matter; in that case, you can "group" them by just listing everyone, and then takign the top $n$ people for the first group, the next $n$ people for the second group, etc. That's how the groups are "created" in that setting.2018-04-24
1

Let me derive another expression for the following:

The number of ways in which mn different items can be divided equally into m groups, each containing n objects and the order of the groups is not important.

Since the order of items within the group does not matter, there are $C^m_n$ $\cdot$ $C^{m-n}_n$ $\cdot$ ... $\cdot$ $C_n^n$ ways of ordering the n objects into m groups. This formulation excludes any kind of ordering within the groups. However, this formulation takes into account the ordering between the groups. Hence, it should be divided by m! to account for this. Hence, the number of ways in which mn different items can be divided equally into m groups, each containing n objects and the order of the groups is not important can be expressed as:

$\frac{C^m_n \cdot C^{m-n}_n \cdot ... \cdot C_n^n}{m!}$

Assume that 8 objects have to be divided equally into 4 groups with 2 items each. Then, it could be calculated as

$\frac{C^8_2 \cdot C^{8-2}_2 \cdot C^{8-4}_2 \cdot C^{8-6}_2}{4!}$

0

Order of the group means that the each of the m groups is ordered as group-1, group-2,.., group-m. Let us understand that better with an example. Let Arrangement-A be such that Group-1={a1,b1,...,n1}, Group-2={a2,b2,...,n2}... Let Arrangement-B be such that Group-1={a2,b2,...,n2}, Group-2={a1,b1,...,n1} while all other elements/objects in the remaining groups remains same as in Arrangement-A. Now if the order of the groups is not important Arrangement-A is the same as Arrangement-B. If the order of the groups is important then Arrangement-A is not the same as Arrangement-B. P.S: I have not provided the proof to the formula as what has been written by Arturo should suffix with this explanation.

  • 1
    Consider including some carriage returns to improve readability and using LaTeX to format any mathematical expressions.2012-12-06