Q: 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 Bn,m, you need to determine the number of ways to put n identical balls into m different bins.
For B1,1, you have only one ball and one bin. In this case, there is only one way to place the ball in the bin.
For B2,1, you have two balls and one bin. Since the balls are identical, the order in which they are placed does not matter. Therefore, you can either put both balls in the bin or not put any ball in the bin. Hence, the number of ways is 2.
For B1,2, you have one ball and two bins. Similarly, since the ball is identical, the order of bins does not matter. Therefore, you can place the ball in the first bin or the second bin. Thus, the number of ways is 2.
For B2,2, you have two balls and two bins. There are several possible combinations: you can put both balls in the first bin, both balls in the second bin, one ball in the first bin and the other ball in the second bin, or no ball in either bin. Hence, the number of ways is 4.
For B3,2, you have three balls and two bins. The possible combinations are: all three balls in the first bin, all three balls in the second bin, two balls in the first bin and one ball in the second bin, two balls in the second bin and one ball in the first bin, or no ball in either bin. Therefore, the number of ways is 5.
(b) To express Bn,m in terms of Bk,m-1, for k = 0,...,n, we can use the following recurrence relation:
Bn,m = Bn-1, m-1 + Bn-1, m
This means that the number of ways to put n balls in m bins is equal to the sum of two terms: the number of ways to put n-1 balls in m-1 bins (considering the last bin is filled) plus the number of ways to put n-1 balls in m bins (considering the last bin is empty).
By using this recurrence relation, we can express Bn,m in terms of Bk,m-1 for k = 0,...,n.