OFFSET
0,2
COMMENTS
Trivially, this also counts 180-degree symmetric permutations avoiding 321 and 4123, 123 and 3214, or 321 and 2341. For the other 140 pairs of patterns in S_3 and S_4, the sequence of symmetric permutations avoiding those patterns is either finite (as in 123 and 4321, by Erdos-Szekeres) or counted by an easily-recognized sequence such as alternating Fibonacci numbers, Catalan numbers, squares plus one, or the naturals.
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,1,1,-1).
FORMULA
a(n) = 2a(n-1) + a(n-3) + a(n-4) - a(n-5).
G.f.: (-x^3 + 2x^2 + 1)/(x^5 - x^4 - x^3 - 2x + 1).
EXAMPLE
For n=2, the a(2) = 6 solutions are 2143, 2413, 3142, 3412, 4231, and 4321. The two other 180-degree symmetric permutations in S_4 are 1234 and 1324, both of which contain the pattern 123.
MATHEMATICA
LinearRecurrence[{2, 0, 1, 1, -1}, {1, 2, 6, 12, 27}, 50] (* G. C. Greubel, May 29 2016 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
David Lonoff and Jonah Ostroff (jonah.ostroff(AT)gmail.com), Oct 25 2009
EXTENSIONS
Fixed typos caused by non-ASCII symbol Jonah Ostroff (jonah.ostroff(AT)gmail.com), Oct 25 2009
STATUS
approved