How many subsets of $\{1,2,...,n\}$ have no $3$ consecutive numbers ?

My solution:

Inspired by How many subsets contain no consecutive elements? I decided to write recurrence: Let be set with numbers from $1$ to $n$ and let $A$ - subset of given set $$ a_n = \underbrace{a_{n-1}}_{n \notin A} + \underbrace{a_{n-2}}_{n \in A , n-1 \notin A} + \underbrace{a_{n-3}}_{n \in A, n-1 \in A, n-2 \notin A} $$

After examining corner cases I use iverson bracket to write full recurrence: $$ a_n = a_{n-1}+ a_{n-2} + a_{n-3} + [n=0] + [n=1] + [n=2]$$ After multiplying by $x^n$ and summing by all $n$ I got generating function: $$A(x) = x A(x) + x^2 A(x) + x^3 A(x) +1+ x + x^2 $$ $$A(x) = \frac{1+x+x^2}{1-x-x^2-x^3} $$ But how to solve this generating function to get coefficient with $x^n$?

  • $\begingroup$ The characteristic polynomial for the recursion is $x^3-x^2-x-1$ and that hasn't got very pleasant roots, so there might not be a terribly good looking solution. $\endgroup$ – lulu Aug 24 at 20:58
  • $\begingroup$ @lulu Before posting I also checked in mathematica so I am not sure if my approach is correct so decided to share that to forum with my explanation, maybe there is logical mistake there $\endgroup$ – Tester1998 Aug 24 at 20:59
  • $\begingroup$ Oh, I trusted your recursion. But it looks correct...is there any reason you expected a pleasant solution? $\endgroup$ – lulu Aug 24 at 21:00
  • $\begingroup$ This exercise comes from old exam, per task is about ~30 minutes so I wonder if there exists anything pleasant but I have doubts too... $\endgroup$ – Tester1998 Aug 24 at 21:03
  • $\begingroup$ Not sure your initial conditions are correct. You seem to have $a_1=1, a_2=2$ but that's not correct. None of the $4$ subsets of $\{1,2\}$ contain $3$ consecutive terms $\endgroup$ – lulu Aug 24 at 21:03

To summarize the discussion in the comments:

The recursion: $$a_n=a_{n-1}+a_{n-2}+a_{n-3}\quad a_1=2\quad a_2=4 \quad a_3=7$$

has characteristic polynomial $$x^3-x^2-x-1$$ which doesn't have particularly pleasant roots, which means that there isn't a simple closed formula for the results. The sequence $$\{a_n\}=\{2,4,7,13, 24, 44, 81, \cdots \}$$ is part of A000073 in oeis.org and that link contains a lot of information on the sequence, though of course it does not present a simple closed formula. Note that the characterization given there as the number of binary sequences of length $n$ for which the string $000$ does not appear is entirely equivalent the one given by the OP here, as each string corresponds to a subset (where a $1$ indicates that the entry is absent and a $0$ indicates that it is present).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.