A340018 -id:A340018 - cp's OEIS frontend

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).

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

A340019 MM-numbers of labeled graphs with half-loops, without isolated vertices.

Original entry on oeis.org

1, 3, 5, 11, 13, 15, 17, 29, 31, 33, 39, 41, 43, 47, 51, 55, 59, 65, 67, 73, 79, 83, 85, 87, 93, 101, 109, 123, 127, 129, 137, 139, 141, 143, 145, 149, 155, 157, 163, 165, 167, 177, 179, 187, 191, 195, 199, 201, 205, 211, 215, 219, 221, 233, 235, 237, 241, 249

Offset: 1

Gus Wiseman, Jan 02 2021

nonn

Here a half-loop is an edge with only one vertex, to be distinguished from a full loop, which has two equal vertices.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.
Also products of distinct primes whose prime indices are either themselves prime or a squarefree semiprime (A006881).

			The sequence of terms together with their corresponding multisets of multisets (edge sets) begins:
     1: {}              55: {{2},{3}}      137: {{2,5}}
     3: {{1}}           59: {{7}}          139: {{1,7}}
     5: {{2}}           65: {{2},{1,2}}    141: {{1},{2,3}}
    11: {{3}}           67: {{8}}          143: {{3},{1,2}}
    13: {{1,2}}         73: {{2,4}}        145: {{2},{1,3}}
    15: {{1},{2}}       79: {{1,5}}        149: {{3,4}}
    17: {{4}}           83: {{9}}          155: {{2},{5}}
    29: {{1,3}}         85: {{2},{4}}      157: {{12}}
    31: {{5}}           87: {{1},{1,3}}    163: {{1,8}}
    33: {{1},{3}}       93: {{1},{5}}      165: {{1},{2},{3}}
    39: {{1},{1,2}}    101: {{1,6}}        167: {{2,6}}
    41: {{6}}          109: {{10}}         177: {{1},{7}}
    43: {{1,4}}        123: {{1},{6}}      179: {{13}}
    47: {{2,3}}        127: {{11}}         187: {{3},{4}}
    51: {{1},{4}}      129: {{1},{1,4}}    191: {{14}}

