A232899 Number of permutations of [n] cyclically avoiding the consecutive step pattern UDU (U=up, D=down).

1, 1, 0, 3, 12, 35, 144, 910, 5976, 39942, 306570, 2698223, 25536132, 257563618, 2813856192, 33154390275, 415692891552, 5523237345701, 77778820305558, 1157352664763569, 18120617730892800, 297774609082108662, 5127157782095091402, 92308888110570124310

Offset: 0

Author

Alois P. Heinz, Dec 02 2013

Keywords

• nonn

Examples

			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.
		

Links

• Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..460 (first 200 terms from Alois P. Heinz)

Crossrefs

Column k=0 of A232933.

Cf. A177477, A245758.

Programs

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]];
a /@ Range[0, 30] (* Jean-François Alcover, Dec 19 2020, after Alois P. Heinz *)

Formula

a(n) ~ d^n * n!, where d = A245758 = 0.782704180171521701844707497734609... . - Vaclav Kotesovec, Aug 22 2014