A366429 a(n) = maximum degree of vertices in the distance graph of the partitions of n.

0, 1, 2, 3, 4, 6, 7, 8, 8, 12, 13, 14, 14, 15, 20, 21, 22, 22, 23, 23, 30, 31, 32, 32, 33, 33, 34, 42, 43, 44, 44, 45, 45, 46, 46, 56, 57, 58, 58, 59, 59, 60, 60, 60, 72, 73, 74, 74, 75, 75, 76, 76, 76, 77, 90, 91, 92, 92, 93, 93, 94, 94, 94, 95, 95, 110, 111

Offset: 1

Author

Clark Kimberling, Oct 12 2023

Keywords

• nonn

Comments

The distance graph of the partitions of n is defined by its edges, specifically, two partitions (i.e. vertices) p and q share an edge if d(p,q) = 2, where d is defined in A366156.

Examples

			Enumerate the 7 partitions (= vertices) of 5 as follows:
  1: 5
  2: 4,1
  3: 3,2
  4: 3,1,1
  5: 2,2,1
  6: 2,1,1,1
  7: 1,1,1,1,1
Call q a neighbor of p if d(p,q)=2. The set of neighbors for vertex k, for k = 1..7, is given by
  vertex 1: {2}
  vertex 2: {1,3,4}
  vertex 3: {2,4,5}
  vertex 4: {2,3,5,6}
  vertex 5: {3,4,6}
  vertex 6: {4,5,7}
  vertex 7: {6}
The maximal degree is 4, which is the degree of vertex 4, so that a(5) = 4.
		

Crossrefs

Cf. A000041, A000097 (number of edges in distance graphs), A000267, A002024, A002262, A366156, A366461.

Programs

Mathematica

c[n_] := PartitionsP[n];
q[n_, k_] := q[n, k] = IntegerPartitions[n][[k]];
r[n_, k_] := r[n, k] = Join[q[n, k], ConstantArray[0, n - Length[q[n, k]]]];
d[u_, v_] := d[u, v] = Total[Abs[u - v]];
s[n_, k_] := s[n, k] = Select[Range[c[n]], d[r[n, k], r[n, #]] == 2 &]
t[n_] := t[n] = Table[s[n, k], {k, 1, c[n]}]
a[n_] := Max[Map[Length, t[n]]]
Table[a[n], {n, 1, 30}]

Python

from math import isqrt, comb
def A366429(n): return isqrt(n-comb((m:=isqrt(k:=n+1<<1))+(k>m*(m+1)),2)<<2|1)+(r:=(isqrt(k<<2)+1>>1)-1)*(r-1)-1 # Chai Wah Wu, Jun 21 2025

Formula

a(n) = 2*binomial(A002024(n+1)-1,2) + A000267(A002262(n)) - 1. - Pontus von Brömssen, Oct 24 2023

Extensions

More terms from Pontus von Brömssen, Oct 24 2023