login
A361360
Number of nonequivalent noncrossing caterpillars with n edges up to rotation and relection.
4
1, 1, 1, 3, 7, 28, 104, 448, 1886, 8212, 35556, 155124, 675897, 2950074, 12872294, 56188904, 245253691, 1070581703, 4673231521, 20399699635, 89048927767, 388718917440, 1696845506274, 7407120344070, 32333775400516, 141144364258374, 616127577376396
OFFSET
0,4
COMMENTS
The number of all noncrossing caterpillars with n edges is given by A361356.
LINKS
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
Cf. A296533 (noncrossing trees), A361356, A361358, A361359 (up to rotation only).
Sequence in context: A197959 A197550 A289605 * A296533 A321719 A309619
KEYWORD
nonn,easy
AUTHOR
Andrew Howroyd, Mar 10 2023
STATUS
approved