VOOZH about

URL: https://oeis.org/A102593

⇱ A102593 - OEIS

login
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.
3
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,7
COMMENTS
Row n has n+1 terms. Row sums yield the ternary numbers (A001764). T(n,0)=A102893(n).
LINKS
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) = (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).
EXAMPLE
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;
...
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 *)
PROG
(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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Jan 22 2005
STATUS
approved