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

%I #25 Jun 23 2024 15:51:38

%S 1,1,2,3,12,45,234,1323,8856,65529,543510,4937031,49030596,526930677,

%T 6101871426,75686176035,1001517264432,14079895613937,209594037600558,

%U 3293305758743679,54470994630103260,945988795762018029,17211193919411902938,327371367293394753627

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

%H Alois P. Heinz, <a href="/A232864/b232864.txt">Table of n, a(n) for n = 0..200</a>

%H R. Ehrenborg, <a href="https://arxiv.org/abs/1312.2051">Cyclically consecutive permutation avoidance</a>, arXiv:1312.2051 [math.CO], 2013.

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

%F a(n) = A080635(n-1)*n for n>0. - _Alois P. Heinz_, Dec 01 2013

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

%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

%p `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+

%p add(b(u-j, o+j-1, 1), j=1..u))

%p end:

%p a:= n-> `if`(n=0, 1, n*b(0, n-1, 1)):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Dec 01 2013

%t 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}]];

%t a[n_]:= If[n==0, 1, n*b[0, n-1, 1]];

%t Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Aug 14 2017, after _Alois P. Heinz_ *)

%Y Cf. A049774, A080635.

%K nonn

%O 0,3

%A _Richard Ehrenborg_, Dec 01 2013