A101371 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges and k leaves at level 1.

1, 0, 1, 2, 0, 1, 7, 4, 0, 1, 34, 14, 6, 0, 1, 171, 72, 21, 8, 0, 1, 905, 370, 114, 28, 10, 0, 1, 4952, 1995, 597, 160, 35, 12, 0, 1, 27802, 11064, 3278, 852, 210, 42, 14, 0, 1, 159254, 62774, 18420, 4762, 1135, 264, 49, 16, 0, 1, 927081, 362614, 105618, 27104, 6455, 1446, 322, 56, 18, 0, 1

Offset

0,4

Comments

Row n has n+1 terms. Row sums give A001764. Column k=0 gives A023053.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

P. Flajolet and M. Noy, Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229, 1999.

M. Noy, Enumeration of noncrossing trees on a circle, Discrete Math., 180, 301-313, 1998.

Formula

T(n, k) = Sum_{i=0..n-k} (-1)^i*((k+i+1)/(2n-k-i+1)) binomial(k+i, i) binomial(3n-2k-2i, n-k-i) for 0 <= k <= n.

G.f.: g/(1+z*g-t*z*g), where g = 1+z*g^3.

Example

Triangle begins:
    1;
    0,  1;
    2,  0,  1;
    7,  4,  0, 1;
   34, 14,  6, 0, 1;
  171, 72, 21, 8, 0, 1;
  ...

Maple

T:=proc(n, k) if k<=n then sum((-1)^i*(k+i+1)*binomial(k+i, i)*binomial(3*n-2*k-2*i, n-k-i)/(2*n-k-i+1), i=0..n-k) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Mathematica

t[n_, k_] := Sum[(-1)^i*(k + i + 1)/(2n - k - i + 1)*Binomial[k + i, i]* Binomial[3n - 2k - 2i, n - k - i], {i, 0, n - k}]; Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 21 2013, after Maple *)

Prog

(PARI) T(n, k) = sum(i=0, n-k, (-1)^i*(k+i+1)*binomial(k+i, i)*binomial(3*n-2*k-2*i, n-k-i)/(2*n-k-i+1)); \\ Andrew Howroyd, Nov 06 2017

Crossrefs

Cf. A001764, A023053.

Sequence in context: A362787 A341200 A300130 * A325754 A154974 A342981

Adjacent sequences: A101368 A101369 A101370 * A101372 A101373 A101374

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 14 2005

Status

approved