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
Examples
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)
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.
Programs
-
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 xx^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
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 *)
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
Comments