cp's OEIS Frontend

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

%I A106489 #32 Feb 01 2025 09:05:48
%S A106489 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 A106489 512,189,44,5,2188,1353,518,133,20,1,5798,3610,1422,392,70,6,15511,
%U A106489 9713,3915,1140,230,27,1,41835,26324,10813,3288,726,104,7,113634,71799,29964
%N 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).
%C A106489 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 A106489 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 A106489 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 A106489 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 A106489 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 A106489 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
%F A106489 The rows are the antidiagonals of the Motzkin triangle A064189. - _Peter Luschny_, Feb 01 2025
%e A106489 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 A106489 Triangle begins:
%e A106489    1;
%e A106489    1;
%e A106489    2,  1;
%e A106489    4,  2;
%e A106489    9,  5,  1;
%e A106489   21, 12,  3;
%e A106489   51, 30,  9,  1.
%p A106489 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 A106489 (* To generate the sequence *)
%t A106489 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 A106489 (* To generate the triangle *)
%t A106489 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 A106489 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 A106489 (* _Emanuele Munarini_, Feb 10 2018 *)
%Y A106489 Cf. A020474, A005043, A001006, A002026, A005322, A005323, A005324, A005325, A005326, A064189.
%K A106489 nonn,tabf
%O A106489 2,3
%A A106489 _Emeric Deutsch_, May 29 2005