login
A375186
Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 4, or 5.
1
1, 2, 3, 4, 6, 8, 10, 14, 19, 25, 35, 48, 64, 88, 120, 161, 220, 300, 405, 552, 752, 1018, 1385, 1885, 2556, 3475, 4727, 6416, 8720, 11857, 16102, 21881, 29745, 40406, 54905, 74626, 101389, 137769, 187235, 254404, 345689, 469781, 638339
OFFSET
0,2
COMMENTS
a(n-4) for n>3 is the number of equivalence classes of binary words of length n for the subword 100110 (see A317669 for further explanation).
a(n) is the number of compositions of n+5 into parts 1, 6, 9, 12, 15, 18, ...
FORMULA
a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) for n>= 6.
G.f.: (1 + x + x^2 + x^4 + x^5)/(1 - x - x^3 + x^4 - x^6).
EXAMPLE
For n = 6, the 10 subsets are {}, {1}, {2}, {3}, {4}, {1,4}, {5}, {2,5}, {6}, {3,6}.
MATHEMATICA
CoefficientList[Series[(1 + x + x^2 + x^4 + x^5)/(1 - x - x^3 + x^4 - x^6), {x, 0, 42}], x]
LinearRecurrence[{1, 0, 1, -1, 0, 1}, {1, 2, 3, 4, 6, 8}, 42]
CROSSREFS
See A375981 for other sequences related to restricted combinations.
Column k=27 of A376033.
Sequence in context: A045476 A368381 A323360 * A297417 A343502 A238876
KEYWORD
easy,nonn
AUTHOR
Michael A. Allen, Aug 02 2024
STATUS
approved