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.
To find the total number of ways to put n identical balls in m different bins, we need to consider the following scenarios:
(a) B1,1: There is only one way to put one ball in one bin.
B2,1: There are two balls that need to be placed in one bin. Since the balls are identical, there is only one way to do this. So, B2,1 = 1.
B1,2: There is one ball that needs to be placed in two different bins. Since the balls are identical, there is only one way to do this. So, B1,2 = 1.
B2,2: There are two balls that need to be placed in two different bins. The balls can either be placed in the same bin (BB) or in different bins (AB or BA). So, B2,2 = 3.
B3,2: There are three balls that need to be placed in two different bins. The possibilities are:
- All three balls in one bin (BBB).
- Two balls in one bin and one ball in the other bin (ABB or BAB).
- One ball in one bin and two balls in the other bin (BA or AB).
So, B3,2 = 5.
(b) To express Bn,m in terms of Bk,m-1, we can use the following formula:
Bn,m = Bn-1,m-1 + Bn-2,m-1 + Bn-3,m-1 + ... + B2,m-1 + B1,m-1 + B0,m-1
This formula suggests that the number of ways to put n balls in m bins can be determined by considering the cases where the last ball is placed in a new bin (Bn-1,m-1), an existing bin with two balls (Bn-2,m-1), an existing bin with one ball (Bn-3,m-1), and so on, until the case where the last ball is placed in a bin with no balls (B0,m-1).
By using this recursive formula, you can calculate Bn,m in terms of Bk,m-1, for k = 0, ..., n.