A129181 Triangle read by rows: T(n,k) is the number of Motzkin paths of length n such that the area between the x-axis and the path is k (n>=0; 0<=k<=floor(n^2/4)).

1, 1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 1, 4, 6, 4, 3, 2, 1, 1, 5, 10, 10, 8, 7, 5, 3, 1, 1, 1, 6, 15, 20, 19, 18, 16, 12, 8, 6, 3, 2, 1, 1, 7, 21, 35, 40, 41, 41, 36, 29, 23, 18, 12, 9, 5, 3, 1, 1, 1, 8, 28, 56, 76, 86, 93, 92, 83, 72, 62, 50, 40, 30, 22, 14, 10, 6, 3, 2, 1, 1, 9, 36, 84, 133, 168

Offset

0,6

Comments

Row n has 1+floor(n^2/4) terms.

Row sums are the Motzkin numbers (A001006).

Links

Alois P. Heinz, Rows n = 0..50, flattened

Clementa Alonso-González and Miguel Ángel Navarro-Pérez, Motzkin numbers and flag codes, arXiv:2207.01997 [math.CO], 2022.

Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

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

A. Bärtschi, B. Geissmann, D. Graf, T. Hruz, P. Penna, and T. Tschager, On computing the total displacement number via weighted Motzkin paths, arXiv:1606.05538 [cs.DS], 2016.

Thomas Grubb and Frederick Rajasekaran, Set Partition Patterns and the Dimension Index, arXiv:2009.00650 [math.CO], 2020. Mentions this sequence.

Formula

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

Sum_{k>=0} k * T(n,k) = A057585(n).

Sum_{j=0..n} T(n-j,j) = A186085(n+1). - Alois P. Heinz, Jun 25 2023

Example

T(5,3) = 4 because we have LULLD, ULLDL, UDULD and ULDUD, where U=(1,1), L=(1,0) and D=(1,-1).
Triangle starts:
00: 1;
01: 1;
02: 1, 1;
03: 1, 2,  1;
04: 1, 3,  3,  1, 1;
05: 1, 4,  6,  4, 3, 2, 1;
06: 1, 5, 10, 10, 8, 7, 5, 3, 1, 1;
...
From Joerg Arndt, Apr 19 2014: (Start)
Row n=5 corresponds to the following Motzkin paths (dots denote zeros):
# :   height in path   area    step in path
01:  [ . . . . . . ]     0     0 0 0 0 0
02:  [ . . . . 1 . ]     1     0 0 0 + -
03:  [ . . . 1 . . ]     1     0 0 + - 0
04:  [ . . . 1 1 . ]     2     0 0 + 0 -
05:  [ . . 1 . . . ]     1     0 + - 0 0
06:  [ . . 1 . 1 . ]     2     0 + - + -
07:  [ . . 1 1 . . ]     2     0 + 0 - 0
08:  [ . . 1 1 1 . ]     3     0 + 0 0 -
09:  [ . . 1 2 1 . ]     4     0 + + - -
10:  [ . 1 . . . . ]     1     + - 0 0 0
11:  [ . 1 . . 1 . ]     2     + - 0 + -
12:  [ . 1 . 1 . . ]     2     + - + - 0
13:  [ . 1 . 1 1 . ]     3     + - + 0 -
14:  [ . 1 1 . . . ]     2     + 0 - 0 0
15:  [ . 1 1 . 1 . ]     3     + 0 - + -
16:  [ . 1 1 1 . . ]     3     + 0 0 - 0
17:  [ . 1 1 1 1 . ]     4     + 0 0 0 -
18:  [ . 1 1 2 1 . ]     5     + 0 + - -
19:  [ . 1 2 1 . . ]     4     + + - - 0
20:  [ . 1 2 1 1 . ]     5     + + - 0 -
21:  [ . 1 2 2 1 . ]     6     + + 0 - -
(End)

Maple

G:=1/(1-z-t*z^2*g[1]): for i from 1 to 13 do g[i]:=1/(1-t^i*z-t^(2*i+1)*z^2*g[i+1]) od: g[14]:=0: Gser:=simplify(series(G, z=0, 13)): for n from 0 to 10 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 0 to 10 do seq(coeff(P[n], t, j), j=0..floor(n^2/4)) od; # yields sequence in triangular form
# second Maple program
b:= proc(x, y, k) option remember;
      `if`(x<0 or x<y or y<0 or k<0 or 2*k>x^2, 0,
      `if`(x=0, 1, add(b(x-1, y+i, k-y-i/2), i=-1..1)))
    end:
T:= (n, k)-> b(n, 0, k):
seq(seq(T(n, k), k=0..floor(n^2/4)), n=0..12); # Alois P. Heinz, Jun 28 2012

Mathematica

b[x_, y_, k_] := b[x, y, k] = If[x<0 || x<y || y<0 || k<0 || 2*k>x^2, 0, If[x==0, 1, Sum[b[x-1, y+i, k-y-i/2], {i, -1, 1}]]]; T[n_, k_] := b[n, 0, k]; Table[Table[ T[n, k], {k, 0, Floor[n^2/4]}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

Crossrefs

Cf. A001006, A057585.

Antidiagonal sums give A186085(n+1).

Sequence in context: A090402 A026082 A117185 * A157694 A271187 A093557

Adjacent sequences: A129178 A129179 A129180 * A129182 A129183 A129184

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 08 2007

Status

approved