We ought never to allow ourselves to be persuaded of the truth of anything unless on the evidence of our own reason – René Descartes
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 "|"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
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 positions to which either n-1 "|"s or r "x"s are assigned;
i.e. we have positions from which to choose n-1 or r positions.
Thus, the number of ways to arrange "|" and "x" is .