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,6

Comments

Row sums yield the ternary numbers (A001764).

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

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.

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).

Example

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;
  ...

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 *)

Prog

(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

Crossrefs

Cf. A001764, A102594.

Sequence in context: A082909 A335906 A029151 * A113415 A332801 A054019

Adjacent sequences: A102592 A102593 A102594 * A102596 A102597 A102598

Keyword

nonn,tabl

Author

Emeric Deutsch, Jan 22 2005

Status

approved