I've seen a few questions as to how to count the number of possible sorted sets sets of $n$ elements from $k$ integers (where the $k$ integers are replenished after each choice). The answer is, as per this answer, $\binom{n+k-1}{k-1}$, however I struggle to understand why. I know the binomial coefficient and its use but in this iteration, where does the expressions (n+k-1) and (k-1) come from?
I'm a beginner in probability and statistics and have a bit of trouble with the combinatorics parts. I sort of understand the reasoning, I think, but I struggle with generalizing it can't easily put it into usable expressions.
My thinking goes like this:
Starting with the largest number $k$, there is only one combination that is sorted in the correct manner.
$\{k, k, ...k\}$
For the smaller numbers, $y<k$, they can fill the entire set up to any given point:
$\{y,x,x, ... x\}$, $\{y,y,...x\}$, $\{y,y,...y,...x\}$, $\{y,y,...y\}$
The sequences of $x$ where $y<x\leq k$ could then also be patterns of similar combinations where the we for example could have something like:
$\{y,y+1,y+1, ... y+2, ... k\}$
I can clearly see that there is a pattern here but I can't intuitively put it into an expression that would get me to the $\binom{n+k-1}{k-1}$ above.
Any input that can shed light on this would be very appreciated, hopefully in fairly simple terms, beginner, remember ;)
We might as well assume that the $k$ integers are the integers $1$ through $k$. Each sorted set is a non-decreasing $n$-tuple of these integers, so if we know how many copeis of each integer there are in one of them, we can reconstruct the $n$-tuple. For instance, if $n=6$, $k=3$, and I tell you that the $n$-tuple has two $1$s, one $2$, and three $3$s, you know that it must be $\langle 1,1,2,3,3,3\rangle$.
Each of these $n$-tuples can therefore be represented uniquely by a string of $n$ asterisks (‘stars’), representing the $n$ positions in the $n$-tuple, and $k-1$ dividers (‘bars’) separating the stars representing $1$s from those representing $2$s, the stars representing $2$s from those representing $3$s, and so on. The $6$-tuple $\langle 1,1,2,3,3,3\rangle$ that I used as an example in the first paragraph would be represented by this string:
$$**\,|*\,|**\,*$$
If $n=7$, $k=4$, and our $7$-tuple is $\langle 1,1,1,3,3,3,3\rangle$, with three $1$s, no $2$s, four $3$s, and no $4$s, the associated string of stars and bars is this one:
$$***\,|\,|****\,|$$
There is a unique string of $n$ stars and $k-1$ bars associated in this way with each non-decreasing $n$-tuple of integers from $\{1,2,\ldots,k\}$, and each string of $n$ stars and $k-1$ bars corresponds to a unique non-decreasing $n$-tuple. For instance, the string
$$|**\,|\,|***\,|\,*$$
of $6$ stars and $4$ bars divides the stars into blocks of lengths $0,2,0,3$, and $1$ and therefore corresponds to the non-decreasing $6$-tuple $\langle 2,2,4,4,4,5\rangle$ of integers from the set $\{1,2,3,4,5\}$. There are therefore exactly as many of these non-decreasing $n$-tuples as there are strings of $n$ stars and $k-1$ bars.
To count these strings, we notice that they are precisely the strings of length $n+k-1$ that contain $n$ stars and $k-1$ bars. The bars can be any $k-1$ of the $n+k-1$ symbols. There are $\binom{n+k-1}{k-1}$ ways to choose $k-1$ things from a set of $n+k-1$ things, so there are $\binom{n+k-1}{k-1}$ possible placements of the bars within the string and therefore $\binom{n+k-1}{k-1}$ possible strings. Thus, there are also $\binom{n+k-1}{k-1}$ non-decreasing $n$-tuples that can be formed using elements of the set $\{1,2,\ldots,k\}$.
See also the Wikipedia articles on counting multisets and on stars and bars calculations.