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

1, 2, 3, 5, 7, 9, 11, 14, 18, 25, 35, 49, 67, 90, 119, 158, 211, 285, 387, 526, 712, 960, 1290, 1733, 2331, 3142, 4241, 5727, 7729, 10422, 14043, 18918, 25490, 34359, 46329, 62478, 84250, 113590, 153123, 206400, 278219, 375056, 505635, 681703, 919076, 1239066

Offset: 0

Author

Michael A. Allen, Sep 21 2024

Keywords

• easy
• nonn

Comments

a(n) is the number of compositions of n+5 into parts 1, 6, and 8.

Examples

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

Crossrefs

Column k=29 of A376033.

Programs

Mathematica

CoefficientList[Series[(1 + x + x^2 + 2*x^3 + 2*x^4 + 2*x^5 + x^6 + x^7)/(1 - x - x^6 - x^8),{x,0,43}],x]
LinearRecurrence[{1, 0, 0, 0, 0, 1, 0, 1}, {1, 2, 3, 5, 7, 9, 11, 14}, 44]

Formula

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

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