A293857 a(n) is the number of permutations {c_1..c_n} of {1..n} for which c_1 - c_2 + ... + (-1)^(n-1)*c_n are squares.

1, 1, 1, 4, 12, 36, 144, 1440, 9216, 66240, 504000, 7344000, 73612800, 830995200, 9373190400, 181875456000, 2474319052800, 38246274662400, 572552876851200, 13783143886848000, 237527801118720000, 4658378696294400000, 86818505051013120000, 2488457229932298240000

Offset: 0

Author

Vladimir Shevelev, Oct 17 2017

Keywords

• nonn

Comments

For a permutation C = {c_1..c_n} of {1..n}, set s(C) = c_1 - c_2 + ... + (-1)^(n-1)*c_n. Then max s(C) is square that is (ceil(n/2))^2 or A008794(n+1).

a(n)/n! is slowly and non-monotonically decreasing: 1, 1/2, 2/3, 1/2, 3/10, 1/5, 2/7, 8/35, 23/126, 5/36, 85/462, 71/462, ... .

Positions for which a(n) divisible by all primes <= n: 1, 4, 10, ... .

The smallest primes <= n not dividing a(n) or 0 if there is no such primes: 0, 2, 3, 0, 5, 5, 7, 5, 7, 0, 7, 7, ... .

Let k = floor(n / 2). Then a(n) = divisible by k! * (n-k)!. - David A. Corneth, Oct 18 2017. (For a proof, cf. comment in A293984. - Vladimir Shevelev, Nov 06 2017)

Examples

			Let n=3. For a permutation C={c_1,c_2,c_3}, set s = s(C) = c_1 - c_2 + c_3. We have the permutations:
1,2,3; s=2
1,3,2; s=0
2,1,3; s=4
2,3,1; s=0
3,1,2; s=4
3,2,1; s=2
Here there are 4 permutations for which {s} are squares. So a(3)=4.
		

Links

• Peter J. C. Moses, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A000290, A008794, A293783, A293984.

Programs

Maple

b:= proc(p, m, s) option remember; (n-> `if`(n=0, `if`(issqr(s), 1, 0),
      `if`(p>0, b(p-1, m, s+n), 0)+`if`(m>0, b(p, m-1, s-n), 0)))(p+m)
    end:
a:= n-> (t-> b(n-t, t, 0)*t!*(n-t)!)(iquo(n, 2)):
seq(a(n), n=0..28);  # Alois P. Heinz, Sep 17 2020

Mathematica

a293857=Table[Total[(Floor[n/2]!*(n-Floor[n/2])!)(Reverse[Map[SeriesCoefficient[QBinomial[n,Floor[(n+1)/2],q],{q,0,#}]&,Map[2#(Floor[(n+1)/2] - #)&,Range[0,Floor[(n+1)/4]]]]]
)],{n,25}] (* Peter J. C. Moses, Nov 01 2017 *)

Formula

From author's comment in A008794 it follows that a(n) >= A010551(n).

Extensions

a(5)-a(12) from Peter J. C. Moses, Oct 17 2017

a(13)-a(23) from David A. Corneth, Oct 17 2017

a(0)=1 prepended by Alois P. Heinz, Sep 17 2020