# Equivalence of another formula for the number of $r$-combinations with repetition allowed

Basically it means choosing r things out of n, where order doesn't matter, and you are allowed to pick a thing more than once. For example, $\{1, 1, 2\}$ out of $\{1, 2, 3, 4\}$.

I managed to find another solution:

$${n \choose r} + (r-1){n \choose r-1} + (r-2){n \choose r-2} + \cdots + {n \choose 1}$$

I am having trouble proving that these two are equivalent.

• Are you sure there is not an $r$ in front of the first term? Commented Mar 1, 2015 at 12:06
• I think there isn't.
– qed
Commented Mar 1, 2015 at 12:07
• The formula cannot be correct (with or without an initial factor $r$) because the extra terms added by increasing $r$ beyond $n$ are all $0$, but $\binom{n+r-1}{r-1}=\binom{n+r-1}n$ does keep increasing (polynomially in $r$) when $r$ increases beyond $n$. Did you try some small explicit values? Commented Mar 1, 2015 at 12:13
• Yes, I did. For example, n = 4, r = 3. But I now realize I didn't take into consideration that multiple elements can be repeated at the same time, such as {1, 1, 2, 2} out of {1, 2, 3, 4, 5}. So, indeed, this is not a solution at all.
– qed
Commented Mar 1, 2015 at 12:17

As has already been pointed out, unfortunately the two solutions are not equivalent.

However, if we use Pascal's Rule:- $${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$$ and apply this $r$ times to ${r+n-1 \choose r}$ the following solution can be shown to be equivalent:-

$${r-1 \choose r-1}{n \choose r} + {r-1 \choose r-2}{n \choose r-1} + {r-1 \choose r-3}{n \choose r-2} + \cdots + {r-1 \choose 0}{n \choose 1}$$ In other words the following relationship holds:- $${r+n-1 \choose r}=\sum_{k=1}^r{r-1 \choose k-1}{n \choose k}$$ Perhaps allowing the repetition of multiple elements at the same time results in the binomial terms ${r-1 \choose k-1}$ for $k\in \{1,2,..,r\}.$

• I think maybe you want to replace the first n-1 with n in the identity you're using. Commented Mar 1, 2015 at 22:57
• @user84413: Well spotted - there was an error in the identity I stated. I have fixed this, but with $k$ instead of $k-1$. Commented Mar 2, 2015 at 8:39
• Thanks - I guess my "correction" wasn't quite correct. Commented Mar 2, 2015 at 16:00