A114690 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n and having k weak ascents (1 <= k <= ceiling(n/2)).

1, 2, 3, 1, 5, 4, 8, 12, 1, 13, 31, 7, 21, 73, 32, 1, 34, 162, 116, 11, 55, 344, 365, 70, 1, 89, 707, 1041, 335, 16, 144, 1416, 2762, 1340, 135, 1, 233, 2778, 6932, 4726, 820, 22, 377, 5358, 16646, 15176, 4039, 238, 1, 610, 10188, 38560, 45305, 17157, 1785, 29, 987

Offset

1,2

Comments

A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps.

Row n has ceiling(n/2) terms.

Row sums are the Motzkin numbers (A001006).

Column 1 yields the Fibonacci numbers (A000045).

Sum_{k=1..ceiling(n/2)} k*T(n,k) = A005773(n).

Links

Alois P. Heinz, Rows n = 1..200, flattened

Jean-Luc Baril and José Luis Ramírez, Descent distribution on Catalan words avoiding ordered pairs of Relations, arXiv:2302.12741 [math.CO], 2023.

Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and Matteo Silimbani, Consecutive patterns in restricted permutations and involutions, arXiv:1902.02213 [math.CO], 2019.

Formula

G.f. G = G(t, z) satisfies G = z*(t+G)*(1+z+z*G).

Example

T(4,2)=4 because we have (HU)D(H),(U)D(HH),(U)D(U)D and (UH)D(H) (the weak ascents are shown between parentheses).
Triangle starts:
   1;
   2;
   3,  1;
   5,  4;
   8, 12,  1;
  13, 31,  7;
  ...

Maple

G:=(1-t*z^2-z-z^2-sqrt(1-2*t*z^2-2*z-z^2+t^2*z^4-2*t*z^3-2*z^4*t+2*z^3+z^4))/2/z^2: Gser:=simplify(series(G, z=0, 18)): for n from 1 to 15 do P[n]:=coeff(Gser, z^n) od: for n from 1 to 15 do seq(coeff(P[n], t^j), j=1..ceil(n/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, t,
      b(x-1, y+1, z)+expand(b(x-1, y-1, 1)*t)+b(x-1, y, z)))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=1..degree(p)))(b(n, 0, 1)):
seq(T(n), n=1..14);  # Alois P. Heinz, Nov 16 2019

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x==0, t,
     b[x-1, y+1, z] + Expand[b[x-1, y-1, 1]*t] + b[x-1, y, z]]];
T[n_] := CoefficientList[b[n, 0, 1]/z, z];
Array[T, 14] // Flatten (* Jean-François Alcover, Feb 14 2021, after Alois P. Heinz *)

Crossrefs

Cf. A001006, A005773, A000045, A114655.

Sequence in context: A345011 A345012 A345145 * A336364 A294223 A355618

Adjacent sequences: A114687 A114688 A114689 * A114691 A114692 A114693

Keyword

nonn,tabf

Author

Emeric Deutsch, Dec 24 2005

Status

approved