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

1, 2, 4, 6, 9, 12, 15, 20, 28, 40, 59, 86, 121, 169, 235, 326, 458, 649, 919, 1301, 1837, 2582, 3627, 5101, 7179, 10118, 14272, 20120, 28349, 39930, 56221, 79165, 111509, 157091, 221325, 311830, 439291, 618791, 871621, 1227752, 1729447, 2436267, 3432010

Offset

0,2

Comments

a(n) is the number of compositions of n+5 into parts 1, 6, 7, 9, 12, 15, 18, 21, ...

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

Formula

a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-7) - a(n-10) for n >= 10.

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

Example

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

Mathematica

CoefficientList[Series[(1 + x + 2*x^2 + x^3 + 2*x^4 + x^5 - x^7 - x^8 - x^9)/(1 - x - x^3 + x^4 - x^6 - x^7 + x^10), {x, 0, 42}], x]
LinearRecurrence[{1, 0, 1, -1, 0, 1, 1, 0, 0, -1}, {1, 2, 4, 6, 9, 12, 15, 20, 28, 40}, 42]

Crossrefs

See A375981 for other sequences related to restricted combinations.

Sequence in context: A076271 A036441 A180107 * A135146 A256956 A257637

Adjacent sequences: A375980 A375981 A375982 * A375984 A375985 A375986

Keyword

easy,nonn

Author

Michael A. Allen, Sep 04 2024

Status

approved