OFFSET
0,10
COMMENTS
Suppose A is a subset of {1,2,3,...,n} having the following property: if A includes an integer k, then A includes none of the integers k+2, k+3, k+4, k+5, k+6, k+7 or k+8. The number of subsets having this property is a(n+8).
Also, a(n+8) is the number of ways of painting an n-section board where if we paint the k-th section, we can't paint the (k+2)-th, (k+3)-th, (k+4)-th, (k+5)-th, (k+6)-th, (k+7)-th or (k+8)-th section.
LINKS
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,1,1).
FORMULA
a(n) = a(n-1) + a(n-9) + a(n-10) for n > 9.
G.f.: 1/(1 - x - x^9 - x^10).
EXAMPLE
G.f. = 1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + 2*x^9 + 4*x^10 + 6*x^11 + 8*x^12 + ...
For n=3 so {1,2,3}, the answer is a(3+8) = a(11) = 6. Here are the subsets: {},{1},{2},{3},{1,2},{2,3}.
For n=4, the number of ways of painting a 4-section board is a(4+8)=a(12)=8; here are the 8 possible sets indicating the painted sections: {},{1},{2},{3},{4},{1,2},{2,3},{3,4}.
MATHEMATICA
CoefficientList[Series[1/(1 - x - x^9 - x^10), {x, 0, 54}], x]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Onur Dik, Dec 18 2023
STATUS
approved