# The Number of R-combinations Repetition Allowed

A note for myself. The number of ways to choose r elements from a set of n elements with repetition allowed can be calculated as the number of ways to arrange $n-1$ “|"s and r "x"s; i.e. it can be shown that there exists a function from either set to another with one-to-one correspondence so that both sets have the same cardinal number by the definition of cardinality. For example, the number of ways to choose three numbers out of $1,2,3,4,5$ is equal to the number of ways to arrange 5 - 1 = 4 ”|“s and 3 "x"s; e.g. xxx|||| means we choose three 1s and |xx||x| means we choose two 2s and one 4. In this example, you can think of 4 + 3 = 7 positions to which each 4 ”|“s and 3 "x"s will be assigned.

Since there are only two symbols ”|“ and "x”, once we have chosen one symbol the other one fills the remaining positions automatically. Then, we have $r+\left(n-1\right)$ positions to which either n-1 “|"s or r "x"s are assigned; i.e. we have $r+\left(n-1\right)$ positions from which to choose n-1 or r positions. Thus, the number of ways to arrange ”|“ and "x” is $\left(\genfrac{}{}{0}{}{r+n-1}{r}\right)=\left(\genfrac{}{}{0}{}{r+n-1}{n-1}\right)$.

## References

Epp., S. S. (2004). Discrete Mathematics with Applications. Cengage Learning.