A227884 - OEIS

%I #29 May 14 2018 10:15:24

%S 1,1,2,6,19,5,70,50,331,328,61,1863,2154,1023,11637,16751,10547,1385,

%T 81110,144840,102030,34900,635550,1314149,1109973,518607,50521,

%U 5495339,12735722,13046040,6858598,1781101,51590494,134159743,157195762,97348436,36004400

%N 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.

%H Alois P. Heinz, <a href="/A227884/b227884.txt">Rows n = 0..170, flattened</a>

%e T(4,1) = 5: 1324, 1423, 2314, 2413, 3412.

%e Triangle T(n,k) begins:

%e :  0 :      1;

%e :  1 :      1;

%e :  2 :      2;

%e :  3 :      6;

%e :  4 :     19,       5;

%e :  5 :     70,      50;

%e :  6 :    331,     328,      61;

%e :  7 :   1863,    2154,    1023;

%e :  8 :  11637,   16751,   10547,   1385;

%e :  9 :  81110,  144840,  102030,  34900;

%e : 10 : 635550, 1314149, 1109973, 518607, 50521;

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(

%p       add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)+

%p       add(b(u+j-1, o-j, 2)*`if`(t=3, x, 1), j=1..o)))

%p     end:

%p T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 1)):

%p seq(T(n), n=0..15);

%t 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 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 1]];

%t Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, Mar 29 2017, translated from Maple *)

%Y Columns k=0-1 give: A177477, A227883.

%Y T(2n,n-1) gives A000364(n) for n>=2.

%Y Row sums give: A000142.

%Y Cf. A000111, A242783, A242784, A295987.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Oct 25 2013