cp's OEIS Frontend

A297708 Number of permutations p of [n] such that p(p(i)) = i for all i or p(n+1-p(i)) = n+1-i for all i.

%I A297708 #43 Jan 02 2024 09:35:53
%S A297708 1,1,2,6,14,46,132,444,1452,5164,18680,71080,278920,1135624,4774448,
%T A297708 20692560,92381072,423566224,1994458656,9619233888,47516407008,
%U A297708 239904464608,1237764055616,6515682543040,34984350444736,191360856810688,1065970229647232,6041353305197184
%N A297708 Number of permutations p of [n] such that p(p(i)) = i for all i or p(n+1-p(i)) = n+1-i for all i.
%C A297708 a(n) is likewise the number of ways to place n points on an n X n grid with pairwise distinct abscissa, pairwise distinct ordinate, and mirror symmetry using one or the other of the diagonals of the grid as axis of symmetry. See also A000085 and A135401. For rotational symmetry see A001813 and A006882.
%H A297708 Alois P. Heinz, <a href="/A297708/b297708.txt">Table of n, a(n) for n = 0..800</a> (terms n = 0..99 from Manfred Scheucher)
%H A297708 Manfred Scheucher, <a href="/A297708/a297708.py.txt">Python program for enumeration</a>
%F A297708 a(n) = 2*A000085(n) - A135401(n). (Proof: A000085 counts the permutations satisfying the first condition as well as the permutations satisfying the second condition. A135401 counts the permutations satisfying both conditions.)
%p A297708 a:= proc(n) option remember; `if`(n<7, [1$2, 2, 6, 14, 46, 132][n+1],
%p A297708       ((-25*n+149)*a(n-1)+(2*(10*n^2-7*n-106))*a(n-2)+
%p A297708        (45*n^2-268*n+298)*a(n-3)-(2*(10*n^2-7*n-61))*a(n-4)
%p A297708        -(65*n^2-367*n+522)*a(n-5)-(2*(10*n^3-67*n^2+96*n+1))*a(n-6)
%p A297708        -(45*n-113)*(n-4)*(n-6)*a(n-7))/(20*n-79))
%p A297708     end:
%p A297708 seq(a(n), n=0..35);  # _Alois P. Heinz_, Jan 07 2018
%t A297708 a[n_] := 2*Sum[2^k*BellB[k, 1/2]*StirlingS1[n, k], {k, 0, n}] - Sum[2^k*BellB[k]*StirlingS1[Floor[n/2], k], {k, 0, Floor[n/2]}];
%t A297708 Array[a, 30, 0] (* _Jean-François Alcover_, May 29 2019 *)
%o A297708 (SageMath)
%o A297708 def a135401(n): return sum( binomial(floor(n/2),2*k)*binomial(2*k,k)*factorial(k)*2^(floor(n/2)-2*k) for k in range(1+floor(n/4)))
%o A297708 def a85(n): return sum( factorial(n) / (factorial(n-2*k) * 2^k * factorial(k)) for k in range(1+floor(n/2)))
%o A297708 def a297708(n): return 2*a85(n) - a135401(n)
%o A297708 for n in range(100): print(n, a297708(n))
%Y A297708 Cf. A000085, A001813, A006882, A135401.
%K A297708 nonn
%O A297708 0,3
%A A297708 _Manfred Scheucher_, Jan 03 2018