12
$\begingroup$

Selecting groups of r items from n items

Example : In how many ways we can select groups of two from 6 students.

Concept :

Let the students be A, B, C, D, E, F . A can group with each of the remaining five as AB, AC, AD, AE, AF now we have B, C, D, E, F left, B can group with each of the remaining four as BC, BD, BE, BF, now we have C, D, E, F left, C can group with each of the remaining three as CD, CE, CF, now we have D, E, F left, D can group with each of the remaining two as DE and DF, E can group with the last one F , EF. Therefore we have AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF and EF, fifteen groups of twos.

Alternatively One student A can select the other one of his group in $^5C_1$ ways . If B is another student who does not belong in the group A, we can select the other one of his group $^3C_1$ ways the remaining two consists of the third group. = 5 $\times 3 \times 1$

But as per my understanding :

I used : $^6C_2$ which is equal to 15.

However if I am using this concept in the following question :

Problem :

In how many ways can we divide 12 students in groups of fours.

A group of 4 can be chosen from 12 students is :

$^4C_{12} = 495$ which is wrong answer and answer is $5775$ Please help on this.. Thanks..

$\endgroup$
10
$\begingroup$

The $12$ students can be lined up in $12!$ ways.

Put in dividers after every fourth student.

For example:

Given $ABCDEFGHIJKL$, we would put in dividers to get $ABCD|EFGH|IJKL$.

We have overcounted, though, in two different ways. Let's examine the resulting problems.

One problem is with regard to the three separate groupings appearing multiple times. In the example above, we would be counting $EFGH|ABCD|IJKL$ a second time. Since there are three groups, we need to divide by $3!$ to avoid this sort of overcounting.

The second problem is that, within each of the three groups, we have four people who are going to appear multiple times. In the example above, we would be counting $CDAB|EFGH|IJKL$ a second time. For each of the groupings, we need to divide by $4!$ to avoid this sort of overcounting. This means dividing by $4!4!4!$ to amelioriate the second issue.

Then our answer becomes:

$$\frac{12!}{3!4!4!4!} = 5,775$$

$\endgroup$
4
$\begingroup$

Perhaps it is easier to see the general case, having to divide $nk$ students in groups of $k$. One way to do it is the following, although the approach of Benjamin Dickman (which lends itself to a straightforward generalization) is probably cleaner.

Pick a student at random, and "pair" her with the $$ \binom{nk-1}{k-1} $$ groups of $k-1$ among the other $nk-1$.

Now you are left with $(n-1)k$ students. Pick one at random, and pair him with the $$ \binom{(n-1)k-1}{k-1} $$ groups of $k-1$ among the other $(n-1)k-1$.

At this point you will have guessed that the formula is $$ \prod_{i=0}^{n-1} \binom{(n-i)k-1}{k-1}. $$ (The last factor is $1$, but I have included it for completeness.)

Benjamin Dickman's formula would be the equivalent $$ \frac{(nk)!}{n! (k!)^{n}}. $$

In your example of the $12$ students to be divided in groups of $4$, you have $n = 3$ and $k = 4$, and this reads $$ \binom{11}{3} \cdot \binom{7}{3} \cdot \binom{3}{3} = 165 \cdot 35 \cdot 1 = 5775. $$

$\endgroup$
1
$\begingroup$

Let's attack first the smaller problem of six students divided into three groups of two. We can divide this problem into three parts: How many groups of two students can you create from six students; how many groups of two students can you create from four students; and how many groups of two students can you create with two students?

