# 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+(n-1)$$ positions to which either n-1 “|"s or r "x"s are assigned; i.e. we have $$r+(n-1)$$ positions from which to choose n-1 or r positions. Thus, the number of ways to arrange ”|“ and "x” is $$\left(\genfrac{}{}{0ex}{}{r+n-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{r+n-1}{n-1}\right)$$.

## References

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