Number of ways to choose 4 among 10 if repetition is allowed Q: In how many ways can you choose 4 things among 10 if the order does not matter and you can choose the same item several times?
I am trying to understand the intuition behind the answer.
The answer is:
$$ \binom{13}{9} = 715$$
I am told the problem can be mapped to:
$$x_1+x_2+x_3...x_{10}=4$$
But how does the $\binom{13}{9}$ map to $x_1+x_2...x_{10}=4?$
 A: I frame the problem as choosing (order doesn't matter) 4 items from 10 categories (each category may be repeatedly picked)?
Or, more generally, picking $r$ items from $n$ categories (repetition allowed).
For each selection, use $(n-1)$ vertical bars as separators to illustrate the $n$ categories, and represent the $r$ selected items by filling $r$ stars in the according categories.
Notice that every selection contains $[(n-1)+r]$ placeholders/positions all filled by stars & bars, and that selections are distinguished by the $r$ stars filling in different combinations of positions (the vertical bars filling in the remaining positions).
Therefore, the total number of selections is the number of ways to choose $r$ positions from $[(n-1)+r]$ positions, i.e., $$\binom{n-1+r}{r}.$$
So for our problem at hand, the answer is $$\binom{10-1+4}{4}=\binom{13}{4}=\binom{13}{9}=715.$$
A: To make the mapping from your problem to
$$x_1 + x_2 + \cdots + x_{10} = 4$$
more explicit: each $x_i$ must lie in $\{0,1,2,3,4\}$, depending how many times the element $i$ has been chosen; then this sum will be 4 iff exactly four items in total have been chosen. "Order does not matter" is captured by the commutativity of addition.
For a given assignment of values to $x_i$'s, we could write this out using ordinary digits. But if we instead write $0$ as $0$, $1$ as $S(0)$, $2$ as $S(S(0))$, and so on (here $S$ stands for "successor" and in general $S(n) = n+1$), then we can see that every assignment of values to this equation will involve four $S$s and ten zeros.
To be syntactically correct we need the last symbol to be a 0, but the four $S$'s and remaining nine zeros may appear in any order. In other words, we have a binary string of length 13 which has 9 zeros in it, and the number of such strings is exactly $\binom{13}{9}$.
By the way -- this is exactly the "stars and bars" link provided in the comment, with 0s in place of bars and $S$ in place of stars.
