Mathematics | Generalized PnC Set 2

1. Distinguishable balls and Distinguishable boxes –

• Example 1 – In how many ways can 10 prizes be distributed among 5 people without exclusion?
• Solution – This situation is analogous to distributing distinct balls into distinct boxes without exclusion. For every prize there are 5 choices of people who can receive it. So the number of ways of distributing the prizes is- .


• Example 2 – How many ways are there to distribute hands of 5 cards to each of four players from a standard deck of 52 cards?
• Solution – This situation is analogous to distributing distinct balls into distinct boxes where each box must have a certain number of balls. The first person can get the cards in C(52,5) ways. The second person can get the cards in C(47,5) ways and so on till the fourth person can get the cards in C(37,5) ways. After 20 balls(cards) have been distributed, the remaining cards form the fifth box (or player). This can be solved with the product rule, total ways- = = = This could also be solved using the formula mentioned above using group sizes 5,5,5,5 and 32.

2. Indistinguishable balls and Distinguishable boxes –

3. Distinguishable balls and Indistinguishable boxes –

4. Indistinguishable balls and Indistinguishable boxes –

• Example 1 – How many ways are there to put four different balls into three indistinguishable offices without exclusion?
• Solution – Enumerating all possible scenarios instead of using the Stirling Formula is easier. Let the four balls be . All balls in one box – 3 balls in one box and 1 in another- 2 balls in one box and 2 in another- 2 balls in one box and 1 each in the remaining boxes- This gives us a total of- 1 + 3 + 4 + 6 = 14 ways.


• Example 2 – How many ways are there to put 4 indistinguishable balls into 3 indistinguishable boxes?
• Solution – As mentioned above, the above problem is analogous to finding the number of partitions of the positive integer 4, where the number of partitions is less than or equal to 3. Enumerating all possible ways- All four balls in one box – 4 3 balls in one box, 1 ball in one – 3,1 2 balls in two boxes – 2,2 2 balls in 1 box, 1 ball in two boxes each – 2,1,1 Total number of ways = 4 It is similar to finding the number of partitions of 4- 4 = 4 3 + 1 = 4 2 + 2 = 4 2 + 1 + 1 = 4

GATE CS Corner Questions

1. GATE CS 2003, Question 34
2. GATE CS 2015 Set-3, Question 15

References-