login
Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).
0

%I #30 Dec 13 2021 02:23:33

%S 1,1,2,1,4,2,9,5,1,21,12,3,51,30,9,1,127,76,25,4,323,196,69,14,1,835,

%T 512,189,44,5,2188,1353,518,133,20,1,5798,3610,1422,392,70,6,15511,

%U 9713,3915,1140,230,27,1,41835,26324,10813,3288,726,104,7,113634,71799,29964

%N Triangle read by rows: T(n,k) is the number of short bushes with n edges and having the leftmost leaf at height k (a short bush is an ordered tree with no nodes of outdegree 1).

%C Basically, the mirror image of A020474. Row n has floor(n/2) terms (first row is row 2). Row sums yield the Riordan numbers (A005043). Column 1 yields the Motzkin numbers (A001006); column 2 yields A002026; column 3 yields A005322; column 4 yields A005323; column 4 yields A005324; column 5 yields A005325; column 6 yields A005326.

%C T(n,k) is the number of Riordan paths (Motzkin paths with no flatsteps on the x-axis) with k returns to the x-axis. For example, T(6,2) = 5 counts UDUFFD, UDUUDD, UFDUFD, UFFDUD, UUDDUD where U = (1,1) is an upstep, F = (1,0) is a flatstep, and D = (1,-1) is a downstep. - _David Callan_, Dec 12 2021

%H F. R. Bernhart, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00054-0">Catalan, Motzkin and Riordan numbers</a>, Discr. Math., 204 (1999), 73-112.

%H Sen-Peng Eu, Shu-Chung Liu, and Yeong-Nan Yeh, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00018-0">Taylor expansions for Catalan and Motzkin numbers</a>, Advances in Applied Mathematics 29, Issue 3 (2002), 345-357 (see p. 352).

%F G.f.: tz^2*S/(1 - zS - tz^2*S), where S = S(z) = (1 + z - sqrt(1 - 2z - 3z^2))/(2z(1+z)) is the g.f. of the short bushes (the Riordan numbers; A005043).

%F a(n,k) = T(n-k+1, n-2*k)*(k+1)/(n-k+1), for n >= 2k, where T(n,k) = A027907(n,k) are the trinomial coefficients. - _Emanuele Munarini_, Feb 10 2018

%e Column 1 yields the Motzkin numbers: indeed, if from each short bush, having leftmost leaf at height 1, we drop the leftmost edge, then we obtain the so-called bushes, known to be counted by the Motzkin numbers.

%e Triangle begins:

%e 1;

%e 1;

%e 2, 1;

%e 4, 2;

%e 9, 5, 1;

%e 21, 12, 3;

%e 51, 30, 9, 1.

%p S:=1/2/(z+z^2)*(1+z-sqrt(1-2*z-3*z^2)): G:=simplify(t*z^2*S/(1-z*S-t*z^2*S)): Gserz:=simplify(series(G,z=0,19)): for n from 2 to 17 do P[n]:=sort(coeff(Gserz,z^n)) od: for n from 2 to 17 do seq(coeff(P[n],t^k),k=1..floor(n/2)) od; # yields sequence in triangular form

%t (* To generate the sequence *)

%t CoefficientList[CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t,0,10}], t], x] // Flatten

%t (* To generate the triangle *)

%t CoefficientList[Series[(1-t-2xt^2-Sqrt[1-2t-3t^2])/(2t^2(1-x+xt+x^2t^2)), {t, 0, 10}], {t, x}] // MatrixForm

%t Table[If[n < 2 k, 0, GegenbauerC[n-2k,-n+k-1,-1/2](k+1)/(n-k+1)], {n,0,10}, {k,0,5}] // MatrixForm

%t (* _Emanuele Munarini_, Feb 10 2018 *)

%Y Cf. A020474, A005043, A001006, A002026, A005322, A005323, A005324, A005325, A005326.

%K nonn,tabf

%O 2,3

%A _Emeric Deutsch_, May 29 2005