If we had something like:
$$
x_1 + x_2 + x_3 = 7, x_i >= 0
$$
It could be solved using the stars and bars method:
$$
****|**|*
$$
The number of ways to choose 2 spots for the bars is 9 choose 2. But using the $(n+r-1)$ choose $r$ formula, it would be:
(7 + 3 – 1) choose 3 = 9 choose 3.
So I'm confused why the formula for combinations with repetition isn't $(n+r-1)$ choose $(r-1)$. It seems like what we care about is the number of bars involved in choosing r objects, which is $r-1$. Why is r used in the formula whatsoever?
Best Answer
You are confusing yourself as to what role the $n$ plays and what role the $r$ plays. In order to try to clarify this, I will use neither $n$ nor will I use $r$.
The number of non-negative integer solutions to the following system:
$$\begin{cases}x_1+x_2+\dots+x_a = b\\0\leq x_i\end{cases}$$
is going to be
$$\binom{a+b-1}{a-1}$$
which is the same thing as
$$\binom{a+b-1}{b}$$
These are equal due to the well known identity that $\binom{n}{r}=\binom{n}{n-r}$, e.g. to choose $r$ winners from $n$ people and the rest be losers is the same as choosing $n-r$ losers from $n$ people instead and the rest be winners.
Your confusion comes from some people choosing to write the formula with $n$ representing the number of balls and $k$ the number of bins while other people might choose to write $n$ as the number of bins with $k$ as the number of balls. In the first case it might have been written as $\binom{n+k-1}{k-1}$ and in the second case it might have been written as $\binom{n+k-1}{k}$. These are the same formula just with the roles of $n$ and $k$ reversed!
In either case, the top of the binomial coefficient will be the number of balls plus the number of bins minus one, and the bottom will be the number of bins minus one (or equivalently, the number of balls). Do not try to memorize formulas based on how they appear... instead try to learn formulas for what they mean and what they actually represent.