A278339 -id:A278339 - cp's OEIS frontend

A275780 Number of set partitions of [n] into blocks with distinct element sums.

1, 1, 2, 4, 12, 43, 160, 668, 3098, 15465, 83100, 477651, 2914505, 18795814, 127790544, 911448954, 6808162094, 53067398065, 430956571977, 3636314065247, 31841519540324, 288664242344692, 2706949104147162, 26205222185730884, 261681461422075548, 2691088457402830312

Offset: 0

Alois P. Heinz, Aug 08 2016

nonn

			a(3) = 4: 123, 13|2, 1|23, 1|2|3.
a(4) = 12: 1234, 123|4, 124|3, 12|34, 134|2, 13|24, 1|234, 1|23|4, 14|2|3, 1|24|3, 1|2|34, 1|2|3|4.

Gus Wiseman, Sequences counting and ranking multiset partitions whose part lengths, sums, or averages are constant or strict.

Cf. A000110, A007837, A035470, A038041, A275781, A278339, A300335, A321469, A326512, A326513, A326519, A326535.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],UnsameQ@@Total/@#&]],{n,0,10}] (* Gus Wiseman, Jul 13 2019 *)

a(n) = A000110(n) - A275781(n).

a(17)-a(25) from Christian Sievers, Aug 20 2024

A281871 Number T(n,k) of k-element subsets of [n] having a square element sum; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 2, 0, 0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 4, 5, 5, 2, 1, 0, 1, 2, 5, 8, 8, 6, 3, 0, 1, 1, 3, 6, 11, 14, 13, 7, 4, 1, 0, 1, 3, 7, 15, 23, 24, 19, 10, 3, 1, 0, 1, 3, 8, 20, 34, 43, 39, 25, 13, 3, 1, 0, 1, 3, 9, 26, 49, 71, 74, 60, 34, 14, 5, 0, 0

Offset: 0

Alois P. Heinz, Jan 31 2017

			T(7,0) = 1: {}.
T(7,1) = 2: {1}, {4}.
T(7,2) = 4: {1,3}, {2,7}, {3,6}, {4,5}.
T(7,3) = 5: {1,2,6}, {1,3,5}, {2,3,4}, {3,6,7}, {4,5,7}.
T(7,4) = 5: {1,2,6,7}, {1,3,5,7}, {1,4,5,6}, {2,3,4,7}, {2,3,5,6}.
T(7,5) = 2: {1,2,3,4,6}, {3,4,5,6,7}.
T(7,6) = 1: {1,2,4,5,6,7}.
T(7,7) = 0.
T(8,8) = 1: {1,2,3,4,5,6,7,8}.
Triangle T(n,k) begins:
  1;
  1, 1;
  1, 1, 0;
  1, 1, 1,  0;
  1, 2, 1,  1,  0;
  1, 2, 2,  2,  0,  0;
  1, 2, 3,  3,  2,  1,  0;
  1, 2, 4,  5,  5,  2,  1,  0;
  1, 2, 5,  8,  8,  6,  3,  0,  1;
  1, 3, 6, 11, 14, 13,  7,  4,  1,  0;
  1, 3, 7, 15, 23, 24, 19, 10,  3,  1, 0;
  1, 3, 8, 20, 34, 43, 39, 25, 13,  3, 1, 0;
  1, 3, 9, 26, 49, 71, 74, 60, 34, 14, 5, 0, 0;
  ...

Alois P. Heinz, Rows n = 0..200, flattened

Columns k=0-10 give: A000012, A000196, A176615, A281706, A281864, A281865, A281866, A281867, A281868, A281869, A281870.
Main diagonal is characteristic function of A001108.
Diagonals T(n+k,n) for k=2-10 give: A281965, A281966, A281967, A281968, A281969, A281970, A281971, A281972, A281973.
Row sums give A126024.
T(2n,n) gives A281872.
Cf. A000217, A000290, A007318, A214857, A214858, A278339, A281994, A284249, A377572.

b:= proc(n, s) option remember; expand(`if`(n=0,
      `if`(issqr(s), 1, 0), b(n-1, s)+x*b(n-1, s+n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..16);

b[n_, s_] := b[n, s] = Expand[If[n == 0, If[IntegerQ @ Sqrt[s], 1, 0], b[n - 1, s] + x*b[n - 1, s + n]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, n}]][b[n, 0]];
Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jun 03 2018, from Maple *)

T(n,n) = 1 for n in { A001108 }, T(n,n) = 0 otherwise.
T(n,n-1) = 1 for n in { A214857 }, T(n,n-1) = 0 for n in { A214858 }.
Sum_{k=0..n} k * T(n,k) = A377572(n).

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.

Original entry on oeis.org

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

Gordon Hamilton, Mar 22 2015

nonn

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

			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.

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.

Cf. A253472, A278329, A278339.

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

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

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

A278329 Number of set partitions of [3n] into n subsets of size three such that all element sums are squares.

Original entry on oeis.org

1, 0, 0, 0, 0, 29, 35, 340, 26579, 390480, 9514434, 145963193, 5474045270, 87251356528, 5454606723223, 182600931998737, 5059541554893941

Offset: 0

Alois P. Heinz, Nov 18 2016

			a(5) = 29: {{1,3,5}, {2,9,14}, {4,6,15}, {7,8,10}, {11,12,13}},
  {{1,3,5}, {2,11,12}, {4,6,15}, {7,8,10}, {9,13,14}},
  {{1,2,6}, {3,7,15}, {4,8,13}, {5,9,11}, {10,12,14}},
  {{1,2,6}, {3,7,15}, {4,10,11}, {5,8,12}, {9,13,14}},
  {{1,3,5}, {2,8,15}, {4,7,14}, {6,9,10}, {11,12,13}},
  {{1,3,5}, {2,8,15}, {4,10,11}, {6,7,12}, {9,13,14}},
  {{1,9,15}, {2,3,4}, {5,6,14}, {7,8,10}, {11,12,13}},
  {{1,9,15}, {2,3,4}, {5,7,13}, {6,8,11}, {10,12,14}},
  {{1,2,6}, {3,9,13}, {4,7,14}, {5,8,12}, {10,11,15}},
  {{1,2,6}, {3,8,14}, {4,9,12}, {5,7,13}, {10,11,15}},
  {{1,3,5}, {2,9,14}, {4,8,13}, {6,7,12}, {10,11,15}},
  {{1,3,12}, {2,6,8}, {4,5,7}, {9,13,14}, {10,11,15}},
  {{1,11,13}, {2,3,4}, {5,6,14}, {7,8,10}, {9,12,15}},
  {{1,3,5}, {2,10,13}, {4,7,14}, {6,8,11}, {9,12,15}},
  {{1,2,6}, {3,8,14}, {4,10,11}, {5,7,13}, {9,12,15}},
  {{1,10,14}, {2,3,4}, {5,7,13}, {6,8,11}, {9,12,15}},
  {{1,2,6}, {3,10,12}, {4,7,14}, {5,9,11}, {8,13,15}},
  {{1,3,5}, {2,11,12}, {4,7,14}, {6,9,10}, {8,13,15}},
  {{1,3,5}, {2,9,14}, {4,10,11}, {6,7,12}, {8,13,15}},
  {{1,10,14}, {2,3,4}, {5,9,11}, {6,7,12}, {8,13,15}},
  {{1,6,9}, {2,3,11}, {4,5,7}, {8,13,15}, {10,12,14}},
  {{1,4,11}, {2,5,9}, {3,6,7}, {8,13,15}, {10,12,14}},
  {{1,2,6}, {3,10,12}, {4,8,13}, {5,9,11}, {7,14,15}},
  {{1,3,5}, {2,11,12}, {4,8,13}, {6,9,10}, {7,14,15}},
  {{1,2,6}, {3,9,13}, {4,10,11}, {5,8,12}, {7,14,15}},
  {{1,3,5}, {2,10,13}, {4,9,12}, {6,8,11}, {7,14,15}},
  {{1,11,13}, {2,3,4}, {5,8,12}, {6,9,10}, {7,14,15}},
  {{1,6,9}, {2,4,10}, {3,5,8}, {7,14,15}, {11,12,13}},
  {{1,5,10}, {2,6,8}, {3,4,9}, {7,14,15}, {11,12,13}}.

Cf. A000290, A252897, A278339, A281706, A295946.

A278329[0] = 1;
A278329[n_] := Length@FindClique[Graph[First@# <-> Last@# & /@ Select[Subsets[Select[Flatten[IntegerPartitions[#^2, {3}, Range[3 n]] & /@ Range[Sqrt[9 n - 3]], 1], DuplicateFreeQ], {2}], DuplicateFreeQ@Flatten@# &]], {n}, All] (* Davin Park, Jan 26 2017 *)

a(12)-a(13) from Bert Dobbelaere, Apr 12 2019

a(14)-a(16) from Martin Fuller, Jul 08 2025

A278340 Number of partitions of n*(n+1)/2 into distinct squares.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 0, 1, 2, 1, 3, 4, 3, 4, 4, 3, 4, 9, 14, 18, 19, 8, 16, 25, 27, 47, 37, 55, 83, 66, 92, 100, 108, 214, 189, 201, 303, 334, 535, 587, 587, 689, 764, 908, 1278, 1494, 1904, 2369, 2744, 2970, 3269, 3805, 4780, 6701, 7744, 9120, 10582, 11082

Offset: 0

Alois P. Heinz, Nov 18 2016

nonn

			a(9) = 2: [25,16,4], [36,9].
a(10) = 1: [25,16,9,4,1].
a(11) = 3: [36,16,9,4,1], [36,25,4,1], [49,16,1].
a(12) = 4: [36,25,16,1], [49,16,9,4], [49,25,4], [64,9,4,1]

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000217, A000290, A033461, A278339.

b:= proc(n, i) option remember; (m-> `if`(n>m, 0,
      `if`(n=m, 1, b(n, i-1)+ `if`(i^2>n, 0,
         b(n-i^2, i-1)))))(i*(i+1)*(2*i+1)/6)
    end:
a:= n-> (m-> b(m, isqrt(m)))(n*(n+1)/2):
seq(a(n), n=0..80);

b[n_, i_] := b[n, i] = (If[n > #, 0, If[n == #, 1, b[n, i - 1] + If[i^2 > n, 0, b[n - i^2, i - 1]]]]) &[i*(i + 1)*(2*i + 1)/6];
a[n_] := b[#, Floor @ Sqrt[#]] &[n*(n + 1)/2];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, May 20 2018, translated from Maple *)

a(n) = [x^(n*(n+1)/2)] Product_{i>=1} (1+x^(i^2)).

a(n) = A033461(A000217(n)).

A281994 Number of set partitions of [n] into subsets whose element sums are squares.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 1, 7, 37, 22, 264, 310, 1181, 2350, 8102, 38471, 136528, 738072, 2811383, 12163208, 45121906, 160620225, 729516611, 3962353196

Offset: 0

Alois P. Heinz, Feb 04 2017

nonn

			a(0) = 1: {}.
a(1) = 1: 1.
a(4) = 1: 1|234.
a(6) = 1: 1|2356|4.
a(7) = 1: 1|27|36|45.
a(8) = 7: 12345678, 1258|367|4, 1267|358|4, 1357|268|4, 13|268|457, 178|2356|4, 18|27|36|45.
a(10) = 22: 1|234|5678(10)|9, 1|23569|4|78(10), 1|2356|4|78(10)|9, 1|23578|4|69(10), 1|23578|4|6(10)|9, 1|23678(10)|45|9, 1|24578(10)|36|9, 1|27|34568(10)|9, 1|258(10)|3679|4, 1|258(10)|367|4|9, 1|258(10)|36|4|79, 1|259|36|4|78(10), 1|267(10)|3589|4, 1|267(10)|358|4|9, 1|2689|357(10)|4, 1|268|357(10)|4|9, 1|27|3589|4|6(10), 1|27|358|4|69(10), 1|27|358|4|6(10)|9, 1|2789(10)|36|45, 1|27|3689(10)|45, 1|27|36|4589(10).

Cf. A000110, A278339, A281871.

cp's OEIS Frontend

A275780 Number of set partitions of [n] into blocks with distinct element sums.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A281871 Number T(n,k) of k-element subsets of [n] having a square element sum; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A278329 Number of set partitions of [3n] into n subsets of size three such that all element sums are squares.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Extensions

A278340 Number of partitions of n*(n+1)/2 into distinct squares.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A281994 Number of set partitions of [n] into subsets whose element sums are squares.

Views

Author

Keywords

Examples

Crossrefs