login
A375980
Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, or 5.
1
1, 2, 3, 4, 6, 9, 12, 17, 25, 35, 49, 71, 101, 142, 203, 290, 410, 583, 832, 1181, 1677, 2389, 3397, 4825, 6865, 9766, 13879, 19736, 28074, 39913, 56748, 80709, 114765, 163175, 232045, 329975, 469189, 667178, 948743, 1349062, 1918310, 2727839, 3878912, 5515657
OFFSET
0,2
FORMULA
a(n) = a(n-1) + a(n-3) - a(n-5) + a(n-6) for n >= 6.
G.f.: (1 + x)*(1 + x^2 - x^3 + x^4)/(1 - x - x^3 + x^5 - x^6).
EXAMPLE
For n = 6, the 12 subsets are {}, {1}, {2}, {3}, {4}, {1,4}, {5}, {1,5}, {2,5}, {6}, {2,6}, {3,6}.
MATHEMATICA
CoefficientList[Series[(1 + x + x^2 + x^5)/(1 - x - x^3 + x^5 - x^6), {x, 0, 42}], x]
LinearRecurrence[{1, 0, 1, 0, -1, 1}, {1, 2, 3, 4, 6, 9}, 43]
CROSSREFS
See A375981 for other sequences related to restricted combinations.
Column k=19 of A376033.
Sequence in context: A064174 A062121 A094995 * A018591 A309591 A018669
KEYWORD
easy,nonn
AUTHOR
Michael A. Allen, Sep 21 2024
STATUS
approved