login
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)).
5
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
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;
07: 1, 6, 15, 20, 19, 18, 16, 12, 8, 6, 3, 2, 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
Antidiagonal sums give A186085(n+1).
Sequence in context: A090402 A026082 A117185 * A157694 A271187 A093557
KEYWORD
nonn,tabf,changed
AUTHOR
Emeric Deutsch, Apr 08 2007
STATUS
approved