OFFSET
0,3
COMMENTS
An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. See A209816 for multigraphical partitions, A000070 for non-multigraphical partitions. Graphical partitions are counted by A000569.
The following are equivalent characteristics for any positive integer n:
(1) the 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 prime signature of n is graphical.
LINKS
Eric Weisstein's World of Mathematics, Graphical partition.
EXAMPLE
The a(1) = 1 through a(4) = 13 partitions:
(2) (4) (6) (8)
(2,2) (3,3) (4,4)
(3,1) (4,2) (5,3)
(5,1) (6,2)
(3,2,1) (7,1)
(4,1,1) (3,3,2)
(4,2,2)
(4,3,1)
(5,2,1)
(6,1,1)
(3,3,1,1)
(4,2,1,1)
(5,1,1,1)
For example, the partition (2,2,2,2) is not counted under a(4) because there are three possible graphs with the prescribed degrees:
{{1,2},{1,3},{2,4},{3,4}}
{{1,2},{1,4},{2,3},{3,4}}
{{1,3},{1,4},{2,3},{2,4}}
MATHEMATICA
prptns[m_]:=Union[Sort/@If[Length[m]==0, {{}}, Join@@Table[Prepend[#, m[[ipr]]]&/@prptns[Delete[m, List/@ipr]], {ipr, Select[Prepend[{#}, 1]&/@Select[Range[2, Length[m]], m[[#]]>m[[#-1]]&], UnsameQ@@m[[#]]&]}]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2, {#1}]&, #]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n], Select[prptns[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]
CROSSREFS
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 13 2020
STATUS
approved