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

1, 2, 3, 4, 5, 7, 9, 12, 16, 22, 29, 39, 52, 70, 93, 125, 167, 224, 299, 401, 536, 718, 960, 1286, 1720, 2303, 3081, 4125, 5519, 7388, 9886, 13233, 17708, 23702, 31719, 42454, 56815, 76042, 101767, 136204, 182284, 243965, 326505, 436984, 584831, 782716

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 100010 (see A317669 for further explanation).

a(n) is the number of compositions of n+5 into parts 1, 6, 10, 14, 18, 22, ...

Links

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

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

Index entries for subsets of {1,..,n} with disallowed differences

Formula

a(n) = a(n-1) + a(n-4) - a(n-5) + a(n-6) for n >= 6.

G.f.: (1 + x + x^2 + x^3 + x^5)/(1 - x - x^4 + x^5 - x^6).

Example

For n = 6, the 9 subsets are {}, {1}, {2}, {3}, {4}, {5}, {1,5}, {6}, {2,6}.

Mathematica

CoefficientList[Series[(1 + x + x^2 + x^3 + x^5)/(1 - x - x^4 + x^5 - x^6), {x, 0, 45}], x]
LinearRecurrence[{1, 0, 0, 1, -1, 1}, {1, 2, 3, 4, 5, 7}, 45]

Crossrefs

Column k=23 of A376033.

Sequence in context: A241336 A233522 A112639 * A290137 A336351 A241818

Adjacent sequences: A375182 A375183 A375184 * A375186 A375187 A375188

Keyword

easy,nonn

Author

Michael A. Allen, Aug 02 2024

Status

approved