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

1, 2, 4, 6, 9, 15, 21, 29, 45, 69, 100, 152, 236, 349, 517, 789, 1185, 1757, 2653, 4014, 5992, 8986, 13573, 20363, 30485, 45901, 69041, 103481, 155468, 233908, 351104, 527033, 792405, 1190493, 1787129, 2685209, 4035261, 6059758, 9101828, 13676670, 20544125

Offset: 0

Author

Michael A. Allen, Sep 20 2024

Keywords

• nonn
• easy

Examples

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

Crossrefs

Column k=18 of A376033.

Programs

Mathematica

CoefficientList[Series[(1 + x + 2*x^2 + x^3 + x^4 + 3*x^5 + x^6 - x^7 - x^10)/(1 - x - x^3 + x^5 - x^6 - 2*x^7 + x^8 - x^10 + x^11),{x,0,39}],x]
LinearRecurrence[{1, 0, 1, 0, -1, 1, 2, -1, 0, 1, -1}, {1, 2, 4, 6, 9, 15, 21, 29, 45, 69, 100}, 39]

Formula

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

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