Let $S = \{ 1, 2,..., 12\}$, how many subsets of $S$ satisfy that the difference of any two number of the set is greater than $2$? Empty set and sets with only one element is counted in.
I am thinking of doing some partition and choosing numbers from each group. But it seems not to work. Any suggestion please? Thank you!
The answer is in the form: $$ 1 + \binom{12-0}{1} + \binom{12-2}{2} + \binom{12-4}{3}+\binom{12-6}{4} $$ Take $\binom{12-4}{3}$ as an example, we can think like this:
Assume we only have $8$ numbers, namely $1,2,3,4,5,6,7,8$, and we choose three numbers from them, such as $1,3,6$, we can always map it back to $1,3+2=5,6+2*2=10$, by adding the $2's$ back. This is one-to-one correspondence. Then we get the result in the end by adding them up.