A209816 -id:A209816 - cp's OEIS frontend

A320923 Heinz numbers of connected graphical partitions.

4, 12, 27, 36, 40, 81, 90, 108, 112, 120, 225, 243, 252, 270, 300, 324, 336, 352, 360, 400, 567, 625, 630, 675, 729, 750, 756, 792, 810, 832, 840, 900, 972, 1000, 1008, 1056, 1080, 1120, 1200, 1323, 1575, 1701, 1750, 1764, 1782, 1872, 1875, 1890, 1980, 2025

Offset: 1

Gus Wiseman, Oct 24 2018

nonn

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

An integer partition is connected and graphical if it comprises the multiset of vertex-degrees of some connected simple graph.

			The sequence of all connected-graphical partitions begins: (11), (211), (222), (2211), (3111), (2222), (3221), (22211), (41111), (32111), (3322), (22222), (42211), (32221), (33211), (222211), (421111), (511111), (322111).

Cf. A000070, A000569, A007717, A025065, A056239, A096373, A112798, A147878, A209816, A300061, A320635, A320911, A320921, A320922, A320925.

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[[#]]&]}]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Select[Range[1000],Select[prptns[Flatten[MapIndexed[Table[#2,{#1}]&,If[#==1,{},Flatten[Cases[FactorInteger[#],{p_,k_}:>Table[PrimePi[p],{k}]]]]]]],And[UnsameQ@@#,Length[csm[#]]==1]&]!={}&]

A339559 Number of integer partitions of n that have an even number of parts and cannot be partitioned into distinct pairs of distinct parts, i.e., that are not the multiset union of any set of edges.

Original entry on oeis.org

0, 0, 1, 0, 2, 1, 4, 3, 7, 6, 14, 14, 23, 27, 41, 47, 70, 84, 114, 141, 190, 225, 303, 370, 475, 578, 738, 890, 1131, 1368, 1698, 2058, 2549, 3048, 3759, 4505, 5495, 6574, 7966, 9483, 11450, 13606, 16307, 19351, 23116, 27297, 32470, 38293, 45346, 53342, 62939

Offset: 0

Gus Wiseman, Dec 10 2020

nonn

The multiplicities of such a partition form a non-graphical partition.

			The a(2) = 1 through a(10) = 14 partitions (empty column indicated by dot):
  11   .   22     2111   33       2221     44         3222       55
           1111          2211     4111     2222       6111       3322
                         3111     211111   3311       222111     3331
                         111111            5111       321111     4222
                                           221111     411111     4411
                                           311111     21111111   7111
                                           11111111              222211
                                                                 322111
                                                                 331111
                                                                 421111
                                                                 511111
                                                                 22111111
                                                                 31111111
                                                                 1111111111
For example, the partition y = (4,4,3,3,2,2,1,1,1,1) can be partitioned into a multiset of edges in just three ways:
  {{1,2},{1,2},{1,3},{1,4},{3,4}}
  {{1,2},{1,3},{1,3},{1,4},{2,4}}
  {{1,2},{1,3},{1,4},{1,4},{2,3}}
None of these are strict, so y is counted under a(22).

Eric Weisstein's World of Mathematics, Graphical partition.

A320894 ranks these partitions (using Heinz numbers).
A338915 allows equal pairs (x,x).
A339560 counts the complement in even-length partitions.
A339564 counts factorizations of the same type.
A000070 counts non-multigraphical partitions of 2n, ranked by A339620.
A000569 counts graphical partitions, ranked by A320922.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A058696 counts partitions of even numbers, ranked by A300061.
A209816 counts multigraphical partitions, ranked by A320924.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339617 counts non-graphical partitions of 2n, ranked by A339618.
A339655 counts non-loop-graphical partitions of 2n, ranked by A339657.
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).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A005117, A007717, A025065, A030229, A089259, A292432, A320893, A338899, A338903, A339619.

strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
Table[Length[Select[IntegerPartitions[n],EvenQ[Length[#]]&&strs[Times@@Prime/@#]=={}&]],{n,0,15}]

A027187(n) = a(n) + A339560(n).

More terms from Jinyuan Wang, Feb 14 2025

A147878 The number of degree sequences with degree sum 2n representable by a connected graph (with multiple edges allowed).

Original entry on oeis.org

1, 2, 5, 11, 23, 46, 86, 156, 273, 463, 766, 1241, 1969, 3073, 4723, 7157, 10711, 15850, 23206, 33654, 48373, 68955, 97544, 137002, 191125, 264955, 365127, 500349, 682018, 924982, 1248502, 1677530, 2244229, 2989952, 3967732, 5245354, 6909211

Offset: 1

James Sellers, Nov 16 2008

nonn

			From _Gus Wiseman_, Oct 26 2018: (Start)
The a(1) = 1 through a(5) = 23 connected multigraphical partitions:
  (11)  (22)   (33)    (44)     (55)
        (211)  (222)   (332)    (433)
               (321)   (422)    (442)
               (2211)  (431)    (532)
               (3111)  (2222)   (541)
                       (3221)   (3322)
                       (3311)   (3331)
                       (4211)   (4222)
                       (22211)  (4321)
                       (32111)  (4411)
                       (41111)  (5221)
                                (5311)
                                (22222)
                                (32221)
                                (33211)
                                (42211)
                                (43111)
                                (52111)
                                (222211)
                                (322111)
                                (331111)
                                (421111)
                                (511111)
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
O. J. Rodseth, J. A. Sellers and H. Tverberg, Enumeration of the Degree Sequences of Non-Separable Graphs and Connected Graphs, European Journal of Combinatorics 30 (2009), 1301-1317.
Gus Wiseman, Connected multigraphs realizing each of the a(5) = 23 connected multigraphical graphical partitions of 10.

Cf. A000070, A000569, A007717, A096373, A147877, A209816, A320911, A320921 (no multiedges), A320923.

with(combinat): seq(numbpart(2*m) - numbpart(m - 1) - 2*add(numbpart(j), j = 0 .. m-2), m=1..60);

a(n) = numbpart(2*n) - numbpart(n-1) - 2*sum(j=0, n-2, numbpart(j)); \\ Michel Marcus, Nov 04 2016

a(n) = p(2n) - p(n-1) - 2*Sum_{j=0..n-2} p(j).
a(n) = A000041(2*n) - 2*A000070(n) + 2*A000041(n) + A000041(n-1). - Vaclav Kotesovec, Nov 05 2016
a(n) ~ exp(2*Pi*sqrt(n/3))/(8*sqrt(3)*n) * (1 - (sqrt(3)/(2*Pi) + Pi/(48*sqrt(3))) /sqrt(n)). - Vaclav Kotesovec, Nov 05 2016

Offset corrected by Michel Marcus, Nov 04 2016

A339658 Heinz numbers of loop-graphical partitions (of even numbers).

Original entry on oeis.org

1, 3, 4, 9, 10, 12, 16, 25, 27, 28, 30, 36, 40, 48, 63, 64, 70, 75, 81, 84, 88, 90, 100, 108, 112, 120, 144, 147, 160, 175, 189, 192, 196, 198, 208, 210, 220, 225, 243, 250, 252, 256, 264, 270, 280, 300, 324, 336, 343, 352, 360, 400, 432, 441, 448, 462, 468, 480

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

Equals the image of A181819 applied to the set of terms of A320912.
The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
A partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. Loop-graphical partitions are counted by A339656.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The sequence of terms > 1 together with their prime indices begins:
      3: {2}               70: {1,3,4}          192: {1,1,1,1,1,1,2}
      4: {1,1}             75: {2,3,3}          196: {1,1,4,4}
      9: {2,2}             81: {2,2,2,2}        198: {1,2,2,5}
     10: {1,3}             84: {1,1,2,4}        208: {1,1,1,1,6}
     12: {1,1,2}           88: {1,1,1,5}        210: {1,2,3,4}
     16: {1,1,1,1}         90: {1,2,2,3}        220: {1,1,3,5}
     25: {3,3}            100: {1,1,3,3}        225: {2,2,3,3}
     27: {2,2,2}          108: {1,1,2,2,2}      243: {2,2,2,2,2}
     28: {1,1,4}          112: {1,1,1,1,4}      250: {1,3,3,3}
     30: {1,2,3}          120: {1,1,1,2,3}      252: {1,1,2,2,4}
     36: {1,1,2,2}        144: {1,1,1,1,2,2}    256: {1,1,1,1,1,1,1,1}
     40: {1,1,1,3}        147: {2,4,4}          264: {1,1,1,2,5}
     48: {1,1,1,1,2}      160: {1,1,1,1,1,3}    270: {1,2,2,2,3}
     63: {2,2,4}          175: {3,3,4}          280: {1,1,1,3,4}
     64: {1,1,1,1,1,1}    189: {2,2,2,4}        300: {1,1,2,3,3}
For example, the four loop-graphs with degrees y = (3,1,1,1) are:
  {{1,1},{1,2},{3,4}}
  {{1,1},{1,3},{2,4}}
  {{1,1},{1,4},{2,3}}
  {{1,2},{1,3},{1,4}},
so the Heinz number 40 is in the sequence. On the other hand, the three loop-multigraphs with degrees y = (4,4) are
  {{1,1},{1,1},{2,2},{2,2}}
  {{1,1},{1,2},{1,2},{2,2}}
  {{1,2},{1,2},{1,2},{1,2}},
but none of these is a loop-graph, so the Heinz number 49 is not in the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A320912 has these prime shadows (see A181819).
A339656 counts these partitions.
A339657 ranks the complement, counted by A339655.
A001358 lists semiprimes, with squarefree case A006881.
A101048 counts partitions into semiprimes.
A320655 counts factorizations into semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A058696 counts partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- A027187 has no additional conditions (A028260).
- A338914 can be partitioned into strict pairs (A320911).
- A338916 can be partitioned into distinct pairs (A320912).
- A339560 can be partitioned into distinct strict pairs (A339561).
Cf. A001055, A001221, A001222, A007717, A056239, A112798, A320732, A320892, A338898, A338912, A338913, A339112.

spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[25],Select[mpsbin[nrmptn[#]],UnsameQ@@#&]!={}&]

A300061 = A339657 \/ A339658.

A339657 Heinz numbers of non-loop-graphical partitions of even numbers.

Original entry on oeis.org

7, 13, 19, 21, 22, 29, 34, 37, 39, 43, 46, 49, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 121, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 154, 155, 156, 159, 163, 165, 166, 169, 171

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

Equals the image of A181819 applied to the set of terms of A320892.
The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). This gives a bijective correspondence between positive integers and integer partitions.
An integer partition is loop-graphical if it comprises the multiset of vertex-degrees of some graph with loops, where a loop is an edge with two equal vertices. Loop-graphical partitions are counted by A339656, with Heinz numbers A339658.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct pairs, i.e., into a set of edges and loops;
(2) n can be factored into distinct semiprimes;
(3) the prime signature of n is loop-graphical.

			The sequence of terms together with their prime indices begins:
      7: {4}         57: {2,8}      107: {28}
     13: {6}         61: {18}       111: {2,12}
     19: {8}         62: {1,11}     113: {30}
     21: {2,4}       66: {1,2,5}    115: {3,9}
     22: {1,5}       71: {20}       116: {1,1,10}
     29: {10}        76: {1,1,8}    117: {2,2,6}
     34: {1,7}       79: {22}       118: {1,17}
     37: {12}        82: {1,13}     121: {5,5}
     39: {2,6}       85: {3,7}      129: {2,14}
     43: {14}        87: {2,10}     130: {1,3,6}
     46: {1,9}       89: {24}       131: {32}
     49: {4,4}       91: {4,6}      133: {4,8}
     52: {1,1,6}     94: {1,15}     134: {1,19}
     53: {16}       101: {26}       136: {1,1,1,7}
     55: {3,5}      102: {1,2,7}    138: {1,2,9}
For example, the three loop-multigraphs with degrees y = (5,2,1) are:
  {{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 loop-graph (they have multiple edges), the Heinz number 66 is in the sequence.

Eric Weisstein's World of Mathematics, Graphical partition.

A320892 has these prime shadows (see A181819).
A321728 is conjectured to be the version for half-loops {x} instead of loops {x,x}.
A339655 counts these partitions.
A339658 ranks the complement, counted by A339656.
A001358 lists semiprimes, with odd and even terms A046315 and A100484.
A006881 lists squarefree semiprimes, with odd and even terms A046388 and A100484.
A101048 counts partitions into semiprimes.
A320655 counts factorizations into semiprimes.
A320656 counts factorizations into squarefree semiprimes.
A339844 counts loop-graphical partitions by length.
factorizations of n into distinct primes or squarefree semiprimes.
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 [this sequence]).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- 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).
Cf. A001055, A001221, A001222, A007717, A056239, A112798, A320732, A338898, A338912, A338913, A339742, A339839.

spsbin[{}]:={{}};spsbin[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsbin[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpsbin[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@spsbin[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Select[Range[50],EvenQ[Length[nrmptn[#]]]&&Select[mpsbin[nrmptn[#]],UnsameQ@@#&]=={}&]

A300061 = A339657 \/ A339658.

A339620 Heinz numbers of non-multigraphical partitions of even numbers.

Original entry on oeis.org

3, 7, 10, 13, 19, 21, 22, 28, 29, 34, 37, 39, 43, 46, 52, 53, 55, 57, 61, 62, 66, 71, 76, 79, 82, 85, 87, 88, 89, 91, 94, 101, 102, 107, 111, 113, 115, 116, 117, 118, 129, 130, 131, 133, 134, 136, 138, 139, 146, 148, 151, 155, 156, 159, 163, 166, 171, 172, 173

Offset: 1

Gus Wiseman, Dec 18 2020

nonn

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.

			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.

Eric Weisstein's World of Mathematics, Graphical partition.

A000070 counts these partitions.
A300061 is a superset.
A320891 has image under A181819 equal to this set of terms.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A320656 counts factorizations into squarefree semiprimes.
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 [this sequence]).
- A209816 counts multigraphical partitions (A320924).
- A147878 counts connected multigraphical partitions (A320925).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
- A339617 counts non-graphical partitions of 2n (A339618).
- 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).
Cf. A001055, A005117, A007717, A030229, A050320, A056239, A112798, A320655, A338899, A339113, A339661.

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[#]]=={}&]

Equals A300061 \ A320924.

For all n, both A181821(a(n)) and A304660(a(n)) belong to A320891.

A339659 Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 2, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 5, 3, 2, 1, 1, 0, 0, 0, 0, 1, 4, 7, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 4, 9, 11, 11, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 2, 11, 15, 17, 15, 11, 7, 5, 3, 2, 1, 1

Offset: 0

Gus Wiseman, Dec 18 2020

Conjecture: The column sums 1, 0, 1, 2, 7, 20, 67, ... are given by A304787.

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

			Triangle begins:
  1
  0 0 1
  0 0 0 1 1
  0 0 0 1 2 1 1
  0 0 0 0 2 3 2 1 1
  0 0 0 0 1 4 5 3 2 1 1
  0 0 0 0 1 4 7 7 5 3 2 1 1
For example, row n = 5 counts the following partitions:
  3322  22222  222211  2221111  22111111  211111111  1111111111
        32221  322111  3211111  31111111
        33211  331111  4111111
        42211  421111
               511111

A000569 gives the row sums.
A004250 is the central column.
A005408 gives the row lengths.
A008284/A072233 is the version counting all partitions.
A259873 is the left half of the triangle.
A309356 is a universal embedding.
A027187 counts partitions of even length.
A339559 = partitions that cannot be partitioned into distinct strict pairs.
A339560 = partitions that can be partitioned into distinct strict pairs.
The following count vertex-degree partitions and give their Heinz numbers:
- A000070 counts non-multigraphical partitions of 2n (A339620).
- A000569 counts graphical partitions (A320922).
- A058696 counts partitions of 2n (A300061).
- A147878 counts connected multigraphical partitions (A320925).
- A209816 counts multigraphical partitions (A320924).
- A320921 counts connected graphical partitions (A320923).
- A321728 is conjectured to count non-half-loop-graphical partitions of n.
- A339617 counts non-graphical partitions of 2n (A339618).
- A339655 counts non-loop-graphical partitions of 2n (A339657).
- A339656 counts loop-graphical partitions (A339658).
Cf. A000219, A002100, A006881, A007717, A025065, A320656, A320894, A338914, A338916, A339561, A339661.

prpts[m_]:=If[Length[m]==0,{{}},Join@@Table[Prepend[#,ipr]&/@prpts[Fold[DeleteCases[#1,#2,{1},1]&,m,ipr]],{ipr,Subsets[Union[m],{2}]}]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Length[Union[#]]==k&&Select[prpts[#],UnsameQ@@#&]!={}&]],{n,0,5},{k,0,2*n}]

A339742 Number of factorizations of n into distinct primes or squarefree semiprimes.

Original entry on oeis.org

1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 1, 1, 2, 2, 0, 1, 1, 1, 1, 2, 2, 1, 0, 0, 2, 0, 1, 1, 4, 1, 0, 2, 2, 2, 1, 1, 2, 2, 0, 1, 4, 1, 1, 1, 2, 1, 0, 0, 1, 2, 1, 1, 0, 2, 0, 2, 2, 1, 3, 1, 2, 1, 0, 2, 4, 1, 1, 2, 4, 1, 0, 1, 2, 1, 1, 2, 4, 1, 0, 0, 2, 1, 3, 2, 2, 2, 0, 1, 3, 2, 1, 2, 2, 2, 0, 1, 1, 1, 1, 1, 4, 1, 0, 4

Offset: 1

Gus Wiseman, Dec 20 2020

nonn

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
The following are equivalent characteristics for any positive integer n:
(1) the prime factors of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops and edges;
(2) n can be factored into distinct primes or squarefree semiprimes.

			The a(n) factorizations for n = 6, 30, 60, 210, 420 are respectively 2, 4, 3, 10, 9:
  (6)    (5*6)    (6*10)    (6*35)     (2*6*35)
  (2*3)  (2*15)   (2*5*6)   (10*21)    (5*6*14)
         (3*10)   (2*3*10)  (14*15)    (6*7*10)
         (2*3*5)            (5*6*7)    (2*10*21)
                            (2*3*35)   (2*14*15)
                            (2*5*21)   (2*5*6*7)
                            (2*7*15)   (3*10*14)
                            (3*5*14)   (2*3*5*14)
                            (3*7*10)   (2*3*7*10)
                            (2*3*5*7)

Antti Karttunen, Table of n, a(n) for n = 1..69300
Index entries for sequences computed from exponents in factorization of n

Dirichlet convolution of A008966 with A339661.
A008966 allows only primes.
A339661 does not allow primes, only squarefree semiprimes.
A339740 lists the positions of zeros.
A339741 lists the positions of positive terms.
A339839 allows nonsquarefree semiprimes.
A339887 is the non-strict version.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A013929 cannot be factored into distinct primes.
A293511 are a product of distinct squarefree numbers in exactly one way.
A320663 counts non-isomorphic multiset partitions into singletons or pairs.
A339840 cannot be factored into distinct primes or semiprimes.
A339841 have exactly one factorization into primes or semiprimes.
The following count factorizations:
- A001055 into all positive integers > 1.
- A050320 into squarefree numbers.
- A050326 into distinct squarefree numbers.
- A320655 into semiprimes.
- A320656 into squarefree semiprimes.
- A320732 into primes or semiprimes.
- A322353 into distinct semiprimes.
- A339742 [this sequence] into distinct primes or squarefree semiprimes.
- A339839 into distinct primes or semiprimes.
The following count vertex-degree partitions and give their Heinz numbers:
- A000569 counts graphical partitions (A320922).
- A058696 counts all partitions of 2n (A300061).
- A209816 counts multigraphical partitions (A320924).
- A339656 counts loop-graphical partitions (A339658).
-
The following count partitions/factorizations of even length and give their Heinz numbers:
- A027187/A339846 has no additional conditions (A028260).
- A338914/A339562 can be partitioned into edges (A320911).
- A338916/A339563 can be partitioned into distinct pairs (A320912).
- A339559/A339564 cannot be partitioned into distinct edges (A320894).
- A339560/A339619 can be partitioned into distinct edges (A339561).
Cf. A000070, A001221, A005117, A320893, A320923, A338899, A339113, A339617, A353471.

sqps[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[sqps[n/d],Min@@#>d&]],{d,Select[Divisors[n],PrimeQ[#]||SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Table[Length[sqps[n]],{n,100}]

A353471(n) = (numdiv(n)==2*omega(n));
A339742(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (dA353471(d), s += A339742(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

a(n) = Sum_{d|n squarefree} A339661(n/d).

More terms from Antti Karttunen, May 02 2022

A344414 Heinz numbers of integer partitions whose sum is at most twice their greatest part.

Original entry on oeis.org

2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 49, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 76, 77, 78, 79, 82, 83, 84, 85

Offset: 1

Gus Wiseman, May 19 2021

nonn

The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

			The sequence of terms together with their prime indices begins:
     2: {1}        20: {1,1,3}    39: {2,6}
     3: {2}        21: {2,4}      40: {1,1,1,3}
     4: {1,1}      22: {1,5}      41: {13}
     5: {3}        23: {9}        42: {1,2,4}
     6: {1,2}      25: {3,3}      43: {14}
     7: {4}        26: {1,6}      44: {1,1,5}
     9: {2,2}      28: {1,1,4}    46: {1,9}
    10: {1,3}      29: {10}       47: {15}
    11: {5}        30: {1,2,3}    49: {4,4}
    12: {1,1,2}    31: {11}       51: {2,7}
    13: {6}        33: {2,5}      52: {1,1,6}
    14: {1,4}      34: {1,7}      53: {16}
    15: {2,3}      35: {3,4}      55: {3,5}
    17: {7}        37: {12}       56: {1,1,1,4}
    19: {8}        38: {1,8}      57: {2,8}
For example, 56 has prime indices {1,1,1,4} and 7 <= 2*4, so 56 is in the sequence. On the other hand, 224 has prime indices {1,1,1,1,1,4} and 9 > 2*4, so 224 is not in the sequence.

These partitions are counted by A025065 but are different from palindromic partitions, which have Heinz numbers A265640.
The opposite even-weight version appears to be A320924, counted by A209816.
The opposite version appears to be A322109, counted by A110618.
The case of equality in the conjugate version is A340387.
The conjugate opposite version is A344291, counted by A110618.
The conjugate opposite 5-smooth case is A344293, counted by A266755.
The conjugate version is A344296, also counted by A025065.
The case of equality is A344415.
The even-weight case is A344416.
A001222 counts prime factors with multiplicity.
A027187 counts partitions of even length, ranked by A028260.
A056239 adds up prime indices, row sums of A112798.
A058696 counts partitions of even numbers, ranked by A300061.
A301987 lists numbers whose sum of prime indices equals their product.
A334201 adds up all prime indices except the greatest.
Cf. A001414, A067538, A301988, A316413, A316428, A325037, A325038, A325044, A330950, A344294, A344297.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Max[primeMS[#]]>=Total[primeMS[#]]/2&]

A056239(a(n)) <= 2*A061395(a(n)).

A339661 Number of factorizations of n into distinct squarefree semiprimes.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0

Offset: 1

Gus Wiseman, Dec 19 2020

nonn

A squarefree semiprime (A006881) is a product of any two distinct prime numbers.

Also the number of strict multiset partitions of the multiset of prime factors of n, into distinct strict pairs.

			The a(n) factorizations for n = 210, 1260, 4620, 30030, 69300 are respectively 3, 2, 6, 15, 7:
  (6*35)   (6*10*21)  (6*10*77)   (6*55*91)    (6*10*15*77)
  (10*21)  (6*14*15)  (6*14*55)   (6*65*77)    (6*10*21*55)
  (14*15)             (6*22*35)   (10*33*91)   (6*10*33*35)
                      (10*14*33)  (10*39*77)   (6*14*15*55)
                      (10*21*22)  (14*33*65)   (6*15*22*35)
                      (14*15*22)  (14*39*55)   (10*14*15*33)
                                  (15*22*91)   (10*15*21*22)
                                  (15*26*77)
                                  (21*22*65)
                                  (21*26*55)
                                  (22*35*39)
                                  (26*33*35)
                                  (6*35*143)
                                  (10*21*143)
                                  (14*15*143)

Antti Karttunen, Table of n, a(n) for n = 1..69300
Index entries for sequences computed from exponents in factorization of n

Dirichlet convolution of A008836 (Liouville's lambda) with A339742.
A050326 allows all squarefree numbers, non-strict case A050320.
A320656 is the not necessarily strict version.
A320911 lists all (not just distinct) products of squarefree semiprimes.
A322794 counts uniform factorizations, such as these.
A339561 lists positions of nonzero terms.
A001055 counts factorizations, with strict case A045778.
A001358 lists semiprimes, with squarefree case A006881.
A320655 counts factorizations into semiprimes, with strict case A322353.
The following count vertex-degree partitions and give their Heinz numbers:
- 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).
- A000569 counts graphical partitions (A320922).
The following count partitions of even length and give their Heinz numbers:
- 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).
Cf. A001221, A005117, A007716, A028260, A280710, A300061, A320658, A320659, A320923, A330974.

bfacs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[bfacs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],SquareFreeQ[#]&&PrimeOmega[#]==2&]}]];
Table[Length[bfacs[n]],{n,100}]

A280710(n) = (bigomega(n)==2*issquarefree(n)); \\ From A280710.
A339661(n, u=(1+n)) = if(1==n, 1, my(s=0); fordiv(n, d, if((d>1) && (dA280710(d), s += A339661(n/d, d))); (s)); \\ Antti Karttunen, May 02 2022

a(n) = Sum_{d|n} (-1)^A001222(d) * A339742(n/d).

More terms and secondary offset added by Antti Karttunen, May 02 2022

cp's OEIS Frontend

A320923 Heinz numbers of connected graphical partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339559 Number of integer partitions of n that have an even number of parts and cannot be partitioned into distinct pairs of distinct parts, i.e., that are not the multiset union of any set of edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A147878 The number of degree sequences with degree sum 2n representable by a connected graph (with multiple edges allowed).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A339658 Heinz numbers of loop-graphical partitions (of even numbers).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339657 Heinz numbers of non-loop-graphical partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339620 Heinz numbers of non-multigraphical partitions of even numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A339659 Irregular triangle read by rows where T(n,k) is the number of graphical partitions of 2n into k parts, 0 <= k <= 2n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A339742 Number of factorizations of n into distinct primes or squarefree semiprimes.

Views

Author

Keywords