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

1, 1, 2, 6, 24, 109, 11, 588, 132, 3654, 1386, 26125, 13606, 589, 209863, 139714, 13303, 1876502, 1508756, 243542, 18441367, 17429745, 3953529, 92159, 197776850, 214536114, 63334182, 3354454, 2297242583, 2815529811, 1020982869, 93265537, 28739304385

Offset: 0

Author

Alois P. Heinz, Oct 27 2013

Keywords

• nonn
• tabf

Examples

			T(5,1) = 11: 14325, 15324, 15423, 24315, 25314, 25413, 34215, 35214, 35412, 45213, 45312.
T(8,2) = 589: 14327658, 14328657, 14328756, ..., 78635412, 78645213, 78645312.
Triangle T(n,k) begins:
:  0 :        1;
:  1 :        1;
:  2 :        2;
:  3 :        6;
:  4 :       24;
:  5 :      109,       11;
:  6 :      588,      132;
:  7 :     3654,     1386;
:  8 :    26125,    13606,     589;
:  9 :   209863,   139714,   13303;
: 10 :  1876502,  1508756,  243542;
: 11 : 18441367, 17429745, 3953529, 92159;
		

Links

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

Crossrefs

Column k=0 gives: A177519.

Row sums give: A000142.

Cf. 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, 4, 1][t]), j=1..u)+
      add(b(u+j-1, o-j, 2)*`if`(t=4, 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, 4, 1}[[t]]], {j, 1, u}] +
     Sum[b[u + j - 1, o - j, 2]*If[t == 4, x, 1], {j, 1, o}]]];
T[n_] := CoefficientList[b[n, 0, 1], x];
T /@ Range[0, 15] // Flatten (* Jean-François Alcover, Mar 22 2021, after Alois P. Heinz *)