Q 3: There are n identical balls and m different bins. Let Bn,m be the total number of way to put n balls in m bins.
(a) What are B1,1, B2,1, B1,2, B2,2, B3,2?
(b) Express Bn,m in terms of Bk;m-1, for k = 0,….. n.
(a) To find the total number of ways to put n balls in m bins, we can use the concept of stars and bars.
- B1,1: There is only 1 ball and 1 bin. Since there is only one way to put one ball in one bin, B1,1 = 1.
- B2,1: There are 2 balls and 1 bin. In this case, both the balls must go in the same bin. So, B2,1 = 1.
- B1,2: There is 1 ball and 2 bins. The ball can go into any one of the two bins. So, B1,2 = 2.
- B2,2: There are 2 balls and 2 bins. For each ball, it can either go into the first bin or the second bin. So, there are 2 possibilities for each ball. Hence, the total number of ways is 2 * 2 = 4.
- B3,2: There are 3 balls and 2 bins. Similar to B2,2, each ball can go into either bin, resulting in 2 possibilities for each ball. Therefore, the total number of ways is 2 * 2 * 2 = 8.
(b) To express Bn,m in terms of Bk;m-1, for k = 0, …, n, we can use the recurrence relation for Stirling numbers of the second kind.
The Stirling number of the second kind, S(n, m), represents the number of ways to partition a set of n objects into m non-empty subsets.
Using this concept, we can express Bn,m in terms of Bk;m-1 as follows:
- Bn,m = m * Bn-1,m + Bn-1,m-1
This equation states that to calculate the total number of ways to put n balls in m bins, we either put the nth ball in one of the existing m bins (giving us m * Bn-1,m possibilities), or we create a new bin for the nth ball (giving us Bn-1,m-1 possibilities).
Using this recurrence relation, we can calculate Bn,m for any given values of n and m by iteratively calculating Bk;m-1 for k = 0, …, n, based on the initial conditions B0,0 = 1 and Bn,0 = 0 for n > 0.