login
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).
(Formerly M1250)
24

%I M1250 #122 Jan 20 2023 05:39:05

%S 1,1,2,4,11,31,102,342,1213,4361,16016,59348,222117,836315,3166852,

%T 12042620,45967479,176005709,675759564,2600672458,10029832754,

%U 38753710486,149990133774,581393603996,2256710139346,8770547818956,34125389919850,132919443189544,518232001761434,2022337118015338,7898574056034636,30873421455729728

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

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

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

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

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

%H Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, <a href="/A004251/b004251.txt">Table of n, a(n) for n = 0..1651</a> (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)

%H Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, <a href="https://arxiv.org/abs/2301.07022">Counting graphic sequences via integrated random walks</a>, arXiv:2301.07022 [math.CO], 2023.

%H T. M. Barnes and C. D. Savage, <a href="https://doi.org/10.37236/1205">A recurrence for counting graphical partitions</a>, Electronic J. Combinatorics, 2 (1995), #R11.

%H B. A. Chat, S. Pirzada, and A. Iványi, <a href="http://dx.doi.org/10.1515/ausi-2015-0007">Recognition of split-graphic sequences</a>, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.

%H D. Dimitrov, <a href="http://arxiv.org/abs/1305.1155">Efficient computation of trees with minimal atom-bond connectivity index</a>, arXiv:1305.1155 [cs.DM], 2013.

%H A. Iványi, L. Lucz, T. F. Móri and P. Sótér, <a href="http://www.acta.sapientia.ro/acta-info/C3-2/info32-7.pdf">On Erdős-Gallai and Havel-Hakimi algorithms</a>, Acta Univ. Sapientiae, Inform. 3(2) (2011), 230-268.

%H A. Ivanyi, L. Lucz, T. Matuszka, and S. Pirzada, <a href="http://www.acta.sapientia.ro/acta-info/C4-2/info42-7.pdf">Parallel enumeration of degree sequences of simple graphs</a>, Acta Univ. Sapientiae, Informatica, 4, 2 (2012), 260-288. - From _N. J. A. Sloane_, Feb 15 2013

%H A. Ivanyi and J. E. Schoenfield, <a href="http://www.acta.sapientia.ro/acta-info/C4-1/info41-7.pdf">Deciding football sequences</a>, 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 <a href="https://oeis.org/wiki/User:Jon_E._Schoenfield">here</a>. - _Jon E. Schoenfield_, Nov 26 2016]

%H Wang Kai, <a href="https://arxiv.org/abs/1604.04148">Efficient Counting of Degree Sequences</a>, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms.

%H P. W. Mills, R. P. Rundle, V. M. Dwyer, T. Tilma, and S. J. Devitt, <a href="https://arxiv.org/abs/1711.09842">A proposal for an efficient quantum algorithm solving the graph isomorphism problem</a>, arXiv 1711.09842, 2017.

%H P. R. Stein, <a href="/A004250/a004250.pdf">On the number of graphical partitions</a>, pp. 671-684 of Proc. 9th S-E Conf. Combinatorics, Graph Theory, Computing, Congr. Numer. 21 (1978). [Annotated scanned copy]

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

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

%H Gus Wiseman, <a href="/A339741/a339741_1.txt">Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.</a>

%H <a href="/index/Gra#graph_part">Index entries for sequences related to graphical partitions</a>

%F 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 + ...

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

%e 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

%e From _Gus Wiseman_, Dec 31 2020: (Start)

%e The a(0) = 1 through a(4) = 11 sorted degree sequences:

%e () (0) (0,0) (0,0,0) (0,0,0,0)

%e (1,1) (0,1,1) (0,0,1,1)

%e (1,1,2) (0,1,1,2)

%e (2,2,2) (0,2,2,2)

%e (1,1,1,1)

%e (1,1,1,3)

%e (1,1,2,2)

%e (1,2,2,3)

%e (2,2,2,2)

%e (2,2,3,3)

%e (3,3,3,3)

%e For example, the graph {{2,3},{2,4}} has degrees (0,2,1,1), so (0,1,1,2) is counted under a(4).

%e (End)

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

%Y Counting the positive partitions by sum gives A000569, ranked by A320922.

%Y The version with half-loops is A029889, with covering case A339843.

%Y The covering case (no zeros) is A095268.

%Y Covering simple graphs are ranked by A309356 and A320458.

%Y Non-graphical partitions are counted by A339617 and ranked by A339618.

%Y The version with loops is A339844, with covering case A339845.

%Y A006125 counts simple graphs, with covering case A006129.

%Y A027187 counts partitions of even length, ranked by A028260.

%Y A058696 counts partitions of even numbers, ranked by A300061.

%Y A320921 counts connected graphical partitions.

%Y A322353 counts factorizations into distinct semiprimes.

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

%Y A339661 counts factorizations into distinct squarefree semiprimes.

%Y Cf. A004250, A007717, A181819, A320894, A320923, A339560, A339561, A339842.

%K nonn,nice

%O 0,3

%A _N. J. A. Sloane_

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

%E a(19) from Herman Jamke (hermanjamke(AT)fastmail.fm), May 19 2007

%E a(20)-a(23) from _Nathann Cohen_, Jul 09 2011

%E a(24)-a(29) from _Antal Iványi_, Nov 15 2011

%E a(30) and a(31) corrected by _Wang Kai_, Jun 05 2016