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,3

Links

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

Example

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;

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 *)

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.

Sequence in context: A262971 A253380 A128123 * A186769 A213400 A282080

Adjacent sequences: A227881 A227882 A227883 * A227885 A227886 A227887

Keyword

nonn,tabf

Author

Alois P. Heinz, Oct 25 2013

Status

approved