# Why does $\binom{n+k-1}{k-1}$ count the number of sorted sets?

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 ;)

• You might want to check out 'stars and bars'. – StubbornAtom Sep 11 '16 at 17:57
• thanks, together with Brians answer it helped alot. – Christian Eriksson Sep 11 '16 at 20:11

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.

• Huge thanks Brian! I follow everything except, perhaps, this sentence: "The bars can be any $k−1$ of the $n+k−1$ symbols." What do we mean by this? I'm thinking that it means the $k-1$ bars can have any position within the $n+k-1$ symbols. Is this correct: lets say we have $1$ to $5$ to choose from, so $k=5$, and we have $n=3$ elements in the tuple. Then we need to place $k-1=4$ bars in some arrangement. Since we can have $n+k-1=7$ possible position we are wondering how many ways can we place $4$ bars in $7$ position which can be counted with $\binom{7}{4}$ – Christian Eriksson Sep 11 '16 at 20:08
• @Christian: You’re welcome! Yes, your understanding is correct. There are altogether $n+k-1$ positions for the symbols to occupy, and any $k-1$ of them can be occupied by the bars. – Brian M. Scott Sep 11 '16 at 20:11