A096373 -id:A096373 - cp's OEIS frontend

A339656 Number of loop-graphical integer partitions of 2n.

1, 2, 4, 8, 15, 28, 49, 84, 140, 229, 367, 577, 895, 1368, 2064, 3080, 4547, 6642, 9627, 13825, 19704, 27868, 39164, 54656, 75832, 104584

Offset: 0

Gus Wiseman, Dec 14 2020

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. See A339658 for the Heinz numbers, and A339655 for the complement.
The following are equivalent characteristics for any positive integer n:
(1) the multiset of 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 unordered prime signature of n is loop-graphical.

			The a(0) = 1 through a(4) = 15 partitions:
  ()  (2)    (2,2)      (3,3)          (3,3,2)
      (1,1)  (3,1)      (2,2,2)        (4,2,2)
             (2,1,1)    (3,2,1)        (4,3,1)
             (1,1,1,1)  (4,1,1)        (2,2,2,2)
                        (2,2,1,1)      (3,2,2,1)
                        (3,1,1,1)      (3,3,1,1)
                        (2,1,1,1,1)    (4,2,1,1)
                        (1,1,1,1,1,1)  (5,1,1,1)
                                       (2,2,2,1,1)
                                       (3,2,1,1,1)
                                       (4,1,1,1,1)
                                       (2,2,1,1,1,1)
                                       (3,1,1,1,1,1)
                                       (2,1,1,1,1,1,1)
                                       (1,1,1,1,1,1,1,1)
For example, there are four possible loop-graphs with degrees y = (2,2,1,1), namely
  {{1,1},{2,2},{3,4}}
  {{1,1},{2,3},{2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}
  {{1,3},{1,4},{2,2}},
so y is counted under a(3). On the other hand, there are two possible loop-multigraphs with degrees z = (4,2), namely
  {{1,1},{1,1},{2,2}}
  {{1,1},{1,2},{1,2}},
but neither of these is a loop-graph, so z is not counted under a(3).

Eric Weisstein's World of Mathematics, Graphical partition.

A339658 ranks these partitions.
A001358 lists semiprimes, with squarefree case A006881.
A006125 counts labeled graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A062740 counts labeled connected loop-graphs.
A320461 ranks normal loop-graphs.
A320655 counts factorizations into semiprimes.
A322353 counts factorizations into distinct semiprimes.
A322661 counts covering loop-graphs.
A339845 counts the same partitions by length, or A339844 with zeros.
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).
- A209816 counts multigraphical partitions (A320924).
- 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 [this sequence] counts loop-graphical partitions (A339658).
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, A001222, A025065, A095268, A101048, A320656, A320921, A338902, A338912, A338913, A339659.

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]]]];
strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];
Table[Length[Select[strnorm[2*n],Select[mpsbin[#],UnsameQ@@#&]!={}&]],{n,0,5}]

A058696(n) = a(n) + A339655(n).

a(8)-a(25) from Andrew Howroyd, Jan 10 2024

A320923 Heinz numbers of connected graphical partitions.

Original entry on oeis.org

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

A029889 Number of graphical partitions (degree-vectors for graphs with n vertices, allowing self-loops which count as degree 1; or possible ordered row-sum vectors for a symmetric 0-1 matrix).

Original entry on oeis.org

1, 2, 5, 14, 43, 140, 476, 1664, 5939, 21518, 78876, 291784, 1087441, 4077662, 15369327, 58184110, 221104527, 842990294, 3223339023

Offset: 0

torsten.sillke(AT)lhsystems.com

I call loops of degree one half-loops, so these are half-loop-graphs or graphs with half-loops. - Gus Wiseman, Dec 31 2020

			From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 14 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)
      (1)  (1,0)  (1,0,0)
           (1,1)  (1,1,0)
           (2,1)  (2,1,0)
           (2,2)  (2,2,0)
                  (1,1,1)
                  (2,1,1)
                  (3,1,1)
                  (2,2,1)
                  (3,2,1)
                  (2,2,2)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graph
  {{1,3},{3}}
has degrees (1,0,2), so (2,1,0) is counted under a(3). The half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees (3,2,2), so (3,2,2) is counted under a(3).
(End)

R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.

T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995).
Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.
Index entries for sequences related to graphical partitions

Cf. A000569, A004250, A029890, A029891.
Non-half-loop-graphical partitions are conjectured to be counted by A321728.
The covering case (no zeros) is A339843.
MM-numbers of half-loop-graphs are given by A340018 and A340019.
A004251 counts degree sequences of graphs, with covering case A095268.
A320663 counts unlabeled multiset partitions into singletons/pairs.
A339659 is a triangle counting graphical partitions.
A339844 counts degree sequences of loop-graphs, with covering case A339845.
Cf. A006125, A006129, A027187, A028260, A062740, A096373, A322661, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Subsets[Subsets[Range[n],{1,2}]]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

Calculated using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.

a(n) = A029890(n) + A029891(n). - Andrew Howroyd, Apr 18 2021

a(0) = 1 prepended by Gus Wiseman, Dec 31 2020

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.

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

Original entry on oeis.org

1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092

Offset: 0

Eric W. Weisstein, May 31 2004

nonn

A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.
Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - Paul D. Hanna, Aug 18 2006
Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - Gordon F. Royle, Aug 29 2006
Previous values a(30) = 5876236938019300 from Lorand Lucz, Jul 07 2013 and a(31) = 22974847474172100 from Lorand Lucz, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed Kai Wang and Axel Kohnert. - Vaclav Kotesovec, Apr 15 2016
In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - Vaclav Kotesovec, Apr 15 2016
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023

			a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):
  ()  .  (1,1)  (2,1,1)  (1,1,1,1)
                (2,2,2)  (2,2,1,1)
                         (2,2,2,2)
                         (3,1,1,1)
                         (3,2,2,1)
                         (3,3,2,2)
                         (3,3,3,3)
For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).
(End)

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (terms 0 through 79 from Kai Wang)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.
A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, Parallel enumeration of degree sequences of simple graphs II, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 2013).
A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapiantiae, Inform. 3 (2) (2011) 230-268.
A. Kohnert, Number of different degree sequences of a graph with no isolated vertices, 2016.
Frank Ruskey, Alley CATs in Search of Good Homes
Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.
Eric Weisstein's World of Mathematics, Degree sequence
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Cf. A002494, A004250, A007721 (analog for connected graphs), A271831.
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
The version with half-loops is A029889, with covering case A339843.
Covering simple graphs are ranked by A309356 and A320458.
Graphical partitions are ranked by A320922.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A339659 is a triangle counting graphical partitions.
Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023

Edited by N. J. A. Sloane, Aug 26 2006
More terms from Gordon F. Royle, Aug 21 2006
a(21) and a(22) from Frank Ruskey, Aug 29 2006
a(23) from Frank Ruskey, Aug 31 2006
a(24)-a(29) from Matuszka Tamás, Jan 10 2013
a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016
a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

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

A321728 Number of integer partitions of n whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 5, 7, 10, 14, 20, 28, 37, 50

Offset: 0

Gus Wiseman, Nov 18 2018

First differs from A000701 at a(11) = 28, A000701(11) = 27
A vertical section is a partial Young diagram with at most one square in each row.
Conjecture: a(n) is the number of non-half-loop-graphical partitions of n. An integer partition is half-loop-graphical if it comprises the multiset of vertex-degrees of some graph with half-loops, where a half-loop is an edge with one vertex, to be distinguished from a full loop, which has two equal vertices.

			The a(2) = 1 through a(9) = 14 partitions whose Young diagram cannot be partitioned into vertical sections of the same sizes as the parts of the original partition are the same as the non-half-loop-graphical partitions up to n = 9:
  (2)  (3)  (4)   (5)   (6)    (7)    (8)     (9)
            (31)  (32)  (33)   (43)   (44)    (54)
                  (41)  (42)   (52)   (53)    (63)
                        (51)   (61)   (62)    (72)
                        (411)  (331)  (71)    (81)
                               (421)  (422)   (432)
                               (511)  (431)   (441)
                                      (521)   (522)
                                      (611)   (531)
                                      (5111)  (621)
                                              (711)
                                              (4311)
                                              (5211)
                                              (6111)
For example, a complete list of all half/full-loop-graphs with degrees y = (4,3,1) is the following:
  {{1,1},{1,2},{1,3},{2,2}}
  {{1},{2},{1,1},{1,2},{2,3}}
  {{1},{2},{1,1},{1,3},{2,2}}
  {{1},{3},{1,1},{1,2},{2,2}}
None of these is a half-loop-graph, as they have full loops (x,x), so y is counted under a(8).

Eric Weisstein's World of Mathematics, Degree Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

The complement is counted by A321729.
Cf. A000110, A000258, A000700, A000701, A008277, A046682, A319616, A321730, A321737, A321738.
The following pertain to the conjecture.
Half-loop-graphical partitions by length are A029889 or A339843 (covering).
The version for full loops is A339655.
A027187 counts partitions of even length, with Heinz numbers A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A322661 counts labeled covering half-loop-graphs, ranked by A340018/A340019.
A339659 counts graphical partitions of 2n into k parts.
Cf. A006129, A025065, A062740, A095268, A096373, A167171, A320461, A338915, A339842, A339844, A339845.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
ptnpos[y_]:=Position[Table[1,{#}]&/@y,1];
ptnverts[y_]:=Select[Join@@Table[Subsets[ptnpos[y],{k}],{k,Reverse[Union[y]]}],UnsameQ@@First/@#&];
Table[Length[Select[IntegerPartitions[n],Select[spsu[ptnverts[#],ptnpos[#]],Function[p,Sort[Length/@p]==Sort[#]]]=={}&]],{n,8}]

a(n) is the number of integer partitions y of n such that the coefficient of m(y) in e(y) is zero, where m is monomial and e is elementary symmetric functions.

a(n) = A000041(n) - A321729(n).

cp's OEIS Frontend

A339656 Number of loop-graphical integer partitions of 2n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A029889 Number of graphical partitions (degree-vectors for graphs with n vertices, allowing self-loops which count as degree 1; or possible ordered row-sum vectors for a symmetric 0-1 matrix).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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