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

Author

Michael A. Allen, Aug 02 2024

Keywords

• easy
• nonn

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

Examples

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

Links

• 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

Crossrefs

Column k=23 of A376033.

Programs

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]

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