|
| |
|
|
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)
|
|
16
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
In other words, a(n) = 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
|
|
|
REFERENCES
|
R. A. Brualdi, H. J. Ryser, Combinatorial Matrix Theory, Cambridge Univ. Press, 1992.
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, http://www.acta.sapientia.ro/acta-info/C4-1/info41-7.pdf. - From N. J. A. Sloane, Dec 22 2012
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
|
Table of n, a(n) for n=0..29.
T. M. Barnes and C. D. Savage, A recurrence for counting graphical partitions, Electronic J. Combinatorics, 2 (1995)
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.
Eric Weisstein's World of Mathematics, Degree Sequence.
Wolfram Mathworld, Graphic Sequence
Index entries for sequences related to graphical partitions
|
|
|
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
|
|
|
CROSSREFS
|
Cf. A000569, A004250, A004251, A029889.
Sequence in context: A148166 A148167 A148168 * A148169 A110140 A190452
Adjacent sequences: A004248 A004249 A004250 * A004252 A004253 A004254
|
|
|
KEYWORD
|
nonn,more,nice,hard
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from 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 (tony@inf.elte.hu), Nov 15 2011
|
|
|
STATUS
|
approved
|
| |
|
|
