A361358 -id:A361358 - cp's OEIS frontend

A361356 Number of noncrossing caterpillars with n edges.

1, 1, 3, 12, 55, 273, 1372, 6824, 33489, 162405, 779801, 3713436, 17560803, 82553597, 386105790, 1797803248, 8338313697, 38539754649, 177581276639, 815982230060, 3740047627071, 17103604731961, 78054858200448, 355541644914072, 1616688603539025

Offset: 0

Andrew Howroyd, Mar 09 2023

A noncrossing caterpillar is a noncrossing tree that is a caterpillar tree (also called a caterpillar graph).

The number of nodes is n + 1. All trees up to 5 edges (or 6 nodes) are caterpillars.

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Caterpillar Graph.
Wikipedia, Caterpillar tree.
Index entries for linear recurrences with constant coefficients, signature (12,-52,104,-114,76,-32,8,-1).

Row sums of A361357.
Cf. A001764 (noncrossing trees), A005418 (unlabeled), A245012 (labeled).
Cf. A361358, A361359 (up to rotations), A361360 (up to rotations and reflections).

Vec((1 - 11*x + 43*x^2 - 76*x^3 + 77*x^4 - 37*x^5 + 6*x^6)/((1 - x)^2*(1 - 5*x + 3*x^2 - x^3)^2) + O(x^30))

a(n) = 12*a(n-1) - 52*a(n-2) + 104*a(n-3) - 114*a(n-4) + 76*a(n-5) - 32*a(n-6) + 8*a(n-7) - a(n-8) for n >= 8.
G.f.: (1 - 11*x + 43*x^2 - 76*x^3 + 77*x^4 - 37*x^5 + 6*x^6)/((1 - x)^2*(1 - 5*x + 3*x^2 - x^3)^2).
G.f.: 1 + x + x^2*(3 - 2*x + (4 - 3*x + x^2)*F(x) + (1 + 2*x)*F(x)^2)/(1 - x)^2 where F(x) = x*(2 - x)/(1 - 5*x + 3*x^2 - x^3).

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

Original entry on oeis.org

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

Andrew Howroyd, Mar 09 2023

The number of all noncrossing caterpillars with n edges is given by A361356.

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).

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

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)) }

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.

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

Original entry on oeis.org

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

Andrew Howroyd, Mar 10 2023

The number of all noncrossing caterpillars with n edges is given by A361356.

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).

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

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)) }

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.

cp's OEIS Frontend

A361356 Number of noncrossing caterpillars with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula