Permutations & Combinations
Subsets with no consecutive elements
nta_pyq_2025_apr
Grade 12
Question:
For n$\ge 2, let S denote the set of all subsets of {1, 2$$\ldots..., n} with no two consecutive numbers. For example n {1, 3, 5}$$\i_n$$S_{6}$$, but {1, 2, 4}$$\notin$ S. Then n ( S ) is equal to ________ 6 5
Step-by-Step Solution
Key Concept: Use the recurrence for subsets with no consecutive integers, equivalent to Fibonacci counting.
$A = {1$, 2, 3, 4, 5$\ldots... n}$(13)$No. of subsets having r elements such that no two are consecutive$is = n-r+1$Cr for$n = 5$, no. of ways = 6$$\cdotr Cr Subsets having no$element = 1$Subsets having exactly 1$element = C = 5$5 1 Subsets having exactly 2$element = C = 6$4 2 Subsets having exactly 3$element = C = 1$3 3$$\Rightarrow$$5 + 6 + 1 + 1 = 13$
Correct Answer: 13