

A283184


a(n) is the number of symmetric permutations (p(1),p(2),...,p(m)) of (1,2,...,m), m=2n or m=2n+1, with p(m+1k) = m+1p(k) for 1<=k<=m, such that adjacent numbers do not differ by 1. a(n) is also the number of pointsymmetric arrangements of m nonattacking kings on an m X m board, with one in each row and column.


1



1, 0, 2, 14, 122, 1262, 15466, 219646, 3551194, 64431374, 1296712778, 28672204574, 691007296954, 18029138380846, 506320912190506, 15228632768870462, 488405396197019546, 16638380026019579726, 600022595692147574794, 22836184629309211495774, 914717041435012519583098
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

For m=2n+1 the symmetry requires p(n+1)=n+1. That is why the number of permutations is the same for m=2n and m=2n+1.
The nth element of any permutation is not allowed to be n because otherwise the next element would be n+1. Because of the symmetry it is sufficient to consider the first n elements. Any such ntuple can be created by a permutation of length n, last element smaller than n: Each element b(k) > n has to be replaced by m+1b(k).
Example m=6: Original symmetric permutation 536142, 3tuple 536 created by 231: 5 is replaced by 75 and 6 by 76.
How many such ntuples can be created by a npermutation?
Let us analyze the example above: There are two pairs of adjacent numbers (23 and 31) in the permutation 231. The difference of the first pair is 1, so either 2 or 3 must be replaced, whereas the second pair represents a "gap" (difference > 1), so that 1 can be kept or replaced by 6.
This way, 231 creates four 3tuples: 531, 241, 536, 246.
Let generally g be the number of gaps in a npermutation (0<=g<=n1). Then the number of related ntuples is 2^(g+1) because the first element of the permutation and each element behind a gap can be arbitrarily replaced or not. On the other hand, when the first element of a section between successive gaps is selected, there is no choice for the replacement of the other elements.
When q is a npermutation, the number of gaps is g(q) = Sum_{j=1..n1} sign(p(j+1)p(j)1). (sign = signum)
The extension up to n=50 was done by a new algorithm, see link "Fast recurrence".  Gerhard Kirchner, Mar 17 2017


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..400 (terms n = 0..50 from Gerhard Kirchner)
Gerhard Kirchner, Fast recurrence


FORMULA

Let q be any permutation (p(1), p(2),..., p(n)) with p(n) < n and g(q) = Sum_{j=1..n1} sgn(p(j+1)p(j)1).
a(n) = Sum_{each q} 2^(g(q)+1).
a(n) ~ exp(1) * 2^n * n!.  Vaclav Kotesovec, Apr 20 2017


EXAMPLE

Example 1, m=5:
The matrix, transforming 12345 into 41352, can also be thought of as a chessboard; each "1" is a king.
./0 0 0 1 0\ /1\ /4\
 1 0 0 0 0  2 1
 0 0 1 0 0 *3=3
 0 0 0 0 1  4 5
.\0 1 0 0 0/ \5/ \2/
Example 2, m=6:
q is a 3permutation not ending on 3:
q g(q) 2^(g(q)+1) Symmetric 6permutations, p(j+1)p(j)>1
132 1 4 135246, 635241, 142536, 642531
231 1 4 531642, 536142, 241635, 246135
312 1 4 315264, 362514, 462513, 415263
321 0 2 426153, 351624
Result: a(3)=14.


MAPLE

b:= proc(n, s, l) option remember; `if`(s={},
`if`(abs(n/2l)<1, 0, 1), add(add(`if`(abs(jl)=1, 0,
b(n, s minus {i}, i)), j=[i, ni]), i=s))
end:
a:= n> b(2*n+1, {$1..n}, 1):
seq(a(n), n=0..10); # Alois P. Heinz, Mar 15 2017
# second Maple program:
a:= proc(n) option remember; `if`(n<4, (n1)*
(7*n^25*n6)/6, (2*n+1)*a(n1) (2*n5)*
(a(n2)+a(n3)) +(2*n6)*a(n4))
end:
seq(a(n), n=0..20); # Alois P. Heinz, Mar 17 2017


MATHEMATICA

a[n_] := a[n] = If[n<4, (n1)*(7n^25n6)/6, (2n+1)*a[n1]  (2n5)*(a[n2] + a[n3]) + (2n6)*a[n4]]; Table[a[n], {n, 0, 20}] (* JeanFrançois Alcover, Mar 18 2017, after Alois P. Heinz *)


PROG

(VB)
a(n) = fusum(n, 1, "", "", 0, 0) with
Function fusum(n, t, permu$, pile$, g, su)
If t = n + 1 Then
su = su + 2 ^ (g + 1)
Else
la = n + 1  t
If t = 1 Then
la = n  1
For k = 1 To n: pile$ = pile$ + Chr(k): Next
End If
For s = la To 1 Step 1
y = Asc(Mid(pile$, s))
If t = 1 Then ad = 0 Else ad = Sgn(Abs(y  Asc(permu$))  1)
fusum = fusum(n, t + 1, Chr(y) + permu$, Left(pile$, s  1) + Mid(pile$, s + 1), g + ad, su)
Next
If t = n Then fusum = su
End If
End Function


CROSSREFS

Cf. A002464.
Sequence in context: A155728 A267906 A199560 * A319536 A060468 A349261
Adjacent sequences: A283181 A283182 A283183 * A283185 A283186 A283187


KEYWORD

nonn


AUTHOR

Gerhard Kirchner, Mar 02 2017


EXTENSIONS

a(14)a(20) from Alois P. Heinz, Mar 15 2017


STATUS

approved



