login
Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having pyramid weight k (1 <= k <= n).
5

%I #27 Jan 22 2020 03:33:24

%S 1,0,2,0,1,4,0,1,4,8,0,1,5,12,16,0,1,6,18,32,32,0,1,7,25,56,80,64,0,1,

%T 8,33,88,160,192,128,0,1,9,42,129,280,432,448,256,0,1,10,52,180,450,

%U 832,1120,1024,512,0,1,11,63,242,681,1452,2352,2816,2304,1024,0,1,12,75,316

%N Triangle read by rows: T(n,k) is the number of nondecreasing Dyck paths of semilength n, having pyramid weight k (1 <= k <= n).

%C A pyramid in a Dyck word (path) is a factor of the form U^h D^h, where U=(1,1), D=(1,-1) and h is the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.

%C Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,n)=2^(n-1). Sum_{k=1..n} k*T(n,k) = A030267(n).

%C Mirror image of triangle in A153342. - _Philippe Deléham_, Dec 31 2008

%C Essentially triangle given by (0,1/2,1/2,0,0,0,0,0,0,0,...) DELTA (2,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - _Philippe Deléham_, Oct 30 2011

%C A121462 is jointly generated with A208341 as an array of coefficients of polynomials u(n,x): initially, u(1,x)=v(1,x)=1; for n > 1, u(n,x) = x*u(n-1,x) + x*v(n-1) and v(n,x) = x*u(n-1,x) + (x+1)*v(n-1,x). See the Mathematica section. - _Clark Kimberling_, Mar 11 2012

%H E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, <a href="http://dx.doi.org/10.1016/S0012-365X(97)82778-1">Nondecreasing Dyck paths and q-Fibonacci numbers</a>, Discrete Math., 170, 1997, 211-217.

%H A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.

%H E. Deutsch and H. Prodinger, <a href="http://dx.doi.org/10.1016/S0304-3975(03)00222-6">A bijection between directed column-convex polyominoes and ordered trees of height at most three</a>, Theoretical Comp. Science, 307, 2003, 319-325.

%F T(n,k) = Sum_{j=0..k-1} binomial(k-1,j)*binomial(n-k-1+j,j-1) for 2 <= k <= n; T(1,1)=1; T(n,1)=0 for n >= 2.

%F G.f.: G = G(t,z) = tz(1-z)/(1-2tz-z+tz^2).

%F T(n+1,k+1) = A062110(n,k)*2^(2*k-n). - _Philippe Deléham_, Aug 01 2006

%e T(4,3)=4 because we have (UD)U(UD)(UD)D, U(UD)(UD)(UD)D, U(UD)(UUDD)D and U(UUDD)(UD)D, where U=(1,1) and D=(1,-1) (the maximal pyramids are shown between parentheses).

%e Triangle starts:

%e 1;

%e 0, 2;

%e 0, 1, 4;

%e 0, 1, 4, 8;

%e 0, 1, 5, 12, 16;

%e 0, 1, 6, 18, 32, 32;

%p T:=proc(n,k) if n=1 and k=1 then 1 elif k=1 then 0 elif k<=n then sum(binomial(k-1,j)*binomial(n-k-1+j,j-1),j=0..k-1) else 0 fi end: for n from 1 to 13 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form

%t u[1, x_] := 1; v[1, x_] := 1; z = 16;

%t u[n_, x_] := x*u[n - 1, x] + x*v[n - 1, x];

%t v[n_, x_] := x*u[n - 1, x] + (x + 1) v[n - 1, x];

%t Table[Expand[u[n, x]], {n, 1, z/2}]

%t Table[Expand[v[n, x]], {n, 1, z/2}]

%t cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];

%t TableForm[cu]

%t Flatten[%] (* A121462 *)

%t Table[Expand[v[n, x]], {n, 1, z}]

%t cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];

%t TableForm[cv]

%t Flatten[%] (* A208341 *)

%t (* _Clark Kimberling_, Mar 11 2012 *)

%Y Cf. A001519, A030267, A091866.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, Jul 31 2006