Grouping and Distribution
This is a very important concept of permutation and combination where some higher order fundamentals of permutation and combination is involved – the reason for reserving this topic for the end.
Here is the list of articles in this series of permutation-combination for quick reference. Ideally you should check these articles in order to gain better understanding of the whole concept –
- Principle of Counting
- Permutations Introduced
- Permutations – Special cases
- Combinations – Introduction
- Combinations – Grouping & Distribution
What is the difference between grouping and distribution?
To distribute something, first grouping is done. Only after you have made groups of some objects, you might want to distribute these groups in various places. For example, after you made groups of some toys, you might want to distribute these groups among some children. Or, after dividing some number of toffees into groups, you might want to distribute these groups into boxes.
Just as the objects that we group can be similar or dissimilar, so can the places that we assign these groups to be similar or dissimilar.
While distributing groups, we need to keep one rule in mind: We permute the groups only if these places for distribution are dissimilar, otherwise not.
Say, we have 2 items- X and Y and I have to split them into two groups. There is only one way of doing it – X goes in one group and Y in the other. However, if I have to distribute among 2 people A and B, then these 2 groups can be permuted in 2! ways.
Division of dissimilar items into groups of EQUAL SIZE
Let’s take a very simple example. In how many ways can you divide 4 different things (say A, B, C and D) into two groups having two things each?
You would like to say that we select two things out of the four and two would be left behind, i.e. 4C2 = 6 ways. But are there really 6 ways?
Take a look. We can divide four things, A, B, C and D into two groups of two in the following ways:
AB – CD
AC – BD
AD – BC
You can keep trying but there is no fourth way to do it. So where have the remaining 3 ways calculated through 4C2 = 6 disappear? If you look carefully, there was an overlap. When we select 2 things out of 4, we can do it in 6 ways – AB, AC, AD, CD, BD and BC but when we select the first three groups, the last three get automatically selected without having to select them separately and vice-versa. So when we select AB, CD is automatically selected and vice-versa.
This overlap will manifold itself if we increase the number of items further.
So be very careful not to apply the usual combinations formula whenever we have to divide into groups of equal size. However, if the groups contain unequal number of things, then our earlier method of using combinations formula for selection will be valid as will be discussed in the next section.
Let me now increase the objects to 5. How would you divide these 5 distinct (dissimilar) objects into groups of 2, 2 and 1?
The single object can be chosen in 5C1 = 5 ways. The rest of the 4 objects can be divided into two equal groups in 3 ways as explained above. Therefore, total number of ways = 5 x 3 = 15.
Note: In the distribution, order is important hence the divisible things can be arranged in m! ways since things are divided into m groups.
Division of dissimilar items into groups of UNEQUAL SIZE
Say we have k things and we have to divide them into 2 groups containing m and n things respectively such that m+n =k, then this can be done in k!/m!.n! ways. This is because m things can be selected out of k things in kCm ways and when m things are taken, n things are left to form the other group of n things which can only be done in nCn =1 way. Hence the required number of ways is kCm = m+nCm = (m+n)!/(m+n-n)!.n! = k!/m!.n!.
We can extend the same concept for increased number of groups as long as the number of items in all the groups add up to the total i.e. n.
The number of ways in which n distinct things can be DIVIDED into R unequal groups containing a1, a2, a3, ……, aR things (different number of things in each group and the groups are not distinct)
= nCa1 × (n-a1)Ca2 × … × (n-a1-a2-….-a(r-1))CaR
=n! / a1! a2! a3!…….aR! (here a1 + a2 + a3 + … + aR = n)
What if there are n distinct things and we have to find out the number of ways in which they can be distributed among r persons such that some person get a1 things, another person get a2 things, . . . . and similarly someone gets aR things (each person gets different number of things)?
Number of ways in which n distinct things can be divided into R unequal groups containing a1, a2, a3, ……, aR things (different number of objects in each group and the groups are distinct)
=n! / a1! a2! a3!…….aR!x R! (here a1 + a2 + a3 + … + aR = n)
Division of IDENTICAL / SIMILAR ITEMS into Groups
Number of ways in which n identical things can be divided into r groups, if blank groups are allowed i.e. each can receive zero or more things (here groups are numbered, i.e., distinct), where 0≤r≤n = (n+r-1)C(r-1)
Number of ways in which n identical things can be divided into r groups, if blank groups are not allowed i.e. each receives at least one item (here groups are numbered, i.e., distinct), where 1≤r≤n = (n-1)C(r-1)
Number of ways in which n identical things can be divided into r groups so that no group contains less than m items and more than k (where m<k) is coefficient of xn in the expansion of (xm + xm+1 +…..xk)r
Some Important Results:
With this discussion on Grouping and Distribution we come to an end on the topic Permutations and Combinations.
Please post in your doubts, queries and interesting problems in the comments box.
Hope you enjoyed reading these 5 articles as much as I enjoyed writing them.