Name: Number of Onto Functions
Uploaded: 2019-07-19
Duration: 9 min 3 s
Description: In this video, I'll show you how to prove the number of onto functions formula. This will prove handy for a better understanding of this concept.

Question

A party of

10

consists of

2

Americans,

2

Britishmen,

2

Chinese &

4

men of other nationalities (all different). Find the number of ways in which they can stand in row so that no two men of the same nationality are next to one another. Find also the number of ways in which they can sit at a round table.

Accepted Answer

(i) Total possible arrangements $= 10!$

Undesirable cases: When $2$ Americans are together $(A_{1} A_{2})$ or two British are together $(B_{1} B_{2})$ or two Chinese are together $(C_{1} C_{2})$ i.e. we need to subtract $n (A_{1} A_{2} \cup B_{1} B_{2} \cup C_{1} C_{2}) = n (A_{1} A_{2}) + n (B_{1} B_{2}) + n (C_{1} C_{2}) - n [(A_{1} A_{2}) \cap (B_{1} B_{2})] - n [(B_{1} B_{2}) \cap (C_{1} C_{2})] - n [(C_{1} C_{2}) \cap (A_{1} A_{2})] + n [(A_{1} A_{2}) \cap (B_{1} B_{2}) \cap (C_{1} C_{2})]$

For $n (A_{1} A_{2})$ i.e. when $2$ Americans are together:

Consider the two Americans as a group, then we have $9$ entities which can be arranged in $9!$ ways and for each arrangement, there will be $2!$ arrangements amongst the Americans themselves. So, total arrangements in this case $= 9! \times 2!$

Similarly, $n (B_{1} B_{2}) = n (C_{1} C_{2}) = 9! \times 2!$ .

For $n [(A_{1} A_{2}) \cap (B_{1} B_{2})]$ i.e. when $2$ Americans and $2$ Britishmen are together:

Consider $2$ groups of $2$ Americans and $2$ Britishmen in each. Then we have $8$ entities which can be arranged in $8!$ ways and for each arrangement, there will be $2!$ arrangements each for the $2$ Americans and the $2$ British amongst themselves. So, total arrangements in this case $= 8! \times 2! \times 2!$

Similarly, $n [(B_{1} B_{2}) \cap (C_{1} C_{2})] = n [(A_{1} A_{2}) \cap (C_{1} C_{2})] = 8! \times 2! \times 2!$

For $n [(A_{1} A_{2}) \cap (B_{1} B_{2}) \cap (C_{1} C_{2})]$ i.e. when $2$ Americans, $2$ Britishmen and $2$ Chinese are together:

Consider $3$ groups for each. Then we have $7$ entities which can be arranged in $7!$ ways and for each arrangement, there will be $2!$ arrangements each for the groups amongst themselves. So, total arrangements in this case $= 7! \times 2! \times 2! \times 2!$ .

Thus, $n (A_{1} A_{2} \cup B_{1} B_{2} \cup C_{1} C_{2})$ $= 9! \times 2! \times 3 - 8! \times 2! \times 2! \times 3 + 7! \times 2! \times 2! \times 2! = 43 \times 8!$

So, required number of arrangements $= 10! - 43 \times 8! = 47 \times 8!$

(ii) Now they are on a round table.

Total possible arrangements $= (10 - 1)! = 9!$

Undesirable cases: When $2$ Americans are together $(A_{1} A_{2})$ or two British are together $(B_{1} B_{2})$ or two Chinese are together $(C_{1} C_{2})$ i.e. we need to subtract $n (A_{1} A_{2} \cup B_{1} B_{2} \cup C_{1} C_{2}) = n (A_{1} A_{2}) + n (B_{1} B_{2}) + n (C_{1} C_{2}) - n [(A_{1} A_{2}) \cap (B_{1} B_{2})] - n [(B_{1} B_{2}) \cap (C_{1} C_{2})] - n [(C_{1} C_{2}) \cap (A_{1} A_{2})] + n [(A_{1} A_{2}) \cap (B_{1} B_{2}) \cap (C_{1} C_{2})]$

For $n (A_{1} A_{2})$ i.e. when $2$ Americans are together:

Consider the two Americans as a group, then we have $9$ entities which can be arranged in $8!$ ways and for each arrangement, there will be $2!$ arrangements amongst the Americans themselves. So, total arrangements in this case $= 8! \times 2!$

Similarly, $n (B_{1} B_{2}) = n (C_{1} C_{2}) = 8! \times 2!$ .

For $n [(A_{1} A_{2}) \cap (B_{1} B_{2})]$ i.e. when $2$ Americans and $2$ Britishmen are together:

Consider $2$ groups of $2$ Americans and $2$ Britishmen in each. Then we have $8$ entities which can be arranged in $7!$ ways and for each arrangement, there will be $2!$ arrangements each for the $2$ Americans and the $2$ British amongst themselves. So, total arrangements in this case $= 7! \times 2! \times 2!$

Similarly, $n [(B_{1} B_{2}) \cap (C_{1} C_{2})] = n [(A_{1} A_{2}) \cap (C_{1} C_{2})] = 7! \times 2! \times 2!$

For $n [(A_{1} A_{2}) \cap (B_{1} B_{2}) \cap (C_{1} C_{2})]$ i.e. when $2$ Americans, $2$ Britishmen and $2$ Chinese are together:

Consider $3$ groups for each. Then we have $7$ entities which can be arranged in $6!$ ways and for each arrangement, there will be $2!$ arrangements each for the groups amongst themselves. So, total arrangements in this case $= 6! \times 2! \times 2! \times 2!$ .

Thus, $n (A_{1} A_{2} \cup B_{1} B_{2} \cup C_{1} C_{2})$ $= 8! \times 2! \times 3 - 7! \times 2! \times 2! \times 3 + 6! \times 2! \times 2! \times 2! = 260 \times 6!$

So, required number of arrangements $= 9! - 260 \times 6! = 244 \times 6!$

Important Questions on Permutation and Combination

Learn and Prepare for any exam you want !