There are several questions (like this one) that involve counting the ways that $b$ balls can be placed into $n$ spaces such that no balls are adjacent, for instance $B\_ B\_ B\_ $ but not $ BB\_ B\_\, \_$. I've been playing with this, and found that the formula $$ \binom{n-b+1}{b}$$seems to work, but I don't know how to prove this. Additionally, I don't understand the intuition behind it.
I thought of induction on b: Assume $\binom{n-b+1}{b}$ holds for $b$ balls. If we place $b-1$ balls in left to right order, we notice that the ways to place the $b$th ball declines by one for each new ordering, creating a triangular arrangement. For instance, $n=5$, $b=2$ gives $ B\_ x x x$, $\_ B\_ xx$, and $\_\,\_ B\_ x$ where $x$ is possible placements of the second ball.
Adding another ball into the mix effectively removes the largest two "diagonals" in such arrangements, but how does this become $\binom{n-b}{b+1}$?
Induction on n: you add a space, and therefore add a new "diagonal" onto each current arrangement. Again, I'm not seeing it.
EDIT:
Could I assume that the base case is where the balls are precisely fixed, as in $B\_ B\_ \dots B\_ B$ where the run ends on a ball and $n=2b-1$? In that case, there is only one arrangement, which corresponds to $$\binom{n-b+1}{b}=\binom{2b-1 - b + 1}{b}=\binom{b}{b} = 1$$ Now, add one more space to this arrangement: a space at the end, between the last pair, between the next to last pair, and so on, and one at the start, for a total of $b+1$ ways. Now compare against $n+1$ in the relationship above, where $n+1 = 2b-1+1 = 2b$, thus $$\binom{n+1-b+1}{b}=\binom{2b-b+1}{b}=\binom{b+1}{b} = b+1$$What else must I prove?
Start with something like: $$n_0Bn_1Bn_2\dots n_{b-1}Bn_b$$where then $n_i$ are integers.
Here $n_0$ denotes the number of spaces on the utmost left, $n_b$ the same on the utmost right and e.g. $n_1$ the number of spaces between the first and the second ball.
Then to be found is the number of sums that satisfy $\sum_{i=0}^bn_i=n-b$ and where $n_0,n_b\geq0$ and $n_i>0$ for every other $i$.
Setting $m_0=n_0, m_b=n_b$ and $m_i=n_i-1$ for the other $i$ that comes to the same as finding the number of sums $\sum_{i=0}^bm_i=n-2b+1$ where $m_i\geq0$ for every $i$.
Then with stars and bars we find that there are:$$\binom{(n-2b+1)+b}{b}=\binom{n-b+1}{b}$$possibilities.