A339842 -id:A339842 - cp's OEIS frontend

A004251 Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).

1, 1, 2, 4, 11, 31, 102, 342, 1213, 4361, 16016, 59348, 222117, 836315, 3166852, 12042620, 45967479, 176005709, 675759564, 2600672458, 10029832754, 38753710486, 149990133774, 581393603996, 2256710139346, 8770547818956, 34125389919850, 132919443189544, 518232001761434, 2022337118015338, 7898574056034636, 30873421455729728

Offset: 0

N. J. A. Sloane

In other words, a(n) is the number of graphic sequences of length n, where a graphic sequence is a sequence of numbers which can be the degree sequence of some graph.

In the article by A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, "Parallel enumeration of degree sequences of simple graphs II", in Table 4 on page 260 the values a(30) = 7898574056034638 and a(31) = 30873429530206738 are incorrect due to the incorrect Gz(30) = 5876236938019300 and Gz(31) = 22974847474172100. - Wang Kai, Jun 05 2016

			For n = 3, there are 4 different graphic sequences possible: 0 0 0; 1 1 0; 2 1 1; 2 2 2. - Daan van Berkel (daan.v.berkel.1980(AT)gmail.com), Jun 25 2010
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(4) = 11 sorted degree sequences:
  ()  (0)  (0,0)  (0,0,0)  (0,0,0,0)
           (1,1)  (0,1,1)  (0,0,1,1)
                  (1,1,2)  (0,1,1,2)
                  (2,2,2)  (0,2,2,2)
                           (1,1,1,1)
                           (1,1,1,3)
                           (1,1,2,2)
                           (1,2,2,3)
                           (2,2,2,2)
                           (2,2,3,3)
                           (3,3,3,3)
For example, the graph {{2,3},{2,4}} has degrees (0,2,1,1), so (0,1,1,2) is counted under a(4).
(End)

R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978).

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (Terms 1 through 31 were computed by various authors; terms 32 through 34 by Axel Kohnert and Wang Kai; terms 35 to 79 by Wang Kai)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995), #R11.
B. A. Chat, S. Pirzada, and A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.
D. Dimitrov, Efficient computation of trees with minimal atom-bond connectivity index, arXiv:1305.1155 [cs.DM], 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. Sapientiae, Inform. 3(2) (2011), 230-268.
A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapientiae, Informatica, 4, 2 (2012), 260-288. - From _N. J. A. Sloane_, Feb 15 2013
A. Ivanyi and J. E. Schoenfield, Deciding football sequences, Acta Univ. Sapientiae, Informatica, 4, 1 (2012), 130-183. - From _N. J. A. Sloane_, Dec 22 2012 [Disclaimer: I am not one of the authors of this paper; I was unpleasantly surprised to find my name on it, as explained here. - _Jon E. Schoenfield_, Nov 26 2016]
Wang Kai, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms.
P. W. Mills, R. P. Rundle, V. M. Dwyer, T. Tilma, and S. J. Devitt, A proposal for an efficient quantum algorithm solving the graph isomorphism problem, arXiv 1711.09842, 2017.
P. R. Stein, On the number of graphical partitions, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]
Eric Weisstein's World of Mathematics, Degree Sequence.
Eric Weisstein's World of Mathematics, Graphic Sequence.
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.
Index entries for sequences related to graphical partitions

Counting the positive partitions by sum gives A000569, ranked by A320922.
The version with half-loops is A029889, with covering case A339843.
The covering case (no zeros) is A095268.
Covering simple graphs are ranked by A309356 and A320458.
Non-graphical partitions are counted by A339617 and ranked by A339618.
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.
A320921 counts connected graphical partitions.
A322353 counts factorizations into distinct semiprimes.
A339659 counts graphical partitions of 2n into k parts.
A339661 counts factorizations into distinct squarefree semiprimes.
Cf. A004250, A007717, A181819, A320894, A320923, A339560, A339561, A339842.

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

G.f. = 1 + x + 2*x^2 + 4*x^3 + 11*x^4 + 31*x^5 + 102*x^6 + 342*x^7 + 1213*x^8 + ...

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

