%I #54 May 31 2024 22:04:09
%S 1,0,0,0,1,0,0,1,1,1,0,0,1,6,18,12,36,156,295,429,755,2603,7122,19232,
%T 32818,54363,172374,384053,933748,1639656,4366714,20557751,83801506,
%U 188552665,399677820,640628927,2175071240,8876685569,32786873829,108039828494
%N Rainbow Squares: a(n) = number of ways to pair the integers 1 to 2n so that the sum of each pair is a square.
%C The original sequence is from Henri Picciotto, who asked for which n is such a pairing possible: A253472.
%C The name "rainbow squares" refers to the use of this problem in the elementary school classroom where children draw colored connecting "rainbows" to make the pairings.
%C Number of perfect matchings in the graph with vertices 1 to 2n and edges {i,j} where i+j is a square. - _Robert Israel_, Mar 22 2015
%H Gordon Hamilton, Kiran S. Kedlaya, and Henri Picciotto, <a href="https://www.maa.org/sites/default/files/pdf/awards/college.math.j.46.4.264.pdf">Square-Sum Pair Partitions</a>, The College Mathematics Journal, Vol. 46, No. 4 (September 2015), pp. 264-269.
%e One of the solutions for n=13 consists of the following pairings of 1-26:
%e {1,15}, adding to 16;
%e {2,23}, {3,22}, {4,21}, {5,20}, {6,19}, {7,18}, {8,17}, {9,16}, {11,14}, {12, 13}, each adding to 25;
%e {10,26}, adding to 36;
%e {24,25}, adding to 49.
%e There are five other such pairings possible, so a(13) = 6.
%p F:= proc(S)
%p option remember;
%p local s, ts;
%p if nops(S) = 0 then return 1 fi;
%p s:= S[-1];
%p ts:= select(t -> issqr(s+t),S minus {s});
%p add(procname(S minus {s,t}), t = ts);
%p end proc:
%p seq(F({$1..2*n}), n = 0 .. 24); # _Robert Israel_, Mar 22 2015
%t F[S_] := F[S] = Module[{s, ts}, If[Length[S] == 0, Return[1]]; s = S[[-1]]; ts = Select[S ~Complement~ {s}, IntegerQ[Sqrt[s + #]]&]; Sum[F[S ~Complement~ {s, t}], {t, ts}]];
%t Table[Print[n]; F[Range[2 n]], {n, 0, 24}] (* _Jean-François Alcover_, Mar 19 2019, after _Robert Israel_ *)
%Y Cf. A253472, A278329, A278339.
%K nonn,more
%O 0,14
%A _Gordon Hamilton_, Mar 22 2015
%E a(26)-a(30) from _Hiroaki Yamanouchi_, Mar 25 2015
%E a(31) from _Alois P. Heinz_, Nov 16 2016
%E a(32)-a(36) from Linus and _Joost VandeVondele_, Jun 07 2018
%E a(37)-a(39) from _Bert Dobbelaere_, Aug 09 2022