|
| |
|
|
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).
(Formerly M1250)
|
|
24
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
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
|
|
|
REFERENCES
|
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).
|
|
|
LINKS
|
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)
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]
|
|
|
FORMULA
|
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
|
|
|
EXAMPLE
|
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
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)
|
|
|
MATHEMATICA
|
Table[Length[Union[Sort[Table[Count[Join@@#, i], {i, n}]]&/@Subsets[Subsets[Range[n], {2}]]]], {n, 0, 5}] (* Gus Wiseman, Dec 31 2020 *)
|
|
|
CROSSREFS
|
Counting the positive partitions by sum gives A000569, ranked by A320922.
The covering case (no zeros) is A095268.
Non-graphical partitions are counted by A339617 and ranked by A339618.
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.
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
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(30) and a(31) corrected by Wang Kai, Jun 05 2016
|
|
|
STATUS
|
approved
|
| |
|
|
