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

1, 2, 4, 8, 12, 18, 24, 34, 47, 73, 111, 177, 267, 409, 600, 900, 1324, 2004, 2996, 4564, 6848, 10377, 15513, 23385, 34953, 52685, 78969, 119138, 178840, 269604, 404656, 609310, 914548, 1376530, 2067231, 3111457, 4674751, 7034897, 10570855, 15903377, 23898528

Offset

0,2

Links

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

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

Formula

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

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

Example

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

Mathematica

CoefficientList[Series[(1 + x + x^2 + 3*x^3 + x^4 + x^5 - x^6 - 3*x^7 - 4*x^8 - 3*x^9 - 2*x^10 - x^11)/(1 - x - x^2 + x^3 - x^4 + x^5 - x^6 - x^7 - x^8 + x^9 + x^10 + x^11 + x^12), {x, 0, 38}], x]
LinearRecurrence[{1, 1, -1, 1, -1, 1, 1, 1, -1, -1, -1, -1}, {1, 2, 4, 8, 12, 18, 24, 34, 47, 73, 111, 177}, 39]

Crossrefs

See A375981 for other sequences related to restricted combinations.

Column k=20 of A376033.

Sequence in context: A080476 A256885 A293495 * A330130 A053799 A343949

Adjacent sequences: A375975 A375976 A375977 * A375979 A375980 A375981

Keyword

easy,nonn

Author

Michael A. Allen, Sep 20 2024

Status

approved