A361357 Triangle read by rows: T(n,k) is the number of noncrossing caterpillars with n edges and diameter k, 0 <= k <= n.

1, 0, 1, 0, 0, 3, 0, 0, 4, 8, 0, 0, 5, 30, 20, 0, 0, 6, 75, 144, 48, 0, 0, 7, 154, 595, 504, 112, 0, 0, 8, 280, 1848, 2896, 1536, 256, 0, 0, 9, 468, 4788, 12060, 11268, 4320, 576, 0, 0, 10, 735, 10920, 40700, 58760, 38480, 11520, 1280

Offset: 0

Author

Andrew Howroyd, Mar 09 2023

Keywords

• nonn
• tabl

Comments

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

The diameter of a tree is also the length of the longest path.

Examples

			Triangle begins:
  1;
  0, 1;
  0, 0,  3;
  0, 0,  4,   8;
  0, 0,  5,  30,    20;
  0, 0,  6,  75,   144,    48;
  0, 0,  7, 154,   595,   504,   112;
  0, 0,  8, 280,  1848,  2896,  1536,   256;
  0, 0,  9, 468,  4788, 12060, 11268,  4320,   576;
  0, 0, 10, 735, 10920, 40700, 58760, 38480, 11520, 1280;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
• Eric Weisstein's World of Mathematics, Caterpillar Graph.
• Wikipedia, Caterpillar tree.

Crossrefs

Row sums are A361356.

Main diagonal is A001792(n-1).

Programs

PARI

T(n) = {my(f=x*y*(2 - x)/(1 - (3 + 2*y)*x + 3*x^2 - x^3), g = 1 + x*y + (x*y)^2*((3 - 2*x) + (4 - 3*x + x^2)*f + (1 + 2*x)*f^2)/(1 - x)^2); [Vecrev(p) | p<-Vec(g + O(x*x^n))]}
{ my(A=T(9)); for(i=1, #A, print(A[i])) }

Formula

T(n,2) = n + 1 for n >= 2.

G.f.: A(x,y) = 1 + x*y + (x*y)^2*((3 - 2*x) + (4 - 3*x + x^2)*F(x,y) + (1 + 2*x)*F(x,y)^2)/(1 - x)^2 where F(x,y) = x*y*(2 - x)/(1 - (3 + 2*y)*x + 3*x^2 - x^3).