A232864 Number of permutations of n elements not cyclically containing the consecutive pattern 123.

1, 1, 2, 3, 12, 45, 234, 1323, 8856, 65529, 543510, 4937031, 49030596, 526930677, 6101871426, 75686176035, 1001517264432, 14079895613937, 209594037600558, 3293305758743679, 54470994630103260, 945988795762018029, 17211193919411902938, 327371367293394753627

Offset: 0

Author

Richard Ehrenborg, Dec 01 2013

Keywords

• nonn

Examples

			a(4) = 12 comes from the 3 permutations 1324, 1423 and 1432, and by cyclically shifting we obtain 3 * 4 = 12 permutations.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200
• R. Ehrenborg, Cyclically consecutive permutation avoidance, arXiv:1312.2051 [math.CO], 2013.

Crossrefs

Cf. A049774, A080635.

Programs

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 1), j=1..u))
    end:
a:= n-> `if`(n=0, 1, n*b(0, n-1, 1)):
seq(a(n), n=0..25);  # Alois P. Heinz, Dec 01 2013

Mathematica

b[u_,o_,t_] := b[u, o, t] = If[u+o==0, 1, If[t<2, Sum[b[u+j-1, o-j, t+1], {j, 1, o}], 0] + Sum[b[u-j, o+j-1, 1], {j, 1, u}]];
a[n_]:= If[n==0, 1, n*b[0, n-1, 1]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Aug 14 2017, after Alois P. Heinz *)

Formula

a(n) = n! * Sum_{k=-oo..oo} (sqrt(3)/(2*Pi*(k+1/3)))^n for n >= 2.

a(n) = A080635(n-1)*n for n>0. - Alois P. Heinz, Dec 01 2013