Answer to Question #254767 in Discrete Mathematics for Vishnu Kumar

Question

Determine the number of subsets of size k of the set {1, 2, . . . , n} which do not contain consecutive integers. For instance, when n = 4 and k = 2, there are 3 such subsets, namely {1, 3}, {1, 4} and {2, 4}. 

Answer 1

Note all valid subsets one-to-one correspond to all permutations of $N−k$ unlabelled white balls and k unlabelled black balls where no two black balls are adjacent. Also, each such permutation can be obtained by inserting the k black balls into the gaps between two white balls (including the leftmost and the rightmost positions) such that no two black balls are inserted into the same gap.

There are $N−k+1$ gaps, so there are $\binom{N-k=1}{k}$  ways to insert black balls.

The answer to your question is also $\binom{N-k+1}{k}$