login
A361357
Triangle read by rows: T(n,k) is the number of noncrossing caterpillars with n edges and diameter k, 0 <= k <= n.
2
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,6
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.
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.
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).
EXAMPLE
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;
...
PROG
(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])) }
CROSSREFS
Row sums are A361356.
Main diagonal is A001792(n-1).
Sequence in context: A316801 A143044 A350789 * A305151 A127775 A210953
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Mar 09 2023
STATUS
approved