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;
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
KEYWORD
nonn,tabf,changed
AUTHOR
Emeric Deutsch, Apr 08 2007
STATUS
approved