0
$\begingroup$

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

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

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – Christian Eriksson Sep 11 '16 at 20:08
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Sep 11 '16 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.