Solution to Determine the number of subsets of size k of the set {1, 2, . . … - Sikademy
Author Image

Archangel Macsika

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?


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 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}

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-1311-qpid-1049