Permutations and Combinations

◄ Previous: 9.2. Selection with repetition Next: 11. Number of Paths in a Grid ►

10. Distribution of distinct objects

Suppose 3 distinct balls are to be placed into two distinct boxes \({S_1}\)and\({S_2}\). Now in this case since balls are distinct, we have to see which ball and how many balls are placed in a box. If the balls are \({B_1},\;{B_2}\) and\({B_3}\). 


Each ball can be placed into either box \({S_1}\) or \({S_2}\). So each ball has two ways of distribution. Total number of ways \({2^3} = 8\) ways. These are the 8 possible cases:


In general, we can conclude that \(r\) distinct objects can be distributed among \(n\) recipients in \(n \times n \times n \times .... \times n = {n^r}\) ways. This formula includes cases where one or more recipients are not given any objects.

Example 1:

In how many ways 6 different balls can be placed into 3 distinct boxes such that each box may or may not receive any ball

Each ball has 3 choices, it can be placed into any of the boxes.
Hence total number of ways = \({3^6} = 729\)
Example 2:

A set contains 10 elements, how many subsets can be formed such that each subset contains at least one element.

Each element of the set may or may not be selected in the subset. Hence total number of subsets = \({2^{10}} = 1024\)
But in one case none of the element is selected, (that makes an empty subset), hence number of subsets that contains at least one element = 1024 – 1 = 1023
Example 3:

There are 50 questions on a question paper. In how many ways can a student attempt the paper? They may choose to attempt or not attempt any question from the paper.

We see that each question can be attempted or not attempted. Hence each question has two independent choices.
Total number of ways of attempting the paper is \(2 \times 2 \times 2 \times 2....... \times {2_{{\rm{(50}}\,\,{\rm{times)}}}} = {2^{50}}\)
Example 4:

There is a set S = {1, 2, 3, 4, 5, 6}, how many subsets of S are there such that sum of the elements of the subset is more than 10.

The sum of the elements of S = 1 + 2 + 3 + 4 + 5 + 6 = 21. Now if we split S into two sets, then sum of the elements of one of the sets is more than 10 and for the other it is less than or equal to 10. Since the sum of all the elements is 21 so both cannot have a sum more than 10.
Total number of subsets of S = \({2^6} = 64\).
Hence half of them will have sum of their elements more than 10.
Required answer = \(\frac{{64}}{2} = 32\)
Example 5:

There is a set S = {1, 2, 3, 4, 5, 6, 7}, how many subsets can be formed from this set such that the subset contains at least one of the elements 1, 2, 3.

Total number of subsets = \({2^7} = 128\)
Number of subsets, which do not contain any of the three elements = \({2^{7 - 3}} = 16\)
Number of subsets containing at least one of the elements 1, 2, 3 = 128 – 16 = 112
◄ Previous: 9.2. Selection with repetition Next: 11. Number of Paths in a Grid ►