Here are all the possible combinations of the first group (remember that order doesn't matter within the group):

Students: A, B, C, D, E, and F are unique.

AB  -  BC  -  CD  -  DE  -  EF   - 
AC  -  BD  -  CE  -  DF        
AD  -  BE  -  CF             
AE  -  BF                  
AF

5 + 4 + 3 + 2 + 1 = 15

This result can also be found using the expression:

$\frac{6!}{2!(6-2)!}=720/(2*24)=(6\times 5)/2=15$

Now how many groupings of two people can we create from the four remaining students? Let's give these four students designations as follows:

Students: s1, s2, s3, s4

The combinations can be listed as before:

s1,s2  -  s2,s3  -  s3,s4   - 
s1,s3  -  s2,s4  -         
s1,s4                   

3 + 2 + 1 = 6

This is equal to:

$N=\frac{4!}{2!2!}=(4\times 3)/2=6$

There is left two students after the first two groupings have been made. There is only one combination possible with these two last students (because order doesn't matter). for this last group (say $g1,g2$) we have:

$N3=\frac{2!}{2!(6-2-2-2)!}=\frac{2!}{2!0!}$

The total number of possible groupings of six students into three groups of two is:

$N1*N2*N3=\frac{6!}{2!4!}\frac{4!}{2!2!}\frac{2!}{2!0!}$=15\times 6\times 1=90 (0!=1)

This can be reduced to $N=\frac{6!}{2!2!2!}$

In general we have the expression:

$N=\frac{n!}{n1!n2!n3!}$ (where $n=n1+n2+n3$)

In our concrete case $n=6, n1=2, n2=2$, and $n3=2$.

As a side-note: if order did matter in the groupings we'd multiply our result immediately above by $2!2!2!$ to simply get $N=6!=720$. The problem would then be reduced to finding all possible combinations of six students without replacement.

In such a case we have:

$N=(n-1+1)\cdot (n-2+1)\cdot (n-3+1)...(n-k+1)$ (where $k=n$)

or simply:

$N=n!$

Now for the larger problem (since we understand the formula) we may find all possible combinations of 12 students divided into three groups of 4 as:

$N=\frac{n!}{n1!n2!n3!}$

$N=\frac{12!}{4!4!4!}=34650$ possible combinations

Note again this equality:

$\frac{n!}{n1!n2!n3!}=\frac{n!}{n1!(n-n1)!}\cdot\frac{(n-n1)!}{n2!(n-n1-n2)!}\cdot\frac{(n-n1-n2)!}{n3!(n-n1-n2-n3)!}$

The quantity $(n-n1-n2-n3)!=0!=1$ and the numerator of each subsequent fraction cancels out with the latter part of the denominator of the fraction immediately preceding it.

$\endgroup$
1
$\begingroup$

Another way to look at it is the following: Calculate the number of ways to put the 12 students in three bins each of which contains 4:

$\binom{12}{4} \cdot \binom{8}{4} \cdot \binom{4}{4} = 495 \cdot 70 \cdot 1 = 34650.$

The above considers the positions of the bins, so we need to remove duplicates. Each combination of 3 groups has 3! = 6 permutations, so the final answer is

$\frac{34650}{6} = 5775$

Edit per the suggestion of G Cab:

For nk students divided into n groups each of which has k students, the equation would be:

$\frac{\binom{nk}{k}\cdot\binom{(n-1)k}{k}\cdot\binom{(n-2)k}{k}...\binom{(n-(n-1))k}{k}}{n!}$

$=\frac{\frac{(nk)!}{k!((n-1)k)!}\cdot\frac{((n-1)k)!}{k!((n-2)k)!}\cdot\frac{((n-2)k)!}{k!((n-3)k)!}...\frac{((n-(n-1))k)!}{k!}}{n!} $

$= \frac{\frac{(nk)!}{k!}\cdot\frac{1}{k!}\cdot\frac{1}{k!}...\frac{1}{k!}}{n!} $

$=\frac{\frac{(nk)!}{(k!)^n}}{n!} $

$=\frac{(nk)!}{n!(k!)^n}$

$\endgroup$
  • 1
    $\begingroup$ concise and smart ! (+1). I invite you and complete it , for the general case of $nk$ students in $n$ groups, which easily leads to $(nk)!/(n!(k!)^n)$ $\endgroup$ – G Cab Oct 2 '16 at 16:48

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