I have 'n' identical balls and 'k' distinct bags. So total number of ways I can put balls with no restriction in bags is ${k+n-1 \choose k-1}$. So I want to know the number of times there were exactly 'b' balls in a particular bag.
Eg-> I have 3 balls and 3 bags. So ${3+3-1 \choose 3-1}$ = 10 ways.
If b = 0, there are 4 times [(0,0,3),(0,3,0),(0,1,2),(0,2,1)]
If b = 1, there are 3 times [(1,0,2),(1,2,0),(1,1,1)]
(here I am assuming that the chosen bag is first one)
So how many times do I get exactly 'b' balls in a particular bag?
Best Answer
Your formula is slightly wrong. The number of ways in which $n$ balls can be put in $k$ distinct bags is $\binom{n+k-1}{\color{red}k-1}$. The reason being, that while applying stars and bars, we have to insert $k-1$ bars in any of $k+n-1$ positions, so that there are $k$ partitions formed, which we assume form the contents of each bag. For example, distributing $3$ balls in two boxes means you have to put $1$ bar between three balls, and there are $4$ places for it($2$ in the middle and two on either side) : $$ - \cdot-\cdot-\cdot- $$
The problem that you state can be reformed as follows : if $x_i$ denotes the number of balls in bag $b_i$, then the number of ways that $n$ balls can be put in $k$ bags is the number of non-negative solutions to the equation $x_1+...+x_k = n$.
Suppose there are exactly $b$ balls in some pre-chosen bag, say $b_1$. Then, the rest of the balls contain exactly $n-b$ ball without restriction. So the number of possibilities is the number of solutions to $x_2+...+x_{k} = n-b$, the answer to which is $\binom{n-b+k-2}{k-2}$, using the very same stars and bars logic with which one determines the number of non-negative solutions to $x_1+...+x_k = n$.
For example, if $n=3,k=3$, we see that $\binom 52 = 10$.
If $b = 0$, then $\binom{3-0+3-2}{3-2} = \binom{4}{1} = 4$ possibilities present themselves. They are as you have specified.
If $b = 1$, then $\binom{3-1+3-2}{3-2} = \binom 31 = 3$ with possibilities as given.