login
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.
4
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
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
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Dec 02 2013
STATUS
approved