A069999 -id:A069999 - cp's OEIS frontend

A354468 Number of possible ordered pairs (n_1, S) where (n_1, n_2, ..., n_k) is a partition of n, n_1 is the largest element of the partition, and S = Sum_{j=1..k} n_j^2.

1, 1, 2, 3, 5, 7, 11, 15, 22, 29, 39, 50, 66, 83, 104, 127, 157, 188, 225, 265, 312, 359, 418, 479, 547, 620, 700, 786, 884, 987, 1094, 1214, 1348, 1479, 1627, 1779, 1945, 2122, 2313, 2505, 2719, 2934, 3161, 3412, 3666, 3932, 4218, 4511, 4820, 5140, 5477, 5825

Offset: 0

Noah A Rosenberg, Jun 02 2022

nonn

In categorical data with a sample of size n distributed over at least 1 and at most n distinct categorical types, if a dataset is summarized by an ordered pair of two numbers -- the number of observations of the most frequent type and the sum of squares of the frequencies of all types -- then a(n) gives the number of distinguishable ordered pairs across all possible datasets.

			For n=4 the a(4)=5 ordered pairs are (4,16), (3,10), (2,8), (2,6), and (1,4).

Noah A. Rosenberg, Mathematical Properties of Population-Genetic Statistics, Princeton University Press, 2025, page 112.

Alois P. Heinz, Table of n, a(n) for n = 0..800
Noah A. Rosenberg and Donna M. Zulman, Measures of care fragmentation: mathematical insights from population genetics, Health Services Research 55 (2020), 318-327.

Bounded below by A069999. Bounded above by A000041 and by A000125(n-1).

Cf. A354800.

b:= proc(n, i) option remember; `if`(n=0 or i=1, {n},
     {b(n, i-1)[], map(x-> x+i^2, b(n-i, min(n-i, i)))[]})
    end:
a:= n-> add(nops(b(n-i, min(n-i, i))), i=signum(n)..n):
seq(a(n), n=0..60);  # Alois P. Heinz, Jun 02 2022

b[n_, i_] := b[n, i] = If[n == 0 || i == 1, {n},
     Union@Flatten@{b[n, i-1], #+i^2& /@ b[n-i, Min[n-i, i]]}];
a[n_] := Sum[Length[b[n-i, Min[n-i, i]]], {i, Sign[n], n}];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 05 2022, after Alois P. Heinz *)

a(16)-a(51) from Alois P. Heinz, Jun 02 2022

A354800 Cardinality of the set of ordered pairs (m(lambda),f(lambda)), where lambda ranges over all partitions of n and m gives the infimum and f gives the sum of the squares of the argument.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 13, 20, 26, 33, 41, 55, 63, 77, 93, 111, 129, 160, 180, 209, 240, 280, 312, 356, 397, 453, 498, 560, 614, 680, 758, 831, 901, 994, 1087, 1179, 1280, 1389, 1495, 1629, 1745, 1868, 2022, 2159, 2296, 2485, 2650, 2809, 2991, 3181, 3377, 3600

Offset: 0

Alois P. Heinz, Jun 06 2022

nonn

			a(0) = 1 = |{(infinity,0)}|.
a(1) = 1 = |{(1,1)}|.
a(2) = 2 = |{(1,2), (2,4)}|.
a(3) = 3 = |{(1,3), (1,5), (3,9)}|.
a(4) = 5 = |{(1,4), (1,6), (1,10), (2,8), (4,16)}|.
a(5) = 7 = |{(1,5), (1,7), (1,9), (1,11), (1,17), (2,13), (5,25)}|.

Alois P. Heinz, Table of n, a(n) for n = 0..700
Wikipedia, Infima and suprema of real numbers
Wikipedia, Partition (number theory)

Cf. A069999 (lower bound), A354468 (the same for supremum).

a:= n-> nops({map(l-> [min(l), add(i^2, i=l)], combinat[partition](n))[]}):
seq(a(n), n=0..40);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(n x+i^2, b(n-i, i))[]}))
    end:
