login
Number of permutations in S_{2n} avoiding 123 and 1432 whose matrices are 180-degree symmetric.
1

%I #4 May 29 2016 19:01:56

%S 1,2,6,12,27,61,138,309,694,1560,3506,7877,17699,39770,89363,200796,

%T 451184,1013802,2277993,5118603,11501396,25843403,58069600,130481206,

%U 293188608,658788823,1480285049

%N Number of permutations in S_{2n} avoiding 123 and 1432 whose matrices are 180-degree symmetric.

%C 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.

%H G. C. Greubel, <a href="/A166963/b166963.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,1,1,-1).

%F a(n) = 2a(n-1) + a(n-3) + a(n-4) - a(n-5).

%F G.f.: (-x^3 + 2x^2 + 1)/(x^5 - x^4 - x^3 - 2x + 1).

%e 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.

%t LinearRecurrence[{2,0,1,1,-1},{1, 2, 6, 12, 27}, 50] (* _G. C. Greubel_, May 29 2016 *)

%K nonn

%O 0,2

%A David Lonoff and Jonah Ostroff (jonah.ostroff(AT)gmail.com), Oct 25 2009

%E Fixed typos caused by non-ASCII symbol Jonah Ostroff (jonah.ostroff(AT)gmail.com), Oct 25 2009