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}.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
Note all valid subsets one-to-one correspond to all permutations of 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 gaps, so there are ways to insert black balls.
The answer to your question is also