cp's OEIS Frontend

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

%I A366429 #16 Jun 21 2025 19:58:16
%S A366429 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,
%T A366429 34,42,43,44,44,45,45,46,46,56,57,58,58,59,59,60,60,60,72,73,74,74,75,
%U A366429 75,76,76,76,77,90,91,92,92,93,93,94,94,94,95,95,110,111
%N A366429 a(n) = maximum degree of vertices in the distance graph of the partitions of n.
%C A366429 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.
%F A366429 a(n) = 2*binomial(A002024(n+1)-1,2) + A000267(A002262(n)) - 1. - _Pontus von Brömssen_, Oct 24 2023
%e A366429 Enumerate the 7 partitions (= vertices) of 5 as follows:
%e A366429   1: 5
%e A366429   2: 4,1
%e A366429   3: 3,2
%e A366429   4: 3,1,1
%e A366429   5: 2,2,1
%e A366429   6: 2,1,1,1
%e A366429   7: 1,1,1,1,1
%e A366429 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
%e A366429   vertex 1: {2}
%e A366429   vertex 2: {1,3,4}
%e A366429   vertex 3: {2,4,5}
%e A366429   vertex 4: {2,3,5,6}
%e A366429   vertex 5: {3,4,6}
%e A366429   vertex 6: {4,5,7}
%e A366429   vertex 7: {6}
%e A366429 The maximal degree is 4, which is the degree of vertex 4, so that a(5) = 4.
%t A366429 c[n_] := PartitionsP[n];
%t A366429 q[n_, k_] := q[n, k] = IntegerPartitions[n][[k]];
%t A366429 r[n_, k_] := r[n, k] = Join[q[n, k], ConstantArray[0, n - Length[q[n, k]]]];
%t A366429 d[u_, v_] := d[u, v] = Total[Abs[u - v]];
%t A366429 s[n_, k_] := s[n, k] = Select[Range[c[n]], d[r[n, k], r[n, #]] == 2 &]
%t A366429 t[n_] := t[n] = Table[s[n, k], {k, 1, c[n]}]
%t A366429 a[n_] := Max[Map[Length, t[n]]]
%t A366429 Table[a[n], {n, 1, 30}]
%o A366429 (Python)
%o A366429 from math import isqrt, comb
%o A366429 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
%Y A366429 Cf. A000041, A000097 (number of edges in distance graphs), A000267, A002024, A002262, A366156, A366461.
%K A366429 nonn
%O A366429 1,3
%A A366429 _Clark Kimberling_, Oct 12 2023
%E A366429 More terms from _Pontus von Brömssen_, Oct 24 2023