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

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.

Sequence in context: A372048 A053269 A163873 * A292588 A335965 A225176

Adjacent sequences: A309560 A309561 A309562 * A309564 A309565 A309566

Keyword

nonn

Author

Miklos Bona, Aug 07 2019

Status

approved