A102593 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the maximum number of contiguous border edges starting from the root in counterclockwise direction is equal to k.
1, 0, 1, 1, 1, 1, 5, 4, 2, 1, 25, 18, 8, 3, 1, 130, 88, 37, 13, 4, 1, 700, 455, 185, 63, 19, 5, 1, 3876, 2448, 973, 325, 97, 26, 6, 1, 21945, 13566, 5304, 1748, 518, 140, 34, 7, 1, 126500, 76912, 29697, 9690, 2856, 775, 193, 43, 8, 1, 740025, 444015, 169763, 54967
Offset: 0
Examples
T(2,0) = T(2,1) = T(2,2) = 1 because in _\, /\ and /_ the maximum number of contiguous border edges starting from the root in counterclockwise direction is 0,1 and 2, respectively.
Triangle starts:
1;
0, 1;
1, 1, 1;
5, 4, 2, 1;
25, 18, 8, 3, 1;
130, 88, 37, 13, 4, 1;
700, 455, 185, 63, 19, 5, 1;
...
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1274
- 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 n=0 and k=0 then 1 elif n=1 and k=1 then 1 elif k<=n then (k+1)*binomial(3*n-2*k,n-k)/(2*n-k+1)-(k+2)*binomial(3*n-2*k-2,n-k-1)/(2*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_ /; n>1, k_] /; 0 <= k <= n := (k + 1) Binomial[3n - 2k, n - k]/(2n - k + 1) - (k + 2) Binomial[3n - 2k - 2, n - k - 1]/(2n - k); T[1, 1] = T[0, 0] = 1; T[, ] = 0; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 06 2018 *)
-
PARI
T(n,k) = {if(n==0, k==0, if(k<=n, (k+1)*binomial(3*n-2*k, n-k)/(2*n-k+1)-(k+2)*binomial(3*n-2*k-2, n-k-1)/(2*n-k)))} \\ Andrew Howroyd, Nov 06 2017
Formula
T(n, k) = (k+1)binomial(3n-2k, n-k)/(2n-k+1) - (k+2)binomial(3n-2k-2, n-k-1)/(2n-k) if n > 1, 0 <= k <= n; T(1, 1)=1; T(0, 0)=1; T(n, k)=0 if k > n.
G.f.: G(t, z) = g(1-zg)/(1-tzg), where g = 1+zg^3 is the g.f. for the ternary numbers (A001764).
Comments