Question

For a given k, 1 ≤ k ≤ n, how many vectors (x1, x2, . . . , xk) are there for which each xi is a positive integer such that 1 ≤ x1 < x2 < · · · < xk ≤ n?

Answer 1

To rephrase the problem, we need to choose k distinct integers between 1 and n and assign them to x_i's such that 1 ≤ x1 < x2 < · · · < xk ≤ n order is maintained. To do so, we can simply pick k numbers at random, and assign them to x_i's in increasing order.

Thus the problem is equivalent to choosing k distinct integers from n integers.

Hence the number of possible vectors are ⁿC_k = n!/k!/(n-k)!