number of strictly increasing sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$?

Question

What is the number of strictly incremental sequences of length $K$ with elements from $\{1, 2,\cdots,N\}$ ?

Is there any exact value? How about approximations?

Answer 1

Take all subsets of size $K$ from $\{1,2,\ldots,N\}$. There are ${N \choose K}$ such subsets. Each such subset can be arranged to form exactly one strictly increasing sequence. Therefore, there are ${N \choose K}$ such sequences.

Answer 2

OK, so if we can't use the same number twice, I think there is a simple approach : just take $K$ elements from the set. Starting from here, sort the $K$ elements : you have a strictly incremental sequence. Furthermore, a strictly incremental sequence may only come from one given set. So there is a bijection between the number of strictly incremental sequences, and the number of sets.

So the answer is $\frac{N!}{K!*(N-K)!} = $ $N \choose K$.