More terms from Torsten Sillke, torsten.sillke(AT)lhsystems.com, using Cor. 6.3.3, Th. 6.3.6, Cor. 6.2.5 of Brualdi-Ryser.
a(19) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007
a(20)-a(23) from Nathann Cohen, Jul 09 2011
a(24)-a(29) from Antal Iványi, Nov 15 2011
a(30) and a(31) corrected by Wang Kai, Jun 05 2016

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

A340017 Products of squarefree semiprimes that are not products of distinct squarefree semiprimes.

Original entry on oeis.org

36, 100, 196, 216, 225, 360, 441, 484, 504, 540, 600, 676, 756, 792, 936, 1000, 1089, 1156, 1176, 1188, 1224, 1225, 1296, 1350, 1368, 1400, 1404, 1444, 1500, 1521, 1656, 1836, 1960, 2052, 2088, 2116, 2160, 2200, 2232, 2250, 2484, 2600, 2601, 2646, 2664, 2744

Offset: 1

Gus Wiseman, Dec 30 2020

nonn

Of course, every number is a product of squarefree numbers (A050320).
A squarefree semiprime (A006881) is a product of any two distinct prime numbers.
All terms have even Omega (A001222, A028260).

			The sequence of terms together with their prime indices begins:
      36: {1,1,2,2}        1000: {1,1,1,3,3,3}
     100: {1,1,3,3}        1089: {2,2,5,5}
     196: {1,1,4,4}        1156: {1,1,7,7}
     216: {1,1,1,2,2,2}    1176: {1,1,1,2,4,4}
     225: {2,2,3,3}        1188: {1,1,2,2,2,5}
     360: {1,1,1,2,2,3}    1224: {1,1,1,2,2,7}
     441: {2,2,4,4}        1225: {3,3,4,4}
     484: {1,1,5,5}        1296: {1,1,1,1,2,2,2,2}
     504: {1,1,1,2,2,4}    1350: {1,2,2,2,3,3}
     540: {1,1,2,2,2,3}    1368: {1,1,1,2,2,8}
     600: {1,1,1,2,3,3}    1400: {1,1,1,3,3,4}
     676: {1,1,6,6}        1404: {1,1,2,2,2,6}
     756: {1,1,2,2,2,4}    1444: {1,1,8,8}
     792: {1,1,1,2,2,5}    1500: {1,1,2,3,3,3}
     936: {1,1,1,2,2,6}    1521: {2,2,6,6}
For example, a complete list of all factorizations of 7560 into squarefree semiprimes is:
  7560 = (6*6*6*35) = (6*6*10*21) = (6*6*14*15),
but since none of these is strict, 7560 is in the sequence.

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 distinct prime shadows (under A181819) of these terms are A339842.
Factorizations into squarefree semiprimes are counted by A320656.
Products of squarefree semiprimes that are not products of distinct semiprimes are A320893.
Factorizations into distinct squarefree semiprimes are A339661.
For the next four lines, we list numbers with even Omega (A028260).
- A320891 cannot be factored into squarefree semiprimes.
- A320894 cannot be factored into distinct squarefree semiprimes.
- A320911 can be factored into squarefree semiprimes.
- A339561 can be factored into distinct squarefree semiprimes.
A001358 lists semiprimes, with squarefree case A006881.
A002100 counts partitions into squarefree semiprimes.
A030229 lists squarefree numbers with even Omega.
A050320 counts factorizations into squarefree numbers.
A050326 counts factorizations into distinct squarefree numbers.
A181819 is the Heinz number of the prime signature of n (prime shadow).
A320656 counts factorizations into squarefree semiprimes.
A339560 can be partitioned into distinct strict pairs.
Cf. A001055, A001222, A005117, A007717, A096373, A112798, A300061, A322353, A339559, A338899, A339740.

strr[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strr[n/d],Min@@#>=d&]],{d,Select[Divisors[n],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];
Select[Range[1000],Select[strr[#],UnsameQ@@#&]=={}&&strr[#]!={}&]

Equals A320894 /\ A320911.

Numbers n such that A320656(n) > 0 but A339661(n) = 0.

cp's OEIS Frontend

A004251 Number of graphical partitions (degree-vectors for simple graphs with n vertices, or possible ordered row-sum vectors for a symmetric 0-1 matrix with diagonal values 0).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

A340017 Products of squarefree semiprimes that are not products of distinct squarefree semiprimes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula