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.

im a cs student

To solve this problem, we can use the concept of stars and bars, also known as the balls and bins problem.

(a) Calculating Bn,m:
We'll start by finding the values of B1,1, B2,1, B1,2, B2,2, B3,2.

- B1,1:
When we have only 1 ball and 1 bin, there is only 1 way to put the ball. Therefore, B1,1 = 1.

- B2,1:
With 2 balls and 1 bin, we can either put both balls in the bin or leave one outside the bin. There are 2 possibilities for B2,1.

- B1,2:
Now, when we have 1 ball and 2 bins, we can either put the ball in the first bin or the second bin. Therefore, B1,2 = 2.

- B2,2:
With 2 balls and 2 bins, we can have the following possibilities:
(i) Both balls in the first bin.
(ii) One ball in the first bin and one ball in the second bin.
(iii) Both balls in the second bin.
So B2,2 = 3.

- B3,2:
When we have 3 balls and 2 bins, we can have:
(i) All 3 balls in the first bin.
(ii) 2 balls in the first bin and 1 ball in the second bin.
(iii) 1 ball in the first bin and 2 balls in the second bin.
(iv) All 3 balls in the second bin.
Thus, B3,2 = 4.

(b) Expressing Bn,m in terms of Bk;m-1:
To express Bn,m in terms of Bk;m-1, we need to consider the cases when we have n balls and m bins.

For each of the n balls, we have two options:
(i) Either place it in one of the m bins.
(ii) Or leave it outside all bins.

If we choose option (i), we will have n-1 balls to distribute among m bins, which is equivalent to finding Bn-1,m.

If we choose option (ii), we will have n balls to distribute among m-1 bins, which is equivalent to finding Bn,m-1.

Therefore, Bn,m = Bn-1,m + Bn,m-1.

This recursion formula allows us to calculate Bn,m using smaller values of Bk;m-1 until we reach the base case, which in this situation is B1,1 = 1 and B1,2 = 2.

By using this formula and the base cases, we can compute the values of Bn,m for any n and m.