OFFSET
0,4
COMMENTS
The number of all noncrossing caterpillars with n edges is given by A361356.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (5,4,-34,7,63,-30,-46,31,13,-14,0,3,-1).
FORMULA
G.f.: (1 - 4*x - 8*x^2 + 28*x^3 + 15*x^4 - 55*x^5 - 2*x^6 + 46*x^7 - 11*x^8 - 19*x^9 + 10*x^10 + 2*x^11 - 2*x^12)/((1 - x)^2*(1 + x)^2*(1 - 5*x + 3*x^2 - x^3)*(1 - 5*x^2 + 3*x^4 - x^6)).
a(n) = 5*a(n-1) + 4*a(n-2) - 34*a(n-3) + 7*a(n-4) + 63*a(n-5) - 30*a(n-6) - 46*a(n-7) + 31*a(n-8) + 13*a(n-9) - 14*a(n-10) + 3*a(n-12) - a(n-13) for n >= 13.
PROG
(PARI)
G(x)={ my(f = x*(2 - x)/(1 - 5*x + 3*x^2 - x^3), g = 1 + x + x^2*(3 - 2*x + (4 - 3*x + x^2)*f + (1 + 2*x)*f^2)/(1 - x)^2); (intformal(g) - 3)/x/2 + x*subst((3 + 2*x*(3-x)*f)/(1-x)^2, x, x^2)/4 + subst(1/(1-x) + x*f/(1-x), x, x^2)/2}
{ Vec(G(x) + O(x^30)) }
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Mar 10 2023
STATUS
approved