cp's OEIS Frontend

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.

%I A231384 #20 Dec 01 2017 17:41:57
%S A231384 1,1,2,6,13,11,39,52,29,158,233,230,99,674,1344,1537,1118,367,3304,
%T A231384 8197,11208,10200,5868,1543,19511,49846,89657,95624,67223,33118,7901,
%U A231384 122706,351946,724755,907078,781827,492285,206444,41759,834131,2799536,6010150
%N 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.
%H A231384 Alois P. Heinz, <a href="/A231384/b231384.txt">Rows n = 0..80, flattened</a>
%H A231384 A. Baxter, B. Nakamura, and D. Zeilberger, <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>
%H A231384 S. Kitaev and T. Mansour, <a href="http://www.ru.is/kennarar/sergey/index_files/Papers/multi_avoid_gen_patterns.pdf">On multi-avoidance of generalized patterns</a>
%e A231384 T(4,1) = 11: 1243, 1342, 2341 (UUD), 1324, 1423, 2314, 2413, 3412 (UDU), 2134, 3124, 4123 (DUU).
%e A231384 T(5,0) = 39: 12345, 14325, 15324, ..., 54231, 54312, 54321.
%e A231384 T(5,1) = 52: 12354, 12453, 12543, ..., 53124, 53412, 54123.
%e A231384 T(5,2) = 29: 12435, 12534, 13245, ..., 51243, 51342, 52341.
%e A231384 Triangle T(n,k) begins:
%e A231384 : 0 :     1;
%e A231384 : 1 :     1;
%e A231384 : 2 :     2;
%e A231384 : 3 :     6;
%e A231384 : 4 :    13,    11;
%e A231384 : 5 :    39,    52,    29;
%e A231384 : 6 :   158,   233,   230,    99;
%e A231384 : 7 :   674,  1344,  1537,  1118,   367;
%e A231384 : 8 :  3304,  8197, 11208, 10200,  5868,  1543;
%e A231384 : 9 : 19511, 49846, 89657, 95624, 67223, 33118, 7901;
%p A231384 b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
%p A231384      add(b(u+j-1, o-j, [2, 3, 3, 6, 6, 3][t])*
%p A231384              `if`(t in [5, 6], x, 1), j=1..o)+
%p A231384      add(b(u-j, o+j-1, [4, 5, 5, 4, 4, 5][t])*
%p A231384              `if`(t=3, x, 1), j=1..u)))
%p A231384     end:
%p A231384 T:= n-> `if`(n=0, 1, (p-> seq(coeff(p, x, i), i=0..degree(p)))
%p A231384                      (add(b(j-1, n-j, 1), j=1..n))):
%p A231384 seq(T(n), n=0..12);
%t A231384 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_ *)
%Y A231384 Columns k=0-2 give: A231385, A231386, A228408.
%Y A231384 Diagonal gives: A231410.
%Y A231384 Row sums give: A000142.
%Y A231384 Cf. A295987.
%K A231384 nonn,tabf
%O A231384 0,3
%A A231384 _Alois P. Heinz_, Nov 08 2013