login
A339618
Heinz numbers of non-graphical integer partitions of even numbers.
22
3, 7, 9, 10, 13, 19, 21, 22, 25, 28, 29, 30, 34, 37, 39, 43, 46, 49, 52, 53, 55, 57, 61, 62, 63, 66, 70, 71, 75, 76, 79, 82, 84, 85, 87, 88, 89, 91, 94, 100, 101, 102, 107, 111, 113, 115, 116, 117, 118, 121, 129, 130, 131, 133, 134, 136, 138, 139, 146, 147
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.
FORMULA
Equals A300061 \ A320922.
For all n, A181821(a(n)) and A304660(a(n)) belong to A320894.
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
A181819 applied to A320894 gives this sequence.
A300061 is a superset.
A339617 counts these partitions.
A320922 ranks the complement, counted by A000569.
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:
- A058696 counts partitions of 2n (A300061).
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A209816 counts multigraphical partitions (A320924).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618 [this sequence]).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A096373 cannot be partitioned into strict pairs (A320891).
- A338914 can be partitioned into strict pairs (A320911).
- A338915 cannot be partitioned into distinct pairs (A320892).
- A338916 can be partitioned into distinct pairs (A320912).
- A339559 cannot be partitioned into distinct strict pairs (A320894).
- A339560 can be partitioned into distinct strict pairs (A339561).
Sequence in context: A082575 A284526 A344413 * A357707 A294571 A083214
KEYWORD
nonn
AUTHOR
Gus Wiseman, Dec 18 2020
STATUS
approved