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
Examples
Triangle begins:
1;
0, 1;
2, 0, 1;
7, 4, 0, 1;
34, 14, 6, 0, 1;
171, 72, 21, 8, 0, 1;
...
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.
Programs
-
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 *) -
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
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.
Comments