A227884 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern up, down, up; triangle T(n,k), n>=0, 0<=k<=max(0,floor(n/2)-1), read by rows.

1, 1, 2, 6, 19, 5, 70, 50, 331, 328, 61, 1863, 2154, 1023, 11637, 16751, 10547, 1385, 81110, 144840, 102030, 34900, 635550, 1314149, 1109973, 518607, 50521, 5495339, 12735722, 13046040, 6858598, 1781101, 51590494, 134159743, 157195762, 97348436, 36004400

Offset: 0

Author

Alois P. Heinz, Oct 25 2013

Keywords

• nonn
• tabf

Examples

			T(4,1) = 5: 1324, 1423, 2314, 2413, 3412.
Triangle T(n,k) begins:
:  0 :      1;
:  1 :      1;
:  2 :      2;
:  3 :      6;
:  4 :     19,       5;
:  5 :     70,      50;
:  6 :    331,     328,      61;
:  7 :   1863,    2154,    1023;
:  8 :  11637,   16751,   10547,   1385;
:  9 :  81110,  144840,  102030,  34900;
: 10 : 635550, 1314149, 1109973, 518607, 50521;
		

Links

• Alois P. Heinz, Rows n = 0..170, flattened

Crossrefs

Columns k=0-1 give: A177477, A227883.

T(2n,n-1) gives A000364(n) for n>=2.

Row sums give: A000142.

Cf. A000111, A242783, A242784, A295987.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=3, x, 1), j=1..o)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):
seq(T(n), n=0..15);

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o==0, 1, Expand[Sum[b[u-j, o+j-1, {1, 3, 1}[[t]]], {j, 1, u}]+Sum[b[u+j-1, o-j, 2]*If[t==3, x, 1], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 1]];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, Mar 29 2017, translated from Maple *)