A295987 - OEIS

%I #19 Jun 07 2018 04:22:07

%S 1,1,2,6,14,10,52,36,32,204,254,140,122,1010,1368,1498,620,544,5466,

%T 9704,9858,9358,3164,2770,34090,67908,90988,72120,63786,18116,15872,

%U 233026,545962,762816,839678,560658,470262,115356,101042,1765836,4604360,7458522

%N Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step patterns 010 or 101, where 1=up and 0=down; triangle T(n,k), n >= 0, k = max(0, n-3), read by rows.

%H Alois P. Heinz, <a href="/A295987/b295987.txt">Rows n = 0..143, flattened</a>

%e Triangle T(n,k) begins:

%e :      1;

%e :      1;

%e :      2;

%e :      6;

%e :     14,     10;

%e :     52,     36,     32;

%e :    204,    254,    140,    122;

%e :   1010,   1368,   1498,    620,    544;

%e :   5466,   9704,   9858,   9358,   3164,   2770;

%e :  34090,  67908,  90988,  72120,  63786,  18116,  15872;

%e : 233026, 545962, 762816, 839678, 560658, 470262, 115356, 101042;

%p b:= proc(u, o, t, h) option remember; expand(

%p            `if`(u+o=0, 1, `if`(t=0, add(b(u-j, j-1, 1$2), j=1..u),

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

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

%p     end:

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

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

%t b[u_, o_, t_, h_] := b[u, o, t, h] = Expand[If[u + o == 0, 1, If[t == 0, Sum[b[u - j, j - 1, 1, 1], {j, 1, u}], Sum[If[h == 3, x, 1]*b[u - j, o + j - 1, {1, 3, 1}[[t]], 2], {j, 1, u}] + Sum[If[t == 3, x, 1]*b[u + j - 1, o - j, 2, {1, 3, 1}[[h]]], {j, 1, o}]]]];

%t T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, 0, 0, 0]];

%t Table[T[n], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Jun 07 2018, from Maple *)

%Y Column k=0 gives A295974.

%Y Last elements of rows for n>3 give: A001250, A260786, 2*A000111.

%Y Row sums give A000142.

%Y Cf. A227884, A230695, A230797, A231384, A232933, A242783, A242819, A242820, A296054.

%K nonn,tabf

%O 0,3

%A _Alois P. Heinz_, Dec 01 2017