A375186 - OEIS

A375186

Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 4, or 5.

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

(list; graph; refs; listen; history; text; internal format)

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, ...

LINKS

Table of n, a(n) for n=0..42.

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1).

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

Adjacent sequences: A375183 A375184 A375185 * A375187 A375188 A375189

KEYWORD

easy,nonn,changed

AUTHOR

Michael A. Allen, Aug 02 2024

STATUS

approved