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,5

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

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

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)

Example

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

Prog

(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

Crossrefs

Row sums are A132332.

Column sums are A001764.

Cf. A062236.

Sequence in context: A369195 A065719 A336087 * A110509 A113953 A319574

Adjacent sequences: A204384 A204385 A204386 * A204388 A204389 A204390

Keyword

nonn,tabl,changed

Author

N. J. A. Sloane, Jan 17 2012

Extensions

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

Status

approved