Skip to main content

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 n1 "|"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+(n1) positions to which either n-1 "|"s or r "x"s are assigned; i.e. we have r+(n1) positions from which to choose n-1 or r positions. Thus, the number of ways to arrange "|" and "x" is (r+n1r)=(r+n1n1).

References #

% reference discrete_math -l 350-351 %