login
a(n) = number of permutations (p(1),p(2),p(3),...,p(n)) of (1,2,3,...n) each of which is its own inverse and is such that p(k) = n + 1 - p(n+1-k) for all k in the range 1 <= k <= n.
8

%I #64 Mar 12 2024 15:32:36

%S 1,1,2,2,6,6,20,20,76,76,312,312,1384,1384,6512,6512,32400,32400,

%T 168992,168992,921184,921184,5222208,5222208,30710464,30710464,

%U 186753920,186753920,1171979904,1171979904,7573069568,7573069568,50305536256,50305536256,342949298688

%N a(n) = number of permutations (p(1),p(2),p(3),...,p(n)) of (1,2,3,...n) each of which is its own inverse and is such that p(k) = n + 1 - p(n+1-k) for all k in the range 1 <= k <= n.

%C a(n) is also the number of ways to place n points on an n X n grid with pairwise distinct abscissa, pairwise distinct ordinate, mirror symmetry and 180-degree rotational symmetry. Note that both diagonals are actually axes of symmetry. See also A297708, A000085, A001813, and A006882. - _Manfred Scheucher_, Jan 04 2018

%C a(n) is the number of standard Young tableaux of size n invariant under Schützenberger involution. - _Ludovic Schwob_, Feb 17 2024

%H Manfred Scheucher, <a href="/A135401/b135401.txt">Table of n, a(n) for n = 0..99</a>

%F a(n) = A000898(floor(n/2)). - Conjectured by _Leroy Quet_, Jan 20 2008; proved by _Max Alekseyev_, Jan 21 2008: (Start)

%F Let p = (p(1),...,p(n)) be a permutation such that p(k) = n + 1 - p(n+1-k) for all 1 <= k <= n.

%F Then 2-set {k, n+1-k} (i.e., where the sum of elements is n+1) is mapped by p into {p(k), p(n+1-k)} with the same property p(k) + p(n+1-k) = n+1. Therefore every such permutation induces a permutation q on the 2-sets {k, n+1-k}, and for odd n has a fixed point p((n+1)/2) = (n+1)/2.

%F Furthermore, it is easy to see that if p is self-inverse then so is q.

%F Let s=floor(n/2). For every permutation q on the sets {k, n+1-k}, 1 <= k <= s, let's count how many p induce it.

%F It is clear that if q has exactly m fixed points (and so the other s-m 2-sets form pairs of inverses under q), then there exist 2^m ways to define p on the fixed points of q and 2^((s-m)/2) ways to define p on the remaining elements.

%F Hence the total number of permutations p inducing q is 2^m * 2^((s-m)/2) = 2^((s+m)/2). The number of permutations q on s elements with exactly m fixed points is nonzero only if m and s are of the same oddness and in this case it is binomial(s,m) * (s-m)! / 2^((s-m)/2) / ((s-m)/2)! = binomial(s,m) * (s-m-1)!! = s! / m! / 2^((s-m)/2) / ((s-m)/2)!.

%F Hence a(n) = Sum s! * 2^m / m! / ((s-m)/2)!, where sum is taken over m=0,1...,s of the same oddness as s. Let s-m=2t so that m=s-2t and a(n) = Sum_{t=0..floor(s/2)} s! * 2^(s-2t) / ((s-2t)! * t!) = s! * [x^s] e^(2x) * e^(x^2) = s! * [x^s] e^(x^2+2x) = A000898(s), according to its e.g.f. QED

%F (End)

%F a(n) = Sum_{k=0..floor(n/2)} binomial(floor(n/2),2k) *binomial(2k,k) *k! *2^(floor(n/2)-2k). (See A000898 for the original formula by N. Calkin, for further equivalent expressions, and for (exponential) generating function.) - _Manfred Scheucher_, Jan 07 2018

%e For n = 6 we can have the permutation (3,5,1,6,2,4). This permutation is its own inverse permutation. Furthermore, 7 = p(1)+p(6) = p(2)+p(5) = p(3)+p(4) = 3+4 = 5+2 = 1+6. So this permutation among others is included in the count of permutations when n=6.

%e a(4) = 6 because we have 1234, 1324, 3412, 2143, 4231 and 4321.

%p with(combinat): with(group): a:=proc(n) local P,ct,j,pc,prc: P:=permute(n): ct:= 0: for j to factorial(n) do pc:=convert(P[j], 'disjcyc'): prc:=[seq(n+1-P[j][n+1-k],k=1..n)]: if invperm(pc)=pc and P[j]=prc then ct:=ct+1 else end if end do: ct end proc: seq(a(n),n=0..9); # _Emeric Deutsch_, Dec 31 2007

%t a898[n_] := Sum[2^k StirlingS1[n, k] BellB[k], {k, 0, n}];

%t a =.; a[n_] := a898[Floor[n/2]];

%t Table[a[n], {n, 0, 40}]

%t (* or: *)

%t a[n_] := a[n] = Which[n==0 || n==-2, 1, OddQ[n], a[n-1],

%t True, 2 a[n-2] + (n-2) a[n-4]];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, May 13 2019, updated Jul 25 2022 *)

%o (PARI) print1(1", "1", ");a=0;b=1;for(n=1,25,c=2*(b+(n-1)*a);print1(c", "c", ");a=b;b=c) \\ Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

%o (Sage)

%o def a135401(n):

%o return sum(binomial(n//2,2*k)*binomial(2*k,k)*factorial(k)*2**(n//2-2*k) for k in range(1+n//4))

%o for n in range(100): print(n, a135401(n)) # _Manfred Scheucher_, Jan 07 2018

%Y Cf. A000085, A001813, A006882, A297708. - _Manfred Scheucher_, Jan 07 2018

%K nonn

%O 0,3

%A _Leroy Quet_, Dec 11 2007

%E 5 more terms from _Emeric Deutsch_, Dec 31 2007

%E More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), Apr 26 2008

%E a(0)=1 prepended by _Alois P. Heinz_, Jan 03 2018