login
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.
5

%I #34 Mar 09 2024 10:31:41

%S 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,

%T 1333,2119,2154,2189,3280,12405,55329,160895,588081,849906,1258119,

%U 1233262,2478647,4305500,17278636,47424179,153686631,396952852,1043844982

%N 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.

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

%D M. Gardner, Mathematical Games column, Scientific American, Nov 1974.

%D M. Gardner, Mathematical Games column, Scientific American, Mar 1975.

%D M. Gardner, Time Travel and Other Mathematical Bewilderments. Freeman, NY, 1988, p. 81.

%F 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.

%e a(0) = 1: the empty permutation.

%e a(3) = 1: 321.

%e a(5) = 1: 32154.

%e a(8) = 1: 87654321.

%e a(9) = 1: 826543917.

%p b:= proc(s) option remember; (n-> `if`(n=0, 1, add(

%p `if`(issqr(n+j), b(s minus {j}), 0), j=s)))(nops(s))

%p end:

%p a:= n-> b({$1..n}):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Mar 03 2024

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

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

%K nonn,hard,more

%O 0,15

%A _Franklin T. Adams-Watters_, Jul 18 2004

%E a(32) and a(33) from _John W. Layman_, Jul 21 2004

%E a(34)-a(36) from _Ray Chandler_, Jul 26 2004

%E a(37)-a(45) from _William Rex Marshall_, Apr 18 2006

%E a(0)=1 prepended by _Alois P. Heinz_, Mar 03 2024