A102595 Triangle read by rows: T(n,k) is the number of noncrossing trees with n edges in which the maximal number of contiguous border edges starting from the root in both directions is equal to k.

1, 0, 1, 0, 0, 3, 1, 4, 3, 4, 7, 20, 15, 8, 5, 42, 102, 72, 36, 15, 6, 245, 540, 366, 176, 70, 24, 7, 1428, 2950, 1944, 912, 355, 120, 35, 8, 8379, 16524, 10668, 4920, 1890, 636, 189, 48, 9, 49588, 94430, 60021, 27336, 10405, 3492, 1050, 280, 63, 10, 296010

Offset: 0

Author

Emeric Deutsch, Jan 22 2005

Keywords

• nonn
• tabl

Comments

Row sums yield the ternary numbers (A001764).

T(n,0) = A102594(n).

Examples

			T(2,0)=T(2,1)=0, T(2,2)=3 because in all the noncrossing trees _\, /\ and /_, the maximal number of contiguous border edges starting from the root in both directions is equal to 2.
Triangle starts:
   1;
   0,   1;
   0,   0,  3;
   1,   4,  3,  4;
   7,  20, 15,  8,  5;
  42, 102, 72, 36, 15, 6;
  ...
		

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.

Crossrefs

Cf. A001764, A102594.

Programs

Maple

G:=(g+z*g-t*z-2*z*g^2+t^2*(1-t)*z^3*g^2-2*t*(1-t)*z^2*g)/(1-t*z*g)^2: z:=w^2: b:=w*sqrt(3): g:=2*sin(arcsin(3*b/2)/3)/b: Gser:=simplify(series(G,w=0,24)): P[0]:=1: for n from 1 to 10 do P[n]:=sort(coeff(Gser,w^(2*n))) od: for n from 0 to 10 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields sequence in triangular form

Mathematica

max = 20; z = w^2; b = w*Sqrt[3]; g = 2*(Sin[ ArcSin[3*(b/2)]/3]/b); gf = (g + z*g - t*z - 2*z*g^2 + t^2*(1 - t)*z^3*g^2 - 2*t*(1 - t)*z^2*g)/(1 - t*z*g)^2; se = Series[gf, {w, 0, max}]; Flatten[ Rest /@ DeleteCases[ (CoefficientList[t*#1, t] & ) /@ CoefficientList[se, w], {}]] (* Jean-François Alcover, Oct 05 2011, after Maple *)

PARI

S(n)={my(g=1+serreverse(x/(1+x)^3 + O(x*x^n))); Vec((g + x*g - y*x - 2*x*g^2 + y^2*(1-y)*x^3*g^2 - 2*y*(1-y)*x^2*g)/(1 - y*x*g)^2)}
my(v=S(10)); for(n=1, #v, my(p=v[n]); for(k=0, n-1, print1(polcoeff(p, k), ", ")); print); \\ Andrew Howroyd, Nov 17 2017

Formula

G.f.: G(t, z)=(g+zg-tz-2zg^2+t^2*(1-t)z^3*g^2-2t(1-t)z^2*g)/(1-tzg)^2, where g=1+zg^3 is the g.f. for the ternary numbers (A001764).