# How many combinations of K ordered numbers from N numbers list

I have N numbers, 1-N (my N is 70). I need to know how many combinations of sequences of K numbers (K is 8 in my case) are possible, where the sequence is always increasing.

Examples:

1,6,23,45,51,59,60,68 is allowed

1,4,2,23,45,51,59,60 is not allowed

• The crucial question is how the values are sampled (with or withour replacement, what is the procedure of sampling etc.)? Obviously there is $N \choose k$ unordered combinations, but how the ordering of samples drawn is achieved?
– Tim
Feb 1, 2016 at 14:16

## 2 Answers

The answer is $\binom{N}{K} = N!/(K!(N-K)!)$.

A sequence is an ordered tuple whereas a combination is an unordered tuple. Obviously every sequence determines its combination (by forgetting the ordering). Every combination is determined by all the possible ways of reordering its components, but only one of those is a sequence. Consequently the distinct $K$-combinations of $N$ distinct numbers are in one-to-one correspondence with the (strictly) increasing sequences of those numbers.

I believe the answer is:

$\sum_{i=1}^{N-K-1}{N-i \choose {N-i-K+1} }$

Basically, i is the first number in the sequence, when i is 1, you have 7 more numbers to choose or N-1-8+1=N-8=72 numbers not to choose out of N-i=70-1=69 numbers left.

At i = N-K-1, you have no choice at all, hens ${N-i} \choose 0$ or 1

For N=70, K=8, I get 9.44 billion

• 9.440350920 billion is correct--but the general answer has a simpler form!
– whuber
Feb 2, 2016 at 0:33