The version with full loops covering an initial interval is A320461.
The case covering an initial interval is A340018.
The version with full loops is A340020.
A006450 lists primes of prime index.
A106349 lists primes of semiprime index.
A257994 counts prime prime indices.
A302242 is the weight of the multiset of multisets with MM-number n.
A302494 lists MM-numbers of sets of sets, with connected case A328514.
A309356 lists MM-numbers of simple graphs.
A322551 lists primes of squarefree semiprime index.
A330944 counts nonprime prime indices.
A339112 lists MM-numbers of multigraphs with loops.
A339113 lists MM-numbers of multigraphs.
Cf. A000040, A000720, A001222, A005117, A056239, A076610, A112798, A289509, A302590, A305079, A326788.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],And[SquareFreeQ[#],And@@(PrimeQ[#]||(SquareFreeQ[#]&&PrimeOmega[#]==2)&/@primeMS[#])]&]

A340020 MM-numbers of labeled graphs with loops, without isolated vertices.

Original entry on oeis.org

1, 7, 13, 23, 29, 43, 47, 73, 79, 91, 97, 101, 137, 139, 149, 161, 163, 167, 199, 203, 227, 233, 257, 269, 271, 293, 299, 301, 313, 329, 347, 373, 377, 389, 421, 439, 443, 449, 467, 487, 491, 499, 511, 553, 559, 577, 607, 611, 631, 647, 653, 661, 667, 673, 677

Offset: 1

Gus Wiseman, Jan 02 2021

nonn

Here a loop is an edge with two equal vertices, distinguished from a half-loop, which has only one vertex.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.
Also products of distinct primes whose prime indices are semiprimes, where a semiprime (A001358) is a product of any two prime numbers.

			The sequence of terms together with their corresponding multisets of multisets (edge sets) begins:
      1: {}              161: {{1,1},{2,2}}    347: {{2,9}}
      7: {{1,1}}         163: {{1,8}}          373: {{1,12}}
     13: {{1,2}}         167: {{2,6}}          377: {{1,2},{1,3}}
     23: {{2,2}}         199: {{1,9}}          389: {{4,5}}
     29: {{1,3}}         203: {{1,1},{1,3}}    421: {{1,13}}
     43: {{1,4}}         227: {{4,4}}          439: {{3,7}}
     47: {{2,3}}         233: {{2,7}}          443: {{1,14}}
     73: {{2,4}}         257: {{3,5}}          449: {{2,10}}
     79: {{1,5}}         269: {{2,8}}          467: {{4,6}}
     91: {{1,1},{1,2}}   271: {{1,10}}         487: {{2,11}}
     97: {{3,3}}         293: {{1,11}}         491: {{1,15}}
    101: {{1,6}}         299: {{1,2},{2,2}}    499: {{3,8}}
    137: {{2,5}}         301: {{1,1},{1,4}}    511: {{1,1},{2,4}}
    139: {{1,7}}         313: {{3,6}}          553: {{1,1},{1,5}}
    149: {{3,4}}         329: {{1,1},{2,3}}    559: {{1,2},{1,4}}

The case with only one edge is A106349.
The case covering an initial interval is A320461.
The version allowing multiple edges is A339112.
The half-loop version covering an initial interval is A340018.
The half-loop version is A340019.
A006450 lists primes of prime index.
A302242 is the weight of the multiset of multisets with MM-number n.
A302494 lists MM-numbers of sets of sets, with connected case A328514.
A309356 lists MM-numbers of simple graphs.
A339113 lists MM-numbers of multigraphs.
Cf. A000040, A000720, A001222, A005117, A056239, A076610, A112798, A289509, A302590, A305079, A326754, A326788.

Select[Range[100],SquareFreeQ[#]&&FreeQ[If[#==1,{},FactorInteger[#]],{p_,k_}/;PrimeOmega[PrimePi[p]]!=2]&]

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).

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

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 8, 12, 16, 22, 28, 40, 51

Offset: 0

Gus Wiseman, Nov 18 2018

First differs from A046682 at a(11) = 28, A046682(11) = 29.
A vertical section is a partial Young diagram with at most one square in each row. For example, a suitable partition (shown as a coloring by positive integers) of the Young diagram of (322) is:
  1 2 3
  1 2
  2 3
Conjecture: a(n) is the number of 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(1) = 1 through a(8) = 12 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 half-loop-graphical partitions up to n = 8:
  (1)  (11)  (21)   (22)    (221)    (222)     (322)      (332)
             (111)  (211)   (311)    (321)     (2221)     (2222)
                    (1111)  (2111)   (2211)    (3211)     (3221)
                            (11111)  (3111)    (4111)     (3311)
                                     (21111)   (22111)    (4211)
                                     (111111)  (31111)    (22211)
                                               (211111)   (32111)
                                               (1111111)  (41111)
                                                          (221111)
                                                          (311111)
                                                          (2111111)
                                                          (11111111)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(7).

The complement is counted by A321728.
Cf. A000110, A000258, A000700, A000701, A006052, A007016, A008277, A046682, A319056, 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 A339656.
A027187 counts partitions of even length, ranked by 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 is a triangle counting graphical partitions by length.
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],Length[Select[spsu[ptnverts[#],ptnpos[#]],Function[p,Sort[Length/@p]==Sort[#]]]]>0&]],{n,8}]

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

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

A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

Original entry on oeis.org

1, 1, 3, 9, 29, 97, 336, 1188, 4275, 15579, 57358, 212908, 795657, 2990221, 11291665, 42814783, 162920417, 621885767, 2380348729

Offset: 0

Gus Wiseman, Dec 27 2020

In the covering case, these degree sequences, sorted in decreasing order, are the same thing as half-loop-graphical partitions (A321729). 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.
The following are equivalent characteristics for any positive integer n:
(1) the prime indices of n can be partitioned into distinct singletons or strict pairs, i.e., into a set of half-loops or edges;
(2) n can be factored into distinct primes or squarefree semiprimes;
(3) the prime signature of n is half-loop-graphical.

			The a(0) = 1 through a(3) = 9 sorted degree sequences:
  ()  (1)  (1,1)  (1,1,1)
           (2,1)  (2,1,1)
           (2,2)  (2,2,1)
                  (2,2,2)
                  (3,1,1)
                  (3,2,1)
                  (3,2,2)
                  (3,3,2)
                  (3,3,3)
For example, the half-loop-graphs
  {{1},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3}}
both have degrees y = (3,2,2), so y is counted under a(3).

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

See link for additional cross references.
The version for simple graphs is A004251, covering: A095268.
The non-covering version (it allows isolated vertices) is A029889.
The same partitions counted by sum are conjectured to be A321729.
These graphs are counted by A006125 shifted left, covering: A322661.
The version for full loops is A339844, covering: A339845.
These graphs are ranked by A340018 and A340019.
A006125 counts labeled simple graphs, covering: A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A320663/A339888 count unlabeled multiset partitions into singletons/pairs.
A339659 counts graphical partitions of 2n into k parts.
Cf. A062740, A096373, A167171, A320461, A320893, A320921, A320923, A338915, A339560, A339841, A339842.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{1,2}]],Union@@#==Range[n]&]]],{n,0,5}]

a(n) = A029889(n) - A029889(n-1) for n > 0. - Andrew Howroyd, Jan 10 2024

a(7)-a(18) added (using A029889) by Andrew Howroyd, Jan 10 2024

cp's OEIS Frontend

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

A340019 MM-numbers of labeled graphs with half-loops, without isolated vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A340020 MM-numbers of labeled graphs with loops, without isolated vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A339843 Number of distinct sorted degree sequences among all n-vertex half-loop-graphs without isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions