login
A166963
Number of permutations in S_{2n} avoiding 123 and 1432 whose matrices are 180-degree symmetric.
1
1, 2, 6, 12, 27, 61, 138, 309, 694, 1560, 3506, 7877, 17699, 39770, 89363, 200796, 451184, 1013802, 2277993, 5118603, 11501396, 25843403, 58069600, 130481206, 293188608, 658788823, 1480285049
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.
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
Sequence in context: A059078 A335712 A356465 * A188476 A155583 A140853
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