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

Author

Andrew Howroyd, Mar 09 2023

Keywords

• nonn
• easy

Comments

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.

Links

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

Crossrefs

Row sums of A361357.

Cf. A001764 (noncrossing trees), A005418 (unlabeled), A245012 (labeled).

Cf. A361358, A361359 (up to rotations), A361360 (up to rotations and reflections).

Programs

PARI

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

Formula

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