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

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, 512, 189, 44, 5, 2188, 1353, 518, 133, 20, 1, 5798, 3610, 1422, 392, 70, 6, 15511, 9713, 3915, 1140, 230, 27, 1, 41835, 26324, 10813, 3288, 726, 104, 7, 113634, 71799, 29964

Offset: 2

Author

Emeric Deutsch, May 29 2005

Keywords

• nonn
• tabf

Comments

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.

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

Examples

			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.
Triangle begins:
   1;
   1;
   2,  1;
   4,  2;
   9,  5,  1;
  21, 12,  3;
  51, 30,  9,  1.
		

Links

• F. R. Bernhart, Catalan, Motzkin and Riordan numbers, Discr. Math., 204 (1999), 73-112.
• Sen-Peng Eu, Shu-Chung Liu, and Yeong-Nan Yeh, Taylor expansions for Catalan and Motzkin numbers, Advances in Applied Mathematics 29, Issue 3 (2002), 345-357 (see p. 352).

Crossrefs

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

Programs

Maple

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

Mathematica

(* To generate the sequence *)
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
(* To generate the triangle *)
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
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
(* Emanuele Munarini, Feb 10 2018 *)

Formula

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

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

The rows are the antidiagonals of the Motzkin triangle A064189. - Peter Luschny, Feb 01 2025