Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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! –  Mariano Suárez-Alvarez Oct 23 '10 at 21:36

3 Answers 3

up vote 5 down vote accepted
  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.

share|improve this answer
    
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 :) –  Quixotic Oct 23 '10 at 21:00
    
@Debanjan: I just tried to be more explicit in both paragraphs 2 and 3; see if that helps. –  Arturo Magidin Oct 23 '10 at 21:08
    
Now I got your point,actually now I understood that it's easy to derive the second one before and the first one. –  Quixotic Oct 23 '10 at 21:09
    
@Debanjan: I would agree with that, yes. –  Arturo Magidin Oct 23 '10 at 21:11

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.

share|improve this answer
1  
Consider including some carriage returns to improve readability and using LaTeX to format any mathematical expressions. –  Epictetus Dec 6 '12 at 15:59

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!}$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.