A232933 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping, cyclic wrap-around) occurrences of the consecutive step pattern UDU (U=up, D=down); triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.

1, 1, 0, 2, 3, 3, 12, 4, 8, 35, 45, 40, 144, 348, 132, 96, 910, 1862, 1316, 952, 5976, 11600, 14808, 5760, 2176, 39942, 100260, 123606, 63360, 35712, 306570, 919270, 1069910, 910650, 343040, 79360, 2698223, 8427243, 11694397, 10673641, 4477440, 1945856

Offset

0,4

Links

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

Example

T(2,1) = 2: 12, 21 (the two U's of UDU overlap).
T(3,0) = 3: 132, 213, 321.
T(3,1) = 3: 123, 231, 312.
T(4,0) = 12: 1243, 1342, 1432, 2134, 2143, 2431, 3124, 3214, 3421, 4213, 4312, 4321.
T(4,1) = 4: 1234, 2341, 3412, 4123.
T(4,2) = 8: 1324, 1423, 2314, 2413, 3142, 3241, 4132, 4231.
Triangle T(n,k) begins:
:  0 :      1;
:  1 :      1;
:  2 :      0,      2;
:  3 :      3,      3;
:  4 :     12,      4,       8;
:  5 :     35,     45,      40;
:  6 :    144,    348,     132,     96;
:  7 :    910,   1862,    1316,    952;
:  8 :   5976,  11600,   14808,   5760,   2176;
:  9 :  39942, 100260,  123606,  63360,  35712;
: 10 : 306570, 919270, 1069910, 910650, 343040, 79360;

Maple

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

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, If[t == 2, x, 1], Expand[Sum[ b[u + j - 1, o - j, 2]*If[t == 3, x, 1], {j, 1, o}] + Sum[b[u - j, o + j - 1, If[t == 2, 3, 1]], {j, 1, u}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]]   [If[n < 2, 1, n*b[0, n - 1, 1]]];
T /@ Range[0, 12] // Flatten (* Jean-François Alcover, Dec 19 2020, after Alois P. Heinz *)

Crossrefs

Column k=0 gives A232899.

Row sums give A000142.

T(2n,n) gives A009752(n) = 2n * A000182(n) for n>0.

T(2n+1,n) gives (2n+1) * A024283(n) for n>0.

Cf. A295987.

Sequence in context: A112858 A161960 A287428 * A303700 A196837 A275212

Adjacent sequences: A232930 A232931 A232932 * A232934 A232935 A232936

Keyword

nonn,tabf

Author

Alois P. Heinz, Dec 02 2013

Status

approved