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

Author

Alois P. Heinz, Dec 02 2013

Keywords

• nonn
• tabf

Examples

			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;
		

Links

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

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.

Programs

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