login
A374737
Number of subsets of {1,2,...,n} such that no two elements differ by 1 or 5.
2
1, 2, 3, 5, 8, 13, 18, 28, 41, 62, 91, 141, 208, 317, 473, 719, 1069, 1623, 2425, 3666, 5487, 8295, 12424, 18751, 28130, 42416, 63657, 95944, 144083, 217023, 326060, 490985, 737849, 1110753, 1669685, 2512993, 3778125, 5685594, 8549027, 12863637, 19344100, 29104549
OFFSET
0,2
COMMENTS
a(n) is the number of permutations of 0..n with each element moved by -1 to 1 places and every 5 consecutive elements having their maximum within 5 of their minimum.
FORMULA
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) + a(n-7) + a(n-8) + a(n-10) for n >= 10.
G.f.: (1 + 2*x + 2*x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 3*x^6 + 2*x^7 + x^8 + x^9)/(1 - x^2 - x^3 - x^4 + x^5 - x^6 - x^7 - x^8 - x^10).
EXAMPLE
For n = 6, the 18 subsets are {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6}, {1,3,5}, {2,4,6}.
MATHEMATICA
CoefficientList[Series[(1 + 2*x + 2*x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 3*x^6 + 2*x^7 + x^8 + x^9)/(1 - x^2 - x^3 - x^4 + x^5 - x^6 - x^7 - x^8 - x^10), {x, 0, 41}], x]
CROSSREFS
See A375981 for other sequences related to restricted combinations.
Column k=17 of A376033.
Sequence in context: A144117 A081612 A343484 * A301754 A120761 A355513
KEYWORD
easy,nonn
AUTHOR
Michael A. Allen, Jul 18 2024
STATUS
approved