Given a set $X=\{1,2,\ldots,n\}$, how would I count the number of subsets containing only nonconsecutive elements?
For example:
$X=\{1,2,3,4\}$
implies 3 nonconsecutive subsets:
$\{1,3\}, \, \{2,4\}, \, \{1,4\}$
$\begingroup$
$\endgroup$
12
-
$\begingroup$ Doesn't $\{1,3,4\}$ contain $3,4$ which are consecutive? $\endgroup$– b00n heTCommented Jan 30, 2017 at 16:16
-
4$\begingroup$ As a hint, these subsets would either contain 1 or not. The subsets containing 1 would not contain 2, but anything from 3 on out would be allowed (as long as they're still not consecutive). The subsets not containing 1 could contain anything from 2 on out (again, as long as they're still not consecutive). This leads to a recurrence relation, which will likely be familiar to you. $\endgroup$– Rus MayCommented Jan 30, 2017 at 16:19
-
$\begingroup$ Why did you count $\{1,3,4\}$ but not $\{1,2,4\}$? $\endgroup$– MJDCommented Jan 30, 2017 at 16:24
-
$\begingroup$ @MJD Yes, a typo. Fixed. $\endgroup$– rocksNwavesCommented Jan 30, 2017 at 16:27
-
1$\begingroup$ Why did you count $\{1,2,4\}$ but not $\{1,3,4\}$? $\endgroup$– MJDCommented Jan 30, 2017 at 16:28
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
1
Let $f_1(x)$ be the number of ways to pick a subset of numbers from $\{1,2,\cdots,x-1,x\}$ such that the set does not contain 2 consecutive elements and must contain $x$. Let $f_2(x)$ be defined similarly but instead the subset must not contain $x$.
We can see that $f_1(x+1) = f_2(x)$ since if the subset contains $x+1$, it cannot contain $x$
Also, $f_2(x+1) = f_1(x) + f_2(x)$ as you can choose to add $x$ into the subset or not
We also know that $f_1(1) = 1$ and $f_2(1) = 1$
Simplifying:
$$ \begin{align} f_2(x+1) &= f_1(x) + f_2(x)\\ &= f_1(x-1) + 2f_2(x-1)\\ &= 2f_1(x-2) + 3f_2(x-2)\\ &= 3f_1(x-3) + 5f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_x + F_{x+1}\\ &= F_{x+2} \end{align} $$
$$ \begin{align} f_1(x+1) &= f_2(x)\\ &= f_1(x-1) + f_2(x-1)\\ &= f_1(x-2) + 2f_2(x-2)\\ &= 2f_1(x-3) + 3f_2(x-3)\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ & \space\space\space\space\space\space\space\space\space\space\space\space\space .\\ &= F_{x-1} + F_{x}\\ &= F_{x+1} \end{align} $$
where $F_x$ is the $x$th Fibonacci Number.
Thus $f_1(x) + f_2(x) = F_x + F_{x+1} = F_{x+2}$
