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,15

Comments

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

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.

Links

Table of n, a(n) for n=0..45.

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.

Example

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

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 *)

Crossrefs

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

Sequence in context: A329876 A128868 A341073 * A212637 A283273 A269599

Adjacent sequences: A095983 A095984 A095985 * A095987 A095988 A095989

Keyword

nonn,hard,more

Author

Franklin T. Adams-Watters, Jul 18 2004

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

Status

approved