# How many ways to do n chose k such that the picks are non-decreasing?

Given n that represents the maximum value of all the numbers we can pick from such that

1 <= pick <= n


Given k that represents how many numbers we must pick.

I am interested in finding the number of combinations that will have a non-decreasing order.

For example with n = 10, k = 2 if we write it down we can observe:

Pick#1 Pick#2
10     10 (only possible value)
9      9 or 10 (same...)
8      8 -> 10
.      .
.      .
1      1 -> 10 (all values are possible)


And so we find that for k = 2 the number of such combinations will be n(n+1)/2 = 55.

The problem I am facing is that I cannot derive a general formula that would work for any k.

My best attempt:

If n = 10, k = 3:

If Pick#1 = 1, we get (n+1)/2 = 55 combinations possible.

If Pick#1 = 2, we get (n(n+1)/2) - n combinations.

If Pick#1 = 3, we get (n(n+1)/2) - n - (n - 1) combinations.

If Pick#1 = 4, we get (n(n+1)/2) - n - (n - 1) - (n - 2) combinations.

.....

Which can sum to give a total of:

n * (n(n+1)/2) - n(n+1)/2 = (n-1) * (n(n+1)/2) combinations.


I attempt to generalize by recognizing that this pattern will repeat and by writing:

((n-1)^k-2) * (n(n+1)/2) total combinations.


But this is wrong as my test case is that n = 93, k = 8 should equal: 186087894300.

Pick#1  Pick#2 Pick#3
1       10     10
9      9 or 10
8      8 -> 10
.      .
.      .
1      1 -> 10

2       10     10
9      9 or 10
8      8 -> 10
.      .
.      .
2      2 -> 10

3       10     10
9      9 or 10
8      8 -> 10
.      .
.      .
3      3 -> 10


Thanking you in advance for any help!

• If I understand correctly, you want to find the number of non-decreasing sequences of length $k$ using $n$ symbols (numbers)? Commented Aug 28, 2013 at 19:32
• @DanielFischer Exactly, also the numbers can repeat. And now that I think about it, I would also be curious as to the solution in the case of the numbers not allowed to repeat. Commented Aug 28, 2013 at 19:37

You want the number of non-decreasing $k$-tuples of integers chosen from the set $\{1,\ldots,n\}$. Let $\langle a_1,\ldots,a_k\rangle$ be such a $k$-tuple. Let $d_0=a_1-1$ and $d_k=n-a_k$, and for $i=1,\ldots,k-1$ let $d_i=a_{i+1}-a_i$. Note that the $(k+1)$-tuple $\langle d_0,\ldots,d_k\rangle$ is uniquely determined by $\langle a_1,\ldots,a_k\rangle$ and vice versa: from $\langle d_0,\ldots,d_k\rangle$ you can reconstruct $\langle a_1,\ldots,a_k\rangle$. What $(k+1)$-tuples $\langle d_0,\ldots,d_k\rangle$ are possible? Clearly each $d_i$ is a non-negative integer, and

$$\sum_{i=0}^kd_i=(a_1-1)+\sum_{k=1}^{k-1}(a_{i+1}-a_i)+(n-a_k)=n-1\;.$$

You can check that any $(k+1)$-tuple $\langle d_0,\ldots,d_k\rangle$ of non-negative integers summing to $n-1$ comes from a non-decreasing $k$-tuple $\langle a_1,\ldots,a_k\rangle$ whose terms are chosen from $\{1,\ldots,n\}$. Thus, there are exactly as many of your $k$-tuples as there are solutions in non-negative integers to the equation

$$x_0+x_1+\ldots+x_k=n-1\;.$$

This is a standard stars-and-bars problem whose solution is

$$\binom{(n-1)+(k+1)-1}{(k+1)-1}=\binom{n+k-1}k=\binom{n+k-1}{n-1}\;;$$

the linked article gives a reasonably clear derivation of this formula.

• Hello and thanks for your answer but C(93 + 8, 93) = 202095455100 != 186087894300. Commented Aug 28, 2013 at 19:42
• This problem is from a training set of programming problems available on topcoder and it has been solved successfully by other users before. Commented Aug 28, 2013 at 19:46
• @user2441988: Yes, I see the problem now: $d_0$ can’t be $0$, which introduces a slight distortion. I’ll fix it in a few minutes. Commented Aug 28, 2013 at 19:47
• Thanks again, I'm going to look at it more closely. Commented Aug 28, 2013 at 20:02
• I'm ashamed to say it took me all this time to figure out the answer to the same problem with no duplicates is simply C(n, k). Commented Aug 28, 2013 at 21:03