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.

Links

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

Naiomi Cameron and 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

Columns k=0..2 give A023053, A374835, A374836.

Row sums give A001764.

Cf. A065600.

Sequence in context: A341200 A300130 A378974 * A325754 A154974 A342981

Adjacent sequences: A101368 A101369 A101370 * A101372 A101373 A101374

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 14 2005

Status

approved