OFFSET
0,2
LINKS
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,2,3,-1,-2,-3).
FORMULA
a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) + a(n-7) + 2*a(n-8) + 3*a(n-9) - a(n-10) - 2*a(n-11) - 3*a(n-12) for n >= 12.
G.f.: (1 + x + 2*x^2 + 3*x^3 + 7*x^4 + 6*x^5 + 3*x^6 - x^7 - 3*x^8 - 6*x^9 - 5*x^10 - 3*x^11)/(1 - x - x^3 + x^4 - x^6 - x^7 - 2*x^8 - 3*x^9 + x^10 + 2*x^11 + 3*x^12).
EXAMPLE
For n = 6, the 32 subsets are {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}, {5}, {2,5}, {3,5}, {2,3,5}, {4,5}, {2,4,5}, {3,4,5}, {2,3,4,5}, {6}, {3,6}, {4,6}, {3,4,6}, {5,6}, {3,5,6}, {4,5,6}, {3,4,5,6}.
MATHEMATICA
CoefficientList[Series[(1 + x + 2*x^2 + 3*x^3 + 7*x^4 + 6*x^5 + 3*x^6 - x^7 - 3*x^8 - 6*x^9 - 5*x^10 - 3*x^11)/(1 - x - x^3 + x^4 - x^6 - x^7 - 2*x^8 - 3*x^9 + x^10 + 2*x^11 + 3*x^12), {x, 0, 38}], x]
LinearRecurrence[{1, 0, 1, -1, 0, 1, 1, 2, 3, -1, -2, -3}, {1, 2, 4, 8, 16, 24, 32, 42, 55, 76, 118, 192}, 39]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Michael A. Allen, Sep 20 2024
STATUS
approved