A095986 A card-arranging problem: number of permutations p_1, ..., p_n of 1, ..., n such that i + p_i is a square for every i.

1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 2, 4, 3, 2, 5, 15, 21, 66, 37, 51, 144, 263, 601, 1333, 2119, 2154, 2189, 3280, 12405, 55329, 160895, 588081, 849906, 1258119, 1233262, 2478647, 4305500, 17278636, 47424179, 153686631, 396952852, 1043844982

Offset: 0

Author

Franklin T. Adams-Watters, Jul 18 2004

Keywords

• nonn
• hard
• more

Comments

Gardner attributes the problem (for the case n = 13) to David L. Silverman.

Examples

			a(0) = 1: the empty permutation.
a(3) = 1: 321.
a(5) = 1: 32154.
a(8) = 1: 87654321.
a(9) = 1: 826543917.
		

References

• M. Gardner, Mathematical Games column, Scientific American, Nov 1974.
• M. Gardner, Mathematical Games column, Scientific American, Mar 1975.
• M. Gardner, Time Travel and Other Mathematical Bewilderments. Freeman, NY, 1988, p. 81.

Crossrefs

Cf. A006063 (for cubes), A010052, A073364.

Programs

Maple

b:= proc(s) option remember; (n-> `if`(n=0, 1, add(
     `if`(issqr(n+j), b(s minus {j}), 0), j=s)))(nops(s))
    end:
a:= n-> b({$1..n}):
seq(a(n), n=0..25);  # Alois P. Heinz, Mar 03 2024

Mathematica

nmax=45; a[n_]:=Permanent[Table[If[IntegerQ[Sqrt[i+j]],1,0],{i,n},{j,n}]]; Join[{1},Array[a,nmax]] (* Stefano Spezia, Mar 03 2024 *)

Formula

a(n) = permanent(m), where the n X n matrix m is defined by m(i,j) = 1 or 0, depending on whether i+j is a square or not.

Extensions

a(32) and a(33) from John W. Layman, Jul 21 2004

a(34)-a(36) from Ray Chandler, Jul 26 2004

a(37)-a(45) from William Rex Marshall, Apr 18 2006

a(0)=1 prepended by Alois P. Heinz, Mar 03 2024