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

Links

Table of n, a(n) for n=0..42.

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

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

Example

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

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]

Crossrefs

See A375981 for other sequences related to restricted combinations.

Column k=28 of A376033.

Sequence in context: A160408 A221707 A186146 * A006638 A001212 A364769

Adjacent sequences: A375981 A375982 A375983 * A375985 A375986 A375987

Keyword

nonn,easy

Author

Michael A. Allen, Sep 21 2024

Status

approved