|
|
A232899
|
|
Number of permutations of [n] cyclically avoiding the consecutive step pattern UDU (U=up, D=down).
|
|
3
|
|
|
1, 1, 0, 3, 12, 35, 144, 910, 5976, 39942, 306570, 2698223, 25536132, 257563618, 2813856192, 33154390275, 415692891552, 5523237345701, 77778820305558, 1157352664763569, 18120617730892800, 297774609082108662, 5127157782095091402, 92308888110570124310
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(2) = 0 because 12 and 21 do not avoid UDU (the two U's overlap).
a(3) = 3: 132, 213, 321.
a(4) = 12: 1243, 1342, 1432, 2134, 2143, 2431, 3124, 3214, 3421, 4213, 4312, 4321.
a(5) = 35: 12354, 12453, 12543, ..., 54213, 54312, 54321.
|
|
MAPLE
|
b:= proc(u, o, t) option remember; `if`(t=4, 0,
`if`(u+o=0, `if`(t=2, 0, 1),
add(b(u+j-1, o-j, [2, 2, 4][t]), j=1..o)+
add(b(u-j, o+j-1, [1, 3, 1][t]), j=1..u)))
end:
a:= n-> `if`(n<2, 1, n*b(0, n-1, 1)):
seq(a(n), n=0..30);
|
|
MATHEMATICA
|
b[u_, o_, t_] := b[u, o, t] = If[t == 4, 0,
If[u + o == 0, If[t == 2, 0, 1],
Sum[b[u + j - 1, o - j, {2, 2, 4}[[t]]], {j, 1, o}] +
Sum[b[u - j, o + j - 1, {1, 3, 1}[[t]]], {j, 1, u}]]];
a[n_] := If[n < 2, 1, n b[0, n - 1, 1]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|