A361360 Number of nonequivalent noncrossing caterpillars with n edges up to rotation and relection.

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

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

Cf. A296533 (noncrossing trees), A361356, A361358, A361359 (up to rotation only).

Sequence in context: A197959 A197550 A289605 * A296533 A321719 A309619

Adjacent sequences: A361357 A361358 A361359 * A361361 A361362 A361363

Keyword

nonn,easy

Author

Andrew Howroyd, Mar 10 2023

Status

approved