a:= n-> add(nops(b(n-i, i)), i=signum(n)..n):
seq(a(n), n=0..60);

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[n < i, {}, Union@ Flatten@ {b[n, i + 1], # + i^2& /@ b[n - i, i]}]];
a[n_] :=  Sum[Length[b[n - i, i]], {i, Sign[n], n}];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jul 06 2022, after Alois P. Heinz *)

A111212 Number of distinct integers d(pi), where pi ranges over all partitions of n into distinct parts and d(pi) = sum of squares of parts of pi.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 10, 12, 12, 18, 20, 23, 27, 35, 32, 46, 48, 55, 59, 79, 74, 94, 101, 110, 127, 144, 134, 172, 180, 189, 205, 235, 237, 266, 282, 303, 323, 352, 346, 391, 403, 436, 453, 497, 492, 547, 555, 596, 606, 661, 670, 724, 741, 775, 806, 861

Offset: 0

Vladeta Jovovic, Oct 25 2005

			The 8 partitions of 9 into distinct parts have these sums of squares:  81, 65, 53, 45, 41, 41, 35, 29, where 41 = 6^2 + 2^2 + 1^2 = 5^2 + 4^2, so that a(9) = 7. - _Clark Kimberling_, Apr 13 2014

Alois P. Heinz, Table of n, a(n) for n = 0..500 (first 301 terms from Joerg Arndt)

Cf. A000009, A069999.

seq(`if`(m=2, 1, nops(simplify(coeff(series(mul(1+x^(k^2)*y^k, k=1..61), y, 61), y, m)))), m=0..60);
# second Maple program:
b:= proc(n, i) option remember; `if`(i*(i+1)/2x+i^2, b(n-i, min(n-i, i-1)))[]}))
    end:
a:= n-> nops(b(n$2)):
seq(a(n), n=0..65); # Alois P. Heinz, Apr 18 2019

z = 40; g[n_] := n^2; q[n_] := q[n] = Select[IntegerPartitions[n], Max[Length /@ Split@#] == 1 &]; Map[Length, Map[Union, Table[Total[Map[g, q[n][[k]]]], {n, 1, z}, {k, 1, PartitionsQ[n]}]]] (* Clark Kimberling, Apr 13 2014 *)
terms = 60; s = (Product[1+x^k^2*y^k, {k, terms}] + O[y]^terms) + O[x]^terms^2; Join[{1, 1}, Length /@ CoefficientList[s, y][[3 ;; terms]]] (* Jean-François Alcover, Jan 29 2018, adapted from Maple *)

Corrected term a(2), Joerg Arndt, Apr 18 2019

A309838 a(n) = number of dimensions of semisimple matrix subalgebras.

Original entry on oeis.org

2, 4, 7, 11, 16, 22, 29, 39, 50, 60, 73, 88, 103, 120, 139, 160, 181, 203, 229, 256, 284, 313, 343, 377, 412, 448, 487, 528, 569, 610, 653, 699, 748, 797, 849, 904, 959, 1014, 1070, 1129, 1191, 1255, 1321, 1388, 1456, 1526, 1598, 1672, 1746, 1821, 1899, 1981, 2064

Offset: 1

Phillip Heikoop, Aug 19 2019

nonn

a(n) = |A_n| in the Heikoop paper.

A semisimple matrix subalgebra of M_n(k) for an algebraically closed field k is a direct sum of M_n_i(k) such that Sum (n_i) <= n. See Heikoop paper, Section 3.2, for more.

Phillip Heikoop, Table of n, a(n) for n = 1..336
Phillip Tomas Heikoop, Dimensions of Matrix Subalgebras, Bachelor's Thesis, Worcester Polytechnic Institute (2019).
Phillip Heikoop, C++11 code to generate the sequence

Cf. A000124, A002620, A069999, A138544, A309839.

a(n) <= n^2 - Sqrt(2) * Sqrt(2n+ 3) * n.

A309839 a(n) = GAP_n: first integer m that is not the dimension of a semisimple subalgebra of M_n(k).

Original entry on oeis.org

3, 6, 7, 12, 15, 22, 23, 42, 43, 48, 63, 76, 79, 96, 115, 140, 143, 166, 167, 192, 247, 248, 279, 312, 347, 384, 423, 472, 483, 526, 527, 572, 619, 624, 719, 724, 827, 832, 889, 948, 1009, 1072, 1087, 1152, 1219, 1288, 1359, 1432, 1507, 1520, 1597, 1676, 1679

Offset: 2

Phillip Heikoop, Aug 19 2019

nonn

Define the sequence a(n) = GAP_n to be the smallest integer that is not the dimension of a semisimple subalgebra of M_n(k). This is one more than the upper endpoint of the continuous region of M_n(k). Because when n = 1 there are no gaps, this sequence begins at n = 2. See Heikoop paper, page 31.

Michael De Vlieger, Table of n, a(n) for n = 2..101
Phillip Tomas Heikoop, Dimensions of Matrix Subalgebras, Bachelor's Thesis, Worcester Polytechnic Institute (2019).
Phillip Heikoop, C++11 code to generate the sequence

Cf. A000124, A002620, A069999, A138544, A309838.

a(n) > n^2 - 4 * sqrt(n + 2).

A132193 Triangle whose n-th row is the list in increasing order of the integers which are the sum of squares of positive integers with sum n. The n-th row begins with n and ends with n^2.

Original entry on oeis.org

0, 1, 2, 4, 3, 5, 9, 4, 6, 8, 10, 16, 5, 7, 9, 11, 13, 17, 25, 6, 8, 10, 12, 14, 18, 20, 26, 36, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 37, 49, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 38, 40, 50, 64, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 39, 41, 45, 51, 53, 65, 81

Offset: 0

Roger Cuculière, Nov 05 2007

The n-th row is the list of possible dimensions of the commutant space of an n X n matrix A, i.e. the set of matrices M such that A*M=M*A. The number of elements in the n-th row is given by the sequence A069999. - Corrected by Ricardo C. Santamaria, Nov 08 2012

			T(4,1)=4 because 4=1+1+1+1 and 1^2+1^2+1^2+1^2=4 ; T(4,2)=6 because 4=2+1+1 and 2^2+1^2+1^2=6.
Triangle T(n,k) begins:
  0;
  1;
  2, 4;
  3, 5,  9;
  4, 6,  8, 10, 16;
  5, 7,  9, 11, 13, 17, 25;
  6, 8, 10, 12, 14, 18, 20, 26, 36;
  7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 37, 49;
  ...

Alois P. Heinz, Rows n = 0..50, flattened (first 1000 terms from Jean-François Alcover)

Cf. A069999.

b:= proc(n, i) option remember; `if`(n=0 or i=1, {n},
     {b(n, i-1)[], map(x-> x+i^2, b(n-i, min(n-i, i)))[]})
    end:
T:= n-> sort([b(n$2)[]])[]:
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 06 2022

selQ[n_][p_] := MemberQ[#.# & /@ IntegerPartitions[n], p]; row[n_] := Select[Range[n, n^2], selQ[n] ]; Table[row[n], {n, 1, 10}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)

More terms from Ricardo C. Santamaria, Nov 08 2012

Row n=0 prepended by Alois P. Heinz, Jun 06 2022

A306597 a(n) = Card({ Sum_{k=1..n}(x_k * k) : (x_k){k=1..n} is an n-tuple of nonnegative integers such that Sum{k=1..n}(x_k * T_k) = T_n }), where T_k denotes the k-th triangular number.

Original entry on oeis.org

1, 2, 4, 6, 9, 15, 20, 27, 34, 43, 52, 63, 75, 87, 102, 117, 132, 149, 166, 185, 206, 226, 248, 271, 294, 318, 345, 373, 399, 429, 459, 489, 520, 554, 587, 623, 658, 695, 734, 772, 811, 853, 894, 936, 981, 1026, 1072, 1119, 1167, 1215, 1266, 1316, 1368, 1420

Offset: 1

Luc Rousseau, Feb 27 2019

nonn

Inspired by the questions:
- Q1: into how many regions do n+1 straight lines divide the plane?
- Q2: what is the number of possible answers to Q1?
This sequence provides an answer to an analog of Q2 in a modified version of the problem.
Also an analog of A069999(n) with the roles of k and T_k swapped in the definition.

			When n = 3, n*(n+1)/2 = 6. All possible ways to partition 6 into parts with triangular sizes (1, 3, 6) are:
  0*1 + 0*3 + 1*6 = 6
  0*1 + 2*3 + 0*6 = 6
  3*1 + 1*3 + 0*6 = 6
  6*1 + 0*3 + 0*6 = 6
In the above products, keep the left multiplicands and replace the right ones with their triangular roots:
  0*1 + 0*2 + 1*3 = 3
  0*1 + 2*2 + 0*3 = 4
  3*1 + 1*2 + 0*3 = 5
  6*1 + 0*2 + 0*3 = 6
Card({ 3, 4, 5, 6 }) = 4, so a(3) = 4.

Luc Rousseau, Table of n, a(n) for n = 1..150
Luc Rousseau, C program
Luc Rousseau, Java program (standalone version)
Luc Rousseau, Java program (jOEIS version, github)

Cf. A177862, A072964, A069999.

T[n_] := n*(n + 1)/2
R[n_] := (Sqrt[8*n + 1] - 1)/2
S[0] := 0
S[d_] := S[d] =
  Module[{r = R[d]},
   If[IntegerQ[r], r++; r + T[r],
    First@TakeSmallest[
       1]@(S[#[[1]]] + S[#[[2]]] & /@ IntegerPartitions[d, {2}])]]
A0[n_] := Sum[Boole[d + S[d] <= 2*n], {d, 0, n}]
A[n_] := A0[T[n]]
For[n = 1, n <= 150, n++, Print[n, " ", A[n]]]

A381811 The largest nonnegative integer j for which each integer n,n+2,...,n+2j can be written as the sum of the squares for some partition of n.

Original entry on oeis.org

0, 1, 1, 3, 4, 4, 7, 13, 13, 18, 25, 25, 32, 32, 40, 49, 52, 62, 73, 85, 102, 112, 127, 133, 160, 166, 166, 184, 203, 208, 228, 249, 271, 294, 322, 343, 373, 376, 376, 403, 431, 490, 521, 521, 553, 592, 620, 655, 662, 662, 735, 735, 773, 812, 852, 893, 901, 943, 986

Offset: 1

Noah A Rosenberg, May 05 2025

nonn

a(n) has an asymptotic equivalence with (1/2)*n^2-sqrt(2)*n^(3/2)+O(n^(5/4)) (Reznick 1989, p. 201).

			a(3) = 1, because n, n+2 (3 and 5) can be written as the sum of the squares for some partition of n; 3=1^2+1^2+1^2 and 5=2^2+1^2. However, 7 cannot be written as the sum of squares of the parts of a partition of 3, so a(3) = 1.
a(4) = 3, because n, n+2, n+4 and n+6 (4, 6, 8 and 10) can be written as the sum of the squares for some partition of n; 4=1^2+1^2+1^2+1^2, 6=2^2+1^2+1^2, 8=2^2+2^2, and 10=3^2+1^2. However, 12 cannot be written as the sum of squares of the parts of a partition of 4, so a(4) = 3.

B. Reznick, The sum of the squares of the parts of a partition, and some related questions, J. Number Theory 33 (1989), 199-208.
P. Winkler, Mean distance in a tree, Discr. Appl. Math. (1990), 179-185.

Cf. A069999 (a(n) provides a lower bound for A069999(n)).

Cf. A000041, A383682.

a(n) = (A383682(n) - n) / 2.

cp's OEIS Frontend

A354468 Number of possible ordered pairs (n_1, S) where (n_1, n_2, ..., n_k) is a partition of n, n_1 is the largest element of the partition, and S = Sum_{j=1..k} n_j^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A354800 Cardinality of the set of ordered pairs (m(lambda),f(lambda)), where lambda ranges over all partitions of n and m gives the infimum and f gives the sum of the squares of the argument.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A111212 Number of distinct integers d(pi), where pi ranges over all partitions of n into distinct parts and d(pi) = sum of squares of parts of pi.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A309838 a(n) = number of dimensions of semisimple matrix subalgebras.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A309839 a(n) = GAP_n: first integer m that is not the dimension of a semisimple subalgebra of M_n(k).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A132193 Triangle whose n-th row is the list in increasing order of the integers which are the sum of squares of positive integers with sum n. The n-th row begins with n and ends with n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A306597 a(n) = Card({ Sum_{k=1..n}(x_k * k) : (x_k){k=1..n} is an n-tuple of nonnegative integers such that Sum{k=1..n}(x_k * T_k) = T_n }), where T_k denotes the k-th triangular number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A381811 The largest nonnegative integer j for which each integer n,n+2,...,n+2j can be written as the sum of the squares for some partition of n.

Views

Author

Keywords

Comments

Examples

Links