Pattern Avoidance in Circular Permutations
Circular permutations on {1,2,...,n} that avoid a given pattern correspond
to ordinary (linear) permutations that end with n and avoid all cyclic
rotations of the pattern. Three letter patterns are all but unavoidable in
circular permutations and here we give explicit formulas for the number of
circular permutations that avoid one four letter pattern. In the three
essentially distinct cases, the counts are as follows: the Fibonacci number
F_{2n-3} for the pattern 1324, 2^{n-1}-(n-1) for 1342, and
2^n+1-2n-{n}choose{3} for 1234.
