cp's OEIS Frontend

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+1-k) = m+1-p(k) for 1<=k<=m, such that adjacent numbers do not differ by 1. a(n) is also the number of point-symmetric arrangements of m non-attacking kings on an m X m board, with one in each row and column.

%I A283184 #48 Mar 02 2024 12:28:48
%S A283184 1,0,2,14,122,1262,15466,219646,3551194,64431374,1296712778,
%T A283184 28672204574,691007296954,18029138380846,506320912190506,
%U A283184 15228632768870462,488405396197019546,16638380026019579726,600022595692147574794,22836184629309211495774,914717041435012519583098
%N 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+1-k) = m+1-p(k) for 1<=k<=m, such that adjacent numbers do not differ by 1. a(n) is also the number of point-symmetric arrangements of m non-attacking kings on an m X m board, with one in each row and column.
%C A283184 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.
%C A283184 The n-th 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 n-tuple 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+1-b(k).
%C A283184 Example m=6: Original symmetric permutation 536142, 3-tuple 536 created by 231: 5 is replaced by 7-5 and 6 by 7-6.
%C A283184 How many such n-tuples can be created by a n-permutation?
%C A283184 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.
%C A283184 This way, 231 creates four 3-tuples: 531, 241, 536, 246.
%C A283184 Let generally g be the number of gaps in a n-permutation (0<=g<=n-1). Then the number of related n-tuples 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.
%C A283184 When q is a n-permutation, the number of gaps is g(q) = Sum_{j=1..n-1} sign(|p(j+1)-p(j)|-1). (sign = signum)
%C A283184 The extension up to n=50 was done by a new algorithm, see link "Fast recurrence". - _Gerhard Kirchner_, Mar 17 2017
%H A283184 Alois P. Heinz, <a href="/A283184/b283184.txt">Table of n, a(n) for n = 0..400</a> (terms n = 0..50 from Gerhard Kirchner)
%H A283184 Gerhard Kirchner, <a href="/A283184/a283184.txt">Fast recurrence</a>
%F A283184 Let q be any permutation (p(1), p(2),..., p(n)) with p(n) < n and g(q) = Sum_{j=1..n-1} sgn(|p(j+1)-p(j)|-1).
%F A283184 a(n) = Sum_{each q} 2^(g(q)+1).
%F A283184 a(n) ~ exp(-1) * 2^n * n!. - _Vaclav Kotesovec_, Apr 20 2017
%e A283184 Example 1, m=5:
%e A283184 The matrix, transforming 12345 into 41352, can also be thought of as a chessboard; each "1" is a king.
%e A283184 ./0 0 0 1 0\  /1\ /4\
%e A283184 | 1 0 0 0 0 | |2| |1|
%e A283184 | 0 0 1 0 0 |*|3|=|3|
%e A283184 | 0 0 0 0 1 | |4| |5|
%e A283184 .\0 1 0 0 0/  \5/ \2/
%e A283184 Example 2, m=6:
%e A283184 q is a 3-permutation not ending on 3:
%e A283184 q   g(q)  2^(g(q)+1) Symmetric 6-permutations, |p(j+1)-p(j)|>1
%e A283184 132   1        4        135246, 635241, 142536, 642531
%e A283184 231   1        4        531642, 536142, 241635, 246135
%e A283184 312   1        4        315264, 362514, 462513, 415263
%e A283184 321   0        2        426153, 351624
%e A283184 Result: a(3)=14.
%p A283184 b:= proc(n, s, l) option remember; `if`(s={},
%p A283184      `if`(abs(n/2-l)<1, 0, 1), add(add(`if`(abs(j-l)=1, 0,
%p A283184         b(n, s minus {i}, i)), j=[i, n-i]), i=s))
%p A283184     end:
%p A283184 a:= n-> b(2*n+1, {$1..n}, -1):
%p A283184 seq(a(n), n=0..10);  # _Alois P. Heinz_, Mar 15 2017
%p A283184 # second Maple program:
%p A283184 a:= proc(n) option remember; `if`(n<4, (n-1)*
%p A283184       (7*n^2-5*n-6)/6, (2*n+1)*a(n-1) -(2*n-5)*
%p A283184       (a(n-2)+a(n-3)) +(2*n-6)*a(n-4))
%p A283184     end:
%p A283184 seq(a(n), n=0..20);  # _Alois P. Heinz_, Mar 17 2017
%t A283184 a[n_] := a[n] = If[n<4, (n-1)*(7n^2-5n-6)/6, (2n+1)*a[n-1] - (2n-5)*(a[n-2] + a[n-3]) + (2n-6)*a[n-4]]; Table[a[n], {n, 0, 20}] (* _Jean-François Alcover_, Mar 18 2017, after _Alois P. Heinz_ *)
%o A283184 (Visual Basic)
%o A283184 a(n) = fusum(n, 1, "", "", 0, 0) with
%o A283184 Function fusum(n, t, permu$, pile$, g, su)
%o A283184 If t = n + 1 Then
%o A283184   su = su + 2 ^ (g + 1)
%o A283184 Else
%o A283184   la = n + 1 - t
%o A283184   If t = 1 Then
%o A283184     la = n - 1
%o A283184     For k = 1 To n: pile$ = pile$ + Chr(k): Next
%o A283184   End If
%o A283184   For s = la To 1 Step -1
%o A283184     y = Asc(Mid(pile$, s))
%o A283184     If t = 1 Then ad = 0 Else ad = Sgn(Abs(y - Asc(permu$)) - 1)
%o A283184     fusum = fusum(n, t + 1, Chr(y) + permu$, Left(pile$, s - 1) + Mid(pile$, s + 1), g + ad, su)
%o A283184   Next
%o A283184   If t = n Then fusum = su
%o A283184 End If
%o A283184 End Function
%o A283184 (PARI) a(n)={subst(serlaplace(polcoef((1 - x)/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)} \\ _Andrew Howroyd_, Mar 01 2024
%Y A283184 Cf. A002464.
%K A283184 nonn
%O A283184 0,3
%A A283184 _Gerhard Kirchner_, Mar 02 2017
%E A283184 a(14)-a(20) from _Alois P. Heinz_, Mar 15 2017