A005324 -id:A005324 - cp's OEIS frontend

A020474 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.

1, 0, 1, 0, 1, 2, 0, 0, 2, 4, 0, 0, 1, 5, 9, 0, 0, 0, 3, 12, 21, 0, 0, 0, 1, 9, 30, 51, 0, 0, 0, 0, 4, 25, 76, 127, 0, 0, 0, 0, 1, 14, 69, 196, 323, 0, 0, 0, 0, 0, 5, 44, 189, 512, 835, 0, 0, 0, 0, 0, 1, 20, 133, 518, 1353, 2188, 0, 0, 0, 0, 0, 0, 6, 70, 392, 1422, 3610, 5798, 0, 0, 0, 0

Offset: 2

N. J. A. Sloane

T(n,k) = number of Dyck n-paths that start UU, contain no DUDU and no subpath of the form UUPDD with P a nonempty Dyck path and whose terminal descent has length n-k+2. For example, T(5,4)=2 counts UUDUUDUDDD, UUUDDUUDDD (each ending with exactly n-k+2=3 Ds). - David Callan, Sep 25 2006

			Triangle begins:
  1
  0, 1
  0, 1, 2
  0, 0, 2, 4
  0, 0, 1, 5,  9
  0, 0, 0, 3, 12, 21
  0, 0, 0, 1,  9, 30, 51
  0, 0, 0, 0,  4, 25, 76, 127
  0, 0, 0, 0,  1, 14, 69, 196, 323

Reinhard Zumkeller, Rows n = 2..120 of triangle, flattened
M. Aigner, Motzkin Numbers, Europ. J. Comb. 19 (1998), 663-675.
R. De Castro, A. L. Ramírez and J. L. Ramírez, Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs, arXiv preprint arXiv:1310.2449 [cs.DM], 2013.
J. L. Chandon, J. LeMaire and J. Pouget, Denombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.
R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory, Series A, 23 (1977), 291-301.
Paul Peart and Wen-jin Woan, A divisibility property for a subgroup of Riordan matrices, Discrete Appl. Math. 98 (2000), 255-263.

Main diagonal is A001006.
Other diagonals include A002026, A005322, A005323, A005324, A005325. Row sums are (essentially) A005043.
The triangle version of A062105 has the same recurrence with different initial conditions. - N. J. A. Sloane, Apr 11 2020

a020474 n k = a020474_tabl !! (n-2) !! (k-2)
a020474_row n = a020474_tabl !! (n-2)
a020474_tabl = map fst $ iterate f ([1], [0,1]) where
   f (us,vs) = (vs, scanl (+) 0 ws) where
     ws = zipWith (+) (us ++ [0]) vs
-- Reinhard Zumkeller, Jan 03 2013

M:=16; T:=Array(0..M,0..M,0);
T[0,0]:=1; T[1,1]:=1;
for i from 1 to M do T[i,0]:=0; od:
for n from 2 to M do for k from 1 to n do
T[n,k]:= T[n,k-1]+T[n-1,k-1]+T[n-2,k-1];
od: od;
rho:=n->[seq(T[n,k],k=0..n)];
for n from 0 to M do lprint(rho(n)); od: # N. J. A. Sloane, Apr 11 2020

a[2,2]=1; a[n_,k_]/;Not[n>2 && 2<=k<=n] := 0; a[n_,k_]/;(n>2 && 2<=k<=n) := a[n,k] = a[n,k-1] + a[n-1,k-1] + a[n-2,k-1]; Table[a[n,k],{n,2,10},{k,2,n}] (* David Callan, Sep 25 2006 *)

T(n,k)=if(n==0&&k==0,1,if(n<=0||k<=0||nRalf Stephan

@cached_function
def T(n, k):
    if k<0 or nPeter Luschny, Jun 23 2015

a(n,k) = a(n,k-1) + a(n-1,k-1) + a(n-2,k-1), n > k >= 2.

More terms from James Sellers, Feb 04 2000

A026110 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0, s(1) = 1, s(n) = 4, |s(i) - s(i-1)| <= 1 for i >= 2. Also a(n) = T(n,n-4), where T is the array defined in A026105.

Original entry on oeis.org

1, 4, 15, 50, 160, 496, 1509, 4530, 13475, 39820, 117117, 343278, 1003665, 2929200, 8537910, 24863724, 72363951, 210532540, 612398025, 1781252110, 5181318054, 15073505216, 43860668800, 127657036000, 371654416575, 1082359229796

Offset: 4

Clark Kimberling

nonn

Apparently the Motzkin transform of the 6th row of A025117, i.e., of 1, 4, 11, 20, ..., 11, 4, 1 followed by zeros. - R. J. Mathar, Dec 11 2008

First differences of A005324. Cf. A001006, A026125.

Cf. A025117

G.f.: z(1-z)M^5, with M the g.f. of the Motzkin numbers (A001006).

Conjecture: -(n+6)*(n-4)*a(n) +(4*n^2-n-51)*a(n-1) +(-2*n^2+11*n+18)*a(n-2) -(4*n-1)*(n-3)*a(n-3) +3*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jun 23 2013

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

Original entry on oeis.org

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

Emeric Deutsch, May 29 2005

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

			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.

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

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

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

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

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

cp's OEIS Frontend

A020474 A Motzkin triangle: a(n,k), n >= 2, 2 <= k <= n, = number of complete, strictly subdiagonal staircase functions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A026110 a(n) = number of (s(0), s(1), ..., s(n)) such that every s(i) is a nonnegative integer, s(0) = 0, s(1) = 1, s(n) = 4, |s(i) - s(i-1)| <= 1 for i >= 2. Also a(n) = T(n,n-4), where T is the array defined in A026105.

Views

Author

Keywords

Comments

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula