A361359 Number of nonequivalent noncrossing caterpillars with n edges up to rotation.

1, 1, 1, 4, 11, 49, 196, 868, 3721, 16306, 70891, 309739, 1350831, 5897934, 25740386, 112368153, 490489041, 2141121271, 9346382981, 40799215354, 178097506051, 777437032059, 3393689486976, 14814237183658, 64667544141561, 282288713218896, 1232255125682671

Offset: 0

Author

Andrew Howroyd, Mar 09 2023

Keywords

• nonn
• easy

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 (6,-3,-26,36,-2,-18,6,5,-4,1).

Crossrefs

Cf. A296532 (noncrossing trees), A361356, A361358, A361360 (up to rotation and reflection).

Programs

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 + x*subst((1 + 2*x*f)/(1-x)^2, x, x^2)/2 }
{ Vec(G(x) + O(x^30)) }

Formula

G.f.: (1 - 5*x - 2*x^2 + 27*x^3 - 20*x^4 - 13*x^5 + 23*x^6 - 5*x^7 - 6*x^8 + 3*x^9)/((1 - x)*(1 - 5*x + 3*x^2 - x^3)*(1 - 5*x^2 + 3*x^4 - x^6)).

a(n) = 6*a(n-1) - 3*a(n-2) - 26*a(n-3) + 36*a(n-4) - 2*a(n-5) - 18*a(n-6) + 6*a(n-7) + 5*a(n-8) - 4*a(n-9) + a(n-10) for n >= 10.