login
Number of noncrossing caterpillars with n edges.
5

%I #13 Mar 12 2023 14:18:14

%S 1,1,3,12,55,273,1372,6824,33489,162405,779801,3713436,17560803,

%T 82553597,386105790,1797803248,8338313697,38539754649,177581276639,

%U 815982230060,3740047627071,17103604731961,78054858200448,355541644914072,1616688603539025

%N Number of noncrossing caterpillars with n edges.

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

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

%H Andrew Howroyd, <a href="/A361356/b361356.txt">Table of n, a(n) for n = 0..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CaterpillarGraph.html">Caterpillar Graph</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Caterpillar_tree">Caterpillar tree</a>.

%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (12,-52,104,-114,76,-32,8,-1).

%F 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.

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

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

%o (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))

%Y Row sums of A361357.

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

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

%K nonn,easy

%O 0,3

%A _Andrew Howroyd_, Mar 09 2023