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

1, 2, 3, 4, 6, 9, 12, 17, 25, 35, 49, 71, 101, 142, 203, 290, 410, 583, 832, 1181, 1677, 2389, 3397, 4825, 6865, 9766, 13879, 19736, 28074, 39913, 56748, 80709, 114765, 163175, 232045, 329975, 469189, 667178, 948743, 1349062, 1918310, 2727839, 3878912, 5515657

Offset: 0

Author

Michael A. Allen, Sep 21 2024

Keywords

• easy
• nonn

Examples

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

Links

• Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
• Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
• Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,-1,1).
• Index entries for subsets of {1,..,n} with disallowed differences

Crossrefs

Column k=19 of A376033.

Programs

Mathematica

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

Formula

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

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