OFFSET
1,4
COMMENTS
These partitions are qualified as 3-bounded and anchored. The number of 2-bounded anchored partitions of [1..n] is A000930(n). - Michel Marcus, Aug 13 2018
LINKS
G. C. Greubel, Table of n, a(n) for n = 1..1000 (terms 1..250 from Andrew Woods).
Maria M. Gillespie, Kenneth G. Monks, and Kenneth M. Monks, Enumerating Anchored Permutations with Bounded Gaps, arXiv:1808.03573 [math.CO], 2018. Also Discrete Math.,343 (2020), #111957. (Proves the formulas and conjectures.)
Index entries for linear recurrences with constant coefficients, signature (2,-1,2,1,1,0,-1,-1).
FORMULA
Let a(1)=1, g(1)=h(1)=0. For all n<1, let a(n)=g(n)=h(n)=0. Then:
a(n) = a(n-1) + g(n-1) + h(n-1),
g(n) = a(n-2) + a(n-3) + a(n-4) - a(n-6) + g(n-2) + g(n-4) + h(n-2),
h(n) = 2*a(n-3) + 2*a(n-4) + a(n-5) - a(n-7) + g(n-3) + g(n-5) + h(n-3).
Alternatively, let a(1)=1, a(n)=0 for n<1. Let b(1)=1, b(2)=0, b(3)=1, b(4)=3, b(5)=4, b(6)=5, b(7)=7, b(8)=10, and b(n)=b(n-1)+b(n-3) for n>8. Then:
a(n) = a(n-1)*b(1) + a(n-2)*b(2) + a(n-3)*b(3) + ... + a(1)*b(n-1).
From Colin Barker, Mar 07 2015 and Aug 13 2018: (Start)
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) + a(n-4) + a(n-5) - a(n-7) - a(n-8).
G.f.: x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8).
(End)
EXAMPLE
For n = 5, the a(5) = 6 solutions are 123456, 132456, 134256, 135246, 142356, and 143256.
MATHEMATICA
(1-x-x^3)/(1 -2x +x^2 -2x^3 -x^4-x^5+x^7+x^8) + O[x]^33 // CoefficientList[#, x]& (* Jean-François Alcover, Sep 23 2018, after Colin Barker *)
PROG
(PARI) Vec(x*(1 - x - x^3) / (1 - 2*x + x^2 - 2*x^3 - x^4 - x^5 + x^7 + x^8) + O(x^40)) \\ Colin Barker, Aug 13 2018
(Magma)
R<x>:=PowerSeriesRing(Integers(), 41);
Coefficients(R!( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) )); // G. C. Greubel, Sep 23 2024
(SageMath)
def A249665_list(prec):
P.<x> = PowerSeriesRing(ZZ, prec)
return P( x*(1-x-x^3)/(1-2*x+x^2-2*x^3-x^4-x^5+x^7+x^8) ).list()
a=A249665_list(41); a[1:] # G. C. Greubel, Sep 23 2024
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Andrew Woods, Mar 06 2015
STATUS
approved