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

1, 1, 2, 6, 24, 104, 16, 528, 192, 3296, 1472, 272, 23168, 12800, 4352, 179712, 132352, 42880, 7936, 1573632, 1366016, 530432, 158720, 15207424, 14781952, 7662336, 1911296, 353792, 158880768, 178102272, 101713920, 31813632, 8491008, 1801996288, 2282645504

Offset

0,3

Links

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

Example

T(5,1) = 16: 13254, 14253, 14352, 15243, 15342, 23154, 24153, 24351, 25143, 25341, 34152, 34251, 35142, 35241, 45132, 45231.
T(7,2) = 272: 1325476, 1326475, 1326574, ..., 6735241, 6745132, 6745231.
Triangle T(n,k) begins:
:  0 :       1;
:  1 :       1;
:  2 :       2;
:  3 :       6;
:  4 :      24;
:  5 :     104,      16;
:  6 :     528,     192;
:  7 :    3296,    1472,    272;
:  8 :   23168,   12800,   4352;
:  9 :  179712,  132352,  42880,   7936;
: 10 : 1573632, 1366016, 530432, 158720;

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
      add(b(u-j, o+j-1, [1, 3, 1, 3][t])*`if`(t=4, x, 1), j=1..u)+
      add(b(u+j-1, o-j, [2, 2, 4, 2][t]), 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);  # Alois P. Heinz, Oct 30 2013

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, 3}[[t]]]*If[t == 4, x, 1], {j, 1, u}] + Sum[b[u+j-1, o-j, {2, 2, 4, 2}[[t]]], {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, Oct 24 2016, after Alois P. Heinz *)

Crossrefs

Columns k=0-2 give: A177520, A230832, A264077.

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

Row sums give: A000142.

Cf. A242783, A242784, A295987.

Sequence in context: A078486 A352364 A129817 * A376585 A128652 A152316

Adjacent sequences: A230794 A230795 A230796 * A230798 A230799 A230800

Keyword

nonn,tabf

Author

Alois P. Heinz, Oct 30 2013

Status

approved