Calculate the number of ways in which 2 indistinguishable balls can be placed in 3 boxes.
Answers
Answer:
Explanation:
1.11 Indistinguishable Balls in Indistinguishable Boxes
To study the number of onto functions f : M−→N, we were lead to the study of “partition of a
set consisting of m elements into n parts”. In this section, we study the partition of a number
m into n parts and look at a few problems in which this idea can be used.
Definition 1.11.1 (Partition of a number). A partition of a positive integer m into n parts, is
a non-increasing sequence of positive numbers x1, x2, . . . , xn such that Pn
k=1
xk = m. The number
of such partitions is denoted by Π(m, n).
Remark 1.11.2. 1. For example, the distinct partitions of 7 into 4 parts are given by 4 +
1 + 1 + 1, 3 + 2 + 1 + 1, 2 + 2 + 2 + 1. Hence, Π(7, 4) = 3. Verify that Π(7, 2) = 3 and
Π(7, 3) = 4.
2. For a fixed positive integer m, Π(m) denotes the number of partitions of m. Hence, Π(m) =
Pm
k=1
Π(m, k). Verify that Π(7) = 15.
3. By convention, we let Π(0, 0) = 1 and Π(m, n) = 0, whenever n > m.
We are now ready to associate the study of partitions of a number with the following problems.
Example 1.11.3. 1. Determine the number of ways of putting m indistinguishable balls
into n indistinguishable boxes with the restriction that no box is empty?
Solution: Since the balls are indistinguishable balls, the problem reduces to counting the
number of balls in each box with the condition that no box is empty. As the boxes are also
indistinguishable, they can be arranged in such a way that the number of balls inside them
are in non-increasing order. Hence, we have the answer as Π(m, n).
2. Determine the number of ways to put m indistinguishable balls into n indistinguishable boxes.
Solution: The problem can be rephrased as follows: “suppose that each box already has
1 ball, i.e., initially, each of the n boxes are non-empty. Now let us determine the number of ways of putting m indistinguishable balls into the n indistinguishable boxes that are
already non-empty.” This new problem is same as “in how many ways can m + n indistinguishable balls be put into n indistinguishable boxes with the restriction that no box
is empty”. Therefore, the answer to our problem reduces to computing Π(m + n, n).
3. Use the above idea to show that Π(2m, m) = Π(m) for any positive integer m. Hint:
Π(2m, m) corresponds to “putting 2m indistinguishable balls into m indistinguishable boxes
with the condition that no box empty”, where as Π(m) corresponds to “putting m balls into
m indistinguishable boxes”.
1.11. INDISTINGUISHABLE BALLS IN INDISTINGUISHABLE BOXES 35
Till now, we have been looking at problems that required arranging the objects into a row.
That is, we differentiated between the arrangements ABCD and BCDA. In this section, we
briefly study the problem of arranging the objects into a circular fashion. That is, if we are
arranging the four distinct chairs, named A, B, C and D, at a round table then the arrangements
ABCD and the arrangement BCDA are the same. That is, the main problem that we come
across circular arrangements as compared to problems in the previous sections is “there is no
object that can truly be said to be placed at the number 1 position”. The problems related with
round table configurations will be dealt at length in Chapter 3.
So, to get distinct arrangements at a round table, we need to fix an object and assign it the
number 1 position and study the distinct arrangement of the other n − 1 objects relative to the
object which has been assigned position 1. We will look at two examples to understand this
idea.
Example 1.11.4. 1. Determine the number of ways to sit 8 persons at a round table.
Solution: Method 1: Let us number the chairs as 1, 2, . . . , 8. Then, we can pick one of
the person and ask him/her to sit on the chair that has been numbered 1. Then relative to
this person, the other persons (7 of them) can be arranged in 7! ways. So, the total number
of arrangements is 7!.
Method 2: The total number of arrangements of 8 persons if they are to be seated in a row
is 8!. Since the cyclic arrangement P1P2 · · · P8 is same as the arrangement P8P1P2 · · · P7
and so on, we need to divide the number 8! by 8 to get the actual number as 7!.
2. Recall Example 1.9.7. Suppose we are now interested in making the 4 couples sit in a
round table. Find the number of seating arrangements.
Solution: Note that using Example 1.11.4.1, the 4 cohesive units can be arranged in 3!
ways. But we can still have the couples to sit either as “wife and husband” or “husband
and wife’. Hence, the required answer is 2
43!