A204387 Triangle read by rows: T(n,k) is number of noncrossing trees with k edges and path-length n, n >= 1, 1 <= k <= n.

1, 0, 1, 0, 2, 1, 0, 0, 4, 1, 0, 0, 3, 6, 1, 0, 0, 4, 10, 8, 1, 0, 0, 0, 12, 21, 10, 1, 0, 0, 0, 12, 32, 36, 12, 1, 0, 0, 0, 6, 45, 72, 55, 14, 1, 0, 0, 0, 8, 36, 119, 140, 78, 16, 1, 0, 0, 0, 0, 46, 144, 270, 244, 105, 18, 1, 0, 0, 0, 0, 32, 164, 416, 550, 392, 136, 20, 1

Offset: 1

Author

N. J. A. Sloane, Jan 17 2012

Keywords

• nonn
• tabl

Comments

The number of nodes is k + 1. The path-length is the sum of the distances of all nodes from the root node. - Andrew Howroyd, Nov 19 2024

Examples

			Triangle begins:
1
0 1
0 2 1
0 0 4 1
0 0 3 6 1
0 0 4 10 8 1
0 0 0 12 21 10 1
0 0 0 12 32 36 12 1
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
• E. Deutsch and M. Noy, Statistics on non-crossing trees, Discrete Math., 254 (2002), 75-87 (see Th. 6).

Crossrefs

Row sums are A132332.

Column sums are A001764.

Cf. A062236.

Programs

PARI

T(n)={my(g=1+O(x)); for(i=1, n, g=1/(1 - x*y*subst(g,y,x*y)^2)); [Vecrev(p/y) | p<-Vec(g-1)]}
{my(A=T(10)); for(i=1, #A, print(A[i]))} \\ Andrew Howroyd, Nov 19 2024

Formula

From Andrew Howroyd, Nov 19 2024: (Start)

G.f.: A(x,y) satisfies A(x,y) = 1/(1 - x*y*A(x,x*y)^2).

T(k*(k+1)/2, k) = 2^(k-1).

T(n,k) = 0 for n > k*(k+1)/2.

Sum_{n>=1} n*T(n,k) = A062236(k). (End)

Extensions

a(34) corrected and a(42) onwards from Andrew Howroyd, Nov 19 2024