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

1, 2, 4, 8, 12, 16, 20, 25, 33, 49, 77, 121, 181, 258, 356, 488, 680, 976, 1432, 2113, 3089, 4449, 6329, 8961, 12729, 18226, 26292, 38056, 55012, 79200, 113548, 162425, 232401, 333201, 478853, 689177, 991949, 1426322, 2048244, 2938696, 4215552, 6049984, 8688816

Offset: 0

Author

Michael A. Allen, Sep 21 2024

Keywords

• nonn
• easy

Examples

			For n = 6, the 20 subsets are {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {2,4}, {3,4}, {2,3,4}, {5}, {3,5}, {4,5}, {3,4,5}, {6}, {4,6}, {5,6}, {4,5,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,0,0,0,1,1,2).
• Index entries for subsets of {1,..,n} with disallowed differences

Crossrefs

Column k=28 of A376033.

Programs

Mathematica

CoefficientList[Series[(1 + x + 2*x^2 + 4*x^3 + 4*x^4 + 4*x^5 + 3*x^6 + 2*x^7)/(1 - x - x^6 - x^7 - 2*x^8),{x,0,40}],x]
LinearRecurrence[{1, 0, 0, 0, 0, 1, 1, 2}, {1, 2, 4, 8, 12, 16, 20, 25}, 41]

Formula

a(n) = a(n-1) + a(n-6) + a(n-7) + 2*a(n-8) for n >= 8.

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