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,3

Links

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

Example

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;

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 *)

Crossrefs

Column k=0 gives: A177519.

Row sums give: A000142.

Cf. A242783, A242784, A295987.

Sequence in context: A324591 A338987 A174076 * A177519 A214762 A141254

Adjacent sequences: A230692 A230693 A230694 * A230696 A230697 A230698

Keyword

nonn,tabf

Author

Alois P. Heinz, Oct 27 2013

Status

approved