3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tim
    Feb 1 '16 at 14:16
5
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 9.440350920 billion is correct--but the general answer has a simpler form! $\endgroup$
    – whuber
    Feb 2 '16 at 0:33

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.