A309563 - OEIS

A309563

Cyclic permutations of length n that avoid the patterns 123 and 231.

1, 1, 1, 1, 2, 3, 2, 2, 4, 6, 2, 2, 6, 8, 4, 4, 6, 10, 4, 4, 10, 12, 4, 4, 12, 18, 6, 6, 8, 12, 8, 8, 16, 22, 6, 6, 18, 22, 8, 8, 12, 22, 10, 10, 22, 26, 8, 8, 20, 32, 12, 12, 18, 24, 12, 12, 28, 36, 8, 8, 30, 38, 16, 16, 20, 36, 16, 16, 24, 30, 12, 12, 36, 54

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,5

LINKS

Table of n, a(n) for n=1..74.

Miklos Bona, Michael Cory, Cyclic Permutations Avoiding Pairs of Patterns of Length Three, arXiv:1805.05196 [math.CO], 2018

FORMULA

a(2)=1; a(n)=phi(n/2) if n=4k, a(n)=phi((n+2)/4) +phi(n/2) if n=4k+2 > 2, and a(n)=phi((n+1)/2) if n is odd, where phi is the Euler totient function.

EXAMPLE

a(4)=1, since the only cyclic permutation of length 4 avoiding both 123 and 231 is (4231)=4312.

CROSSREFS

Cf. A000010.