A231384 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of some of the consecutive step patterns UUD, UDU, DUU (U=up, D=down); triangle T(n,k), n>=0, 0<=k<=max(0,n-3), read by rows.

1, 1, 2, 6, 13, 11, 39, 52, 29, 158, 233, 230, 99, 674, 1344, 1537, 1118, 367, 3304, 8197, 11208, 10200, 5868, 1543, 19511, 49846, 89657, 95624, 67223, 33118, 7901, 122706, 351946, 724755, 907078, 781827, 492285, 206444, 41759, 834131, 2799536, 6010150

Offset: 0

Author

Alois P. Heinz, Nov 08 2013

Keywords

• nonn
• tabf

Examples

			T(4,1) = 11: 1243, 1342, 2341 (UUD), 1324, 1423, 2314, 2413, 3412 (UDU), 2134, 3124, 4123 (DUU).
T(5,0) = 39: 12345, 14325, 15324, ..., 54231, 54312, 54321.
T(5,1) = 52: 12354, 12453, 12543, ..., 53124, 53412, 54123.
T(5,2) = 29: 12435, 12534, 13245, ..., 51243, 51342, 52341.
Triangle T(n,k) begins:
: 0 :     1;
: 1 :     1;
: 2 :     2;
: 3 :     6;
: 4 :    13,    11;
: 5 :    39,    52,    29;
: 6 :   158,   233,   230,    99;
: 7 :   674,  1344,  1537,  1118,   367;
: 8 :  3304,  8197, 11208, 10200,  5868,  1543;
: 9 : 19511, 49846, 89657, 95624, 67223, 33118, 7901;
		

Links

• Alois P. Heinz, Rows n = 0..80, flattened
• A. Baxter, B. Nakamura, and D. Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
• S. Kitaev and T. Mansour, On multi-avoidance of generalized patterns

Crossrefs

Columns k=0-2 give: A231385, A231386, A228408.

Diagonal gives: A231410.

Row sums give: A000142.

Cf. A295987.

Programs

Maple

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

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Expand[Sum[b[u+j-1, o-j, {2, 3, 3, 6, 6, 3}[[t]]]*If[t == 5 || t == 6, x, 1], {j, 1, o}] + Sum[b[u-j, o+j-1, {4, 5, 5, 4, 4, 5}[[t]]]*If[t == 3, x, 1], {j, 1, u}]]]; T[n_] := If[n == 0, 1, Function[{p},  Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][Sum[b[j-1, n-j, 1], {j, 1, n}]]]; Table[T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 05 2015, after Alois P. Heinz *)