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,3

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.

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

Example

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

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

Crossrefs

Cf. A049774, A080635.

Sequence in context: A012306 A012312 A009243 * A371612 A307957 A307956

Adjacent sequences: A232861 A232862 A232863 * A232865 A232866 A232867

Keyword

nonn

Author

Richard Ehrenborg, Dec 01 2013

Status

approved