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.
Need answer for this question
Need answer
To find the number of ways to put n identical balls into m different bins, we can use the concept of stars and bars. This method is commonly known as the stars and bars combinatorial technique.
(a) Let's find the values of B1,1, B2,1, B1,2, B2,2, B3,2 one by one.
B1,1: In this case, we have only one ball and one bin. It means we have only one way to put this ball into the bin. So, B1,1 = 1.
B2,1: Now, we have two balls and one bin. Since the balls are identical, the only thing that matters is the number of balls in the bin. We can either put both balls in the bin or leave one ball outside the bin. So, B2,1 = 2.
B1,2: With one ball and two bins, there are two possibilities. Either we put the ball in the first bin or in the second bin. So, B1,2 = 2.
B2,2: With two balls and two bins, we can distribute the balls in the following ways:
- Both balls in the first bin: B2,2 = 1
- One ball in each bin: B2,2 = 1
- Both balls in the second bin: B2,2 = 1
Thus, B2,2 = 3.
B3,2: With three balls and two bins, the possible distributions are as follows:
- All three balls in the first bin: B3,2 = 1
- Two balls in the first bin, one ball in the second bin: B3,2 = 3 (three possibilities for the positioning of the two balls)
- One ball in the first bin, two balls in the second bin: B3,2 = 3 (three possibilities for the positioning of the two balls)
- All three balls in the second bin: B3,2 = 1
Hence, B3,2 = 8.
(b) To express Bn,m in terms of Bk;m-1, we need to consider the balls and their distribution.
Let's consider distributing n balls into m bins. For the first m-1 bins (from bin 1 to bin m-1), we can distribute the balls in any way, so the number of ways to distribute them is Bn,m-1.
For the last bin (bin m), we have two possibilities:
1. We can leave it empty, which means all the balls will be distributed in the first m-1 bins. In this case, the number of ways to distribute the balls is Bn,m-1.
2. We can put at least one ball in bin m. Suppose we put k balls in bin m. Now we have n-k balls remaining for the first m-1 bins. The number of ways to distribute the remaining balls is Bn-k,m-1 because we have essentially reduced the problem to distributing n-k balls into m-1 bins.
Since k can vary from 1 to n, we need to sum up the possibilities for each k. This gives us the total number of ways to distribute n balls into m bins:
Bn,m = Bn,m-1 + Bn-1,m-1 + Bn-2,m-1 + ... + B1,m-1
= ∑ Bk, m-1 (sum from k=1 to n)
Therefore, Bn,m can be expressed in terms of Bk;m-1, where k ranges from 1 to n.
*course
I assume you have learned about the ball-and-bin problem in your calls. It may have been called the star-and-bar problem, which is easier to visualize mathematically.
Try to read over your notes and post your answer for a check if you wish.
If you still have difficulties, feel free to explain your attempt.
If your notes are incomplete, or if you were absent from class on the particular day, you can read up the following:
https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)