OFFSET
1,1
COMMENTS
An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. Graphical partitions are counted by A000569.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of prime indices of n can be partitioned into distinct strict pairs (a set of edges);
(2) n can be factored into distinct squarefree semiprimes;
(3) the unordered prime signature of n is graphical.
LINKS
Eric Weisstein's World of Mathematics, Graphical partition.
EXAMPLE
The sequence of terms together with their prime indices begins:
3: {2} 43: {14} 79: {22}
7: {4} 46: {1,9} 82: {1,13}
9: {2,2} 49: {4,4} 84: {1,1,2,4}
10: {1,3} 52: {1,1,6} 85: {3,7}
13: {6} 53: {16} 87: {2,10}
19: {8} 55: {3,5} 88: {1,1,1,5}
21: {2,4} 57: {2,8} 89: {24}
22: {1,5} 61: {18} 91: {4,6}
25: {3,3} 62: {1,11} 94: {1,15}
28: {1,1,4} 63: {2,2,4} 100: {1,1,3,3}
29: {10} 66: {1,2,5} 101: {26}
30: {1,2,3} 70: {1,3,4} 102: {1,2,7}
34: {1,7} 71: {20} 107: {28}
37: {12} 75: {2,3,3} 111: {2,12}
39: {2,6} 76: {1,1,8} 113: {30}
For example, there are three possible multigraphs with degrees (1,1,3,3):
{{1,2},{1,2},{1,2},{3,4}}
{{1,2},{1,2},{1,3},{2,4}}
{{1,2},{1,2},{1,4},{2,3}}.
Since none of these is a graph, the Heinz number 100 belongs to the sequence.
MATHEMATICA
strs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[strs[n/d], Min@@#>d&]], {d, Select[Divisors[n], And[SquareFreeQ[#], PrimeOmega[#]==2]&]}]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]], {#1}]&, If[n==1, {}, Flatten[Cases[FactorInteger[n]//Reverse, {p_, k_}:>Table[PrimePi[p], {k}]]]]];
Select[Range[100], EvenQ[Length[nrmptn[#]]]&&strs[Times@@Prime/@nrmptn[#]]=={}&]
CROSSREFS
A300061 is a superset.
A339617 counts these partitions.
A006881 lists squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339659 counts graphical partitions of 2n into k parts.
The following count vertex-degree partitions and give their Heinz numbers:
The following count partitions of even length and give their Heinz numbers:
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 18 2020
STATUS
approved