A281706 -id:A281706 - cp's OEIS frontend

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.

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

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

A176615 Number of edges in the graph on n vertices, labeled 1 to n, where two vertices are joined just if their labels sum to a perfect square.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15, 16, 17, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 49, 52, 55, 57, 59, 61, 63, 65, 68, 71, 74, 77, 80, 83, 86, 89, 91, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 127, 131, 135, 138, 141, 144, 147, 150

Offset: 1

Franklin T. Adams-Watters, Apr 21 2010

Equivalently, number of pairs of integers 0 < i < j <= n such that i + j is a square.

Suggested by R. K. Guy

			For n = 7 the graph contains the 4 edges 1-3, 2-7, 3-6, 4-5.

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A000196, A022554, A103128, A281706.

Column k=2 of A281871.

b:= n-> 1+floor(sqrt(2*n-1))-ceil(sqrt(n+1)):
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+b(n)) end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 30 2017

a[n_] := Sum[Floor[Sqrt[2k-1]] - Floor[Sqrt[k]], {k, 1, n}]; Table[a[n], {n, 1, 68}] (* Jean-François Alcover, Nov 04 2011, after Pari *)

a(n)=sum(k=1,sqrtint(n+1),ceil(k^2/2)-1)+sum(k=sqrtint(n+1)+1,sqrtint(2*n -1),n-floor(k^2/2))

a(n)=sum(k=1,n,sqrtint(2*k-1)-sqrtint(k))

Asymptotically, a(n) ~ (2*sqrt(2) - 2)/3 n^(3/2). The error term is probably O(n^(1/2)); O(n) is easily provable.

cp's OEIS Frontend

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

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

A176615 Number of edges in the graph on n vertices, labeled 1 to n, where two vertices are joined just if their labels sum to a perfect square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula