|
|
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.
|
|
5
|
|
|
1, 1, 2, 6, 14, 46, 132, 444, 1452, 5164, 18680, 71080, 278920, 1135624, 4774448, 20692560, 92381072, 423566224, 1994458656, 9619233888, 47516407008, 239904464608, 1237764055616, 6515682543040, 34984350444736, 191360856810688, 1065970229647232, 6041353305197184
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
FORMULA
|
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.)
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<7, [1$2, 2, 6, 14, 46, 132][n+1],
((-25*n+149)*a(n-1)+(2*(10*n^2-7*n-106))*a(n-2)+
(45*n^2-268*n+298)*a(n-3)-(2*(10*n^2-7*n-61))*a(n-4)
-(65*n^2-367*n+522)*a(n-5)-(2*(10*n^3-67*n^2+96*n+1))*a(n-6)
-(45*n-113)*(n-4)*(n-6)*a(n-7))/(20*n-79))
end:
|
|
MATHEMATICA
|
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]}];
|
|
PROG
|
(SageMath)
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)))
def a85(n): return sum( factorial(n) / (factorial(n-2*k) * 2^k * factorial(k)) for k in range(1+floor(n/2)))
def a297708(n): return 2*a85(n) - a135401(n)
for n in range(100): print(n, a297708(n))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|