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

1, 2, 4, 6, 8, 11, 14, 18, 25, 37, 53, 75, 105, 145, 198, 274, 383, 537, 752, 1053, 1468, 2041, 2838, 3954, 5513, 7693, 10737, 14979, 20880, 29100, 40558, 56538, 78828, 109926, 153289, 213736, 297991, 415448, 579198, 807519, 1125889, 1569813, 2188752

Offset

0,2

Comments

a(n) is the number of compositions of n+5 into parts 1, 6, 7, 10, 14, 18, 22, ...

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

Formula

a(n) = a(n-1) + a(n-4) - a(n-5) + a(n-6) + a(n-7) - a(n-11) for n >= 11.

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

Example

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

Mathematica

CoefficientList[Series[(1 + x + 2*x^2 + 2*x^3 + x^4 + 2*x^5 - x^7 - x^8 - x^9 - x^10)/(1 - x - x^4 + x^5 - x^6 - x^7 + x^11), {x, 0, 42}], x]
LinearRecurrence[{1, 0, 0, 1, -1, 1, 1, 0, 0, 0, -1}, {1, 2, 4, 6, 8, 11, 14, 18, 25, 37, 53}, 42]

Crossrefs

See A375981 for other sequences related to restricted combinations.

Sequence in context: A321531 A194224 A194252 * A205727 A213609 A374263

Adjacent sequences: A375979 A375980 A375981 * A375983 A375984 A375985

Keyword

easy,nonn

Author

Michael A. Allen, Sep 04 2024

Status

approved