A339618 - OEIS

A339618

Heinz numbers of non-graphical integer partitions of even numbers.

%I #11 Dec 20 2020 22:24:22

%S 3,7,9,10,13,19,21,22,25,28,29,30,34,37,39,43,46,49,52,53,55,57,61,62,

%T 63,66,70,71,75,76,79,82,84,85,87,88,89,91,94,100,101,102,107,111,113,

%U 115,116,117,118,121,129,130,131,133,134,136,138,139,146,147

%N Heinz numbers of non-graphical integer partitions of even numbers.

%C An integer partition is graphical if it comprises the multiset of vertex-degrees of some graph. Graphical partitions are counted by A000569.

%C 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.

%C The following are equivalent characteristics for any positive integer n:

%C (1) the multiset of prime indices of n can be partitioned into distinct strict pairs (a set of edges);

%C (2) n can be factored into distinct squarefree semiprimes;

%C (3) the unordered prime signature of n is graphical.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphicalPartition.html">Graphical partition.</a>

%F Equals A300061 \ A320922.

%F For all n, A181821(a(n)) and A304660(a(n)) belong to A320894.

%e The sequence of terms together with their prime indices begins:

%e 3: {2} 43: {14} 79: {22}

%e 7: {4} 46: {1,9} 82: {1,13}

%e 9: {2,2} 49: {4,4} 84: {1,1,2,4}

%e 10: {1,3} 52: {1,1,6} 85: {3,7}

%e 13: {6} 53: {16} 87: {2,10}

%e 19: {8} 55: {3,5} 88: {1,1,1,5}

%e 21: {2,4} 57: {2,8} 89: {24}

%e 22: {1,5} 61: {18} 91: {4,6}

%e 25: {3,3} 62: {1,11} 94: {1,15}

%e 28: {1,1,4} 63: {2,2,4} 100: {1,1,3,3}

%e 29: {10} 66: {1,2,5} 101: {26}

%e 30: {1,2,3} 70: {1,3,4} 102: {1,2,7}

%e 34: {1,7} 71: {20} 107: {28}

%e 37: {12} 75: {2,3,3} 111: {2,12}

%e 39: {2,6} 76: {1,1,8} 113: {30}

%e For example, there are three possible multigraphs with degrees (1,1,3,3):

%e {{1,2},{1,2},{1,2},{3,4}}

%e {{1,2},{1,2},{1,3},{2,4}}

%e {{1,2},{1,2},{1,4},{2,3}}.

%e Since none of these is a graph, the Heinz number 100 belongs to the sequence.

%t strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[n/d],Min@@#>d&]],{d,Select[Divisors[n],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];

%t nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];

%t Select[Range[100],EvenQ[Length[nrmptn[#]]]&&strs[Times@@Prime/@nrmptn[#]]=={}&]

%Y A181819 applied to A320894 gives this sequence.

%Y A300061 is a superset.

%Y A339617 counts these partitions.

%Y A320922 ranks the complement, counted by A000569.

%Y A006881 lists squarefree semiprimes.

%Y A320656 counts factorizations into squarefree semiprimes.

%Y A339659 counts graphical partitions of 2n into k parts.

%Y The following count vertex-degree partitions and give their Heinz numbers:

%Y - A058696 counts partitions of 2n (A300061).

%Y - A000070 counts non-multigraphical partitions of 2n (A339620).

%Y - A209816 counts multigraphical partitions (A320924).

%Y - A339655 counts non-loop-graphical partitions of 2n (A339657).

%Y - A339656 counts loop-graphical partitions (A339658).

%Y - A339617 counts non-graphical partitions of 2n (A339618 [this sequence]).

%Y - A000569 counts graphical partitions (A320922).

%Y The following count partitions of even length and give their Heinz numbers:

%Y - A027187 has no additional conditions (A028260).

%Y - A096373 cannot be partitioned into strict pairs (A320891).

%Y - A338914 can be partitioned into strict pairs (A320911).

%Y - A338915 cannot be partitioned into distinct pairs (A320892).

%Y - A338916 can be partitioned into distinct pairs (A320912).

%Y - A339559 cannot be partitioned into distinct strict pairs (A320894).

%Y - A339560 can be partitioned into distinct strict pairs (A339561).

%Y Cf. A001358, A007717, A050326, A320923, A338899.

%K nonn

%O 1,1

%A _Gus Wiseman_, Dec 18 2020