Origin. Yesterday I posted a somewhat similar question asking about the number of subsets of $\{1,2,…,n\}$ which do not contain three consecutive integers. That one was solved completely, and I have had a fairly well understanding. However, I have been intrigued to count by brutal force. So here I am: picking $n=10$, I am now stuck at the cases for the numbers of $6,5,4$-element subsets.
My attempt. I was thinking about the $6$-element case. My strategy was through coloring each of the ten integers with either yellow or red, and restricting that no three consecutive yellow's are allowed, and for each legitimate coloring I collected those yellow's into a satisfying subset. For the $7$-element case, the only four ways for distributing the three red's are $(3,6,9),(3,6,8),(3,5,8),(2,5,8)$. For the $6$-element case, I was pondering how to step from the $7$-element case by swapping a yellow with a red; excluding a red, I know there are $10$ ways, but I have no idea how to add back the red without over-counting. Any idea or hint would be appreciated. Thank you!
Remark. Thanks to the hints of lulu and Taussig, I have solved my question completely through two distinct counting approaches for which I have posted two answers accordingly. Personally, I feel that the recursion method is more algorithmic and logically concise, while the Inclusion-Exclusion Principle way provides somewhat quicker computation once I get the core idea. In terms of writing a computer program, I think that the recursion approach would definitely nail it. Nevertheless, as an enthusiastic maths student, the Inclusion-Exclusion Principle approach is definitely worth a go.
Last, though this problem has been resolved, any new approach or idea is always welcome!
Best Answer
Thanks to Taussig's hint for using the Inclusion-Exclusion Principle. I have tried it by myself. I am posting this approach as another answer for future reference.
Let $a_{i,j}$ denote the number of $i$-element subsets of $\{1,2,...,j\}$, where each of such subsets does not contain three consecutive integers.
Let $E_{m,n}$ denote the event to involve $n$ consecutive integers starting from $m$. For example, $E_{1,3}$ represents the event to have integers $1,2,3$.
Let $N(E_{m,n})$ denote the number of such subsets that satisfy $E_{m,n}$.
Note. $E_{m,n}$ changes meaning when the corresponding $a_{i,j}$ changes.
Okay. Now let us do the counting!
$=\binom {10}{4}-(N(E_{1,3})+N(E_{2,3})\cdot\cdot\cdot+N(E_{8,3}))+(N(E_{1,3}\cap E_{2,3})+N(E_{2,3}\cap E_{3,3})+\cdot\cdot\cdot+N(E_{7,3}\cap E_{8,3}))$
$=210-7\times8+1\times7$
$=161$
$=\binom {10}{5}-(N(E_{1,3})+N(E_{2,3})\cdot\cdot\cdot+N(E_{8,3}))+(N(E_{1,3}\cap E_{2,3})+N(E_{2,3}\cap E_{3,3})+\cdot\cdot\cdot+N(E_{7,3}\cap E_{8,3}))+(N(E_{1,3}\cap E_{3,3})+N(E_{2,3}\cap E_{4,3})+\cdot\cdot\cdot+N(E_{6,3}\cap E_{8,3}))-(N(E_{1,3}\cap E_{2,3}\cap E_{3,3})+N(E_{2,3}\cap E_{3,3}\cap E_{4,3})+\cdot\cdot\cdot+N(E_{6,3}\cap E_{7,3}\cap E_{8,3}))$
$=252-\binom {7}{2}\times8+7\times6+6-6$
$=126$