OFFSET
1,1
COMMENTS
An integer partition is non-multigraphical if it does not comprise the multiset of vertex-degrees of any multigraph (multiset of non-loop edges). Multigraphical partitions are counted by A209816, non-multigraphical partitions by A000070.
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 strict pairs (a multiset of edges);
(2) n can be factored into squarefree semiprimes;
(3) the unordered prime signature of n is multigraphical.
LINKS
Eric Weisstein's World of Mathematics, Graphical partition.
FORMULA
EXAMPLE
The sequence of terms together with their prime indices begins:
3: {2} 53: {16} 94: {1,15}
7: {4} 55: {3,5} 101: {26}
10: {1,3} 57: {2,8} 102: {1,2,7}
13: {6} 61: {18} 107: {28}
19: {8} 62: {1,11} 111: {2,12}
21: {2,4} 66: {1,2,5} 113: {30}
22: {1,5} 71: {20} 115: {3,9}
28: {1,1,4} 76: {1,1,8} 116: {1,1,10}
29: {10} 79: {22} 117: {2,2,6}
34: {1,7} 82: {1,13} 118: {1,17}
37: {12} 85: {3,7} 129: {2,14}
39: {2,6} 87: {2,10} 130: {1,3,6}
43: {14} 88: {1,1,1,5} 131: {32}
46: {1,9} 89: {24} 133: {4,8}
52: {1,1,6} 91: {4,6} 134: {1,19}
For example, a complete lists of all loop-multigraphs with degrees (5,2,1) is:
{{1,1},{1,1},{1,2},{2,3}}
{{1,1},{1,1},{1,3},{2,2}}
{{1,1},{1,2},{1,2},{1,3}},
but since none of these is a multigraph (they have loops), the Heinz number 66 belongs to the sequence.
MATHEMATICA
prpts[m_]:=If[Length[m]==0, {{}}, Join@@Table[Prepend[#, ipr]&/@prpts[Fold[DeleteCases[#1, #2, {1}, 1]&, m, ipr]], {ipr, Select[Subsets[Union[m], {2}], MemberQ[#, m[[1]]]&]}]];
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[#]]]&&prpts[nrmptn[#]]=={}&]
CROSSREFS
A000070 counts these partitions.
A300061 is a superset.
A002100 counts partitions into squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
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