A252897 Rainbow Squares: a(n) = number of ways to pair the integers 1 to 2n so that the sum of each pair is a square.

1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 6, 18, 12, 36, 156, 295, 429, 755, 2603, 7122, 19232, 32818, 54363, 172374, 384053, 933748, 1639656, 4366714, 20557751, 83801506, 188552665, 399677820, 640628927, 2175071240, 8876685569, 32786873829, 108039828494, 351090349416

Offset: 0

Author

Gordon Hamilton, Mar 22 2015

Keywords

• nonn

Comments

The original sequence is from Henri Picciotto, who asked for which n is such a pairing possible: A253472.

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.

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

Examples

			One of the solutions for n=13 consists of the following pairings of 1-26:
  {1,15}, adding to 16;
  {2,23}, {3,22}, {4,21}, {5,20}, {6,19}, {7,18}, {8,17}, {9,16}, {11,14}, {12, 13}, each adding to 25;
  {10,26}, adding to 36;
  {24,25}, adding to 49.
There are five other such pairings possible, so a(13) = 6.
		

Links

• Martin Fuller, Table of n, a(n) for n = 0..42
• Gordon Hamilton, Kiran S. Kedlaya, and Henri Picciotto, Square-Sum Pair Partitions, The College Mathematics Journal, Vol. 46, No. 4 (September 2015), pp. 264-269.

Crossrefs

Cf. A253472, A278329, A278339.

Programs

Maple

F:= proc(S)
  option remember;
  local s, ts;
  if nops(S) = 0 then return 1 fi;
  s:= S[-1];
  ts:= select(t -> issqr(s+t),S minus {s});
  add(procname(S minus {s,t}), t = ts);
end proc:
seq(F({$1..2*n}), n = 0 .. 24); # Robert Israel, Mar 22 2015

Mathematica

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}]];
Table[Print[n]; F[Range[2 n]], {n, 0, 24}] (* Jean-François Alcover, Mar 19 2019, after Robert Israel *)

Extensions

a(26)-a(30) from Hiroaki Yamanouchi, Mar 25 2015

a(31) from Alois P. Heinz, Nov 16 2016

a(32)-a(36) from Linus and Joost VandeVondele, Jun 07 2018

a(37)-a(39) from Bert Dobbelaere, Aug 09 2022