

A000088


Number of graphs on n unlabeled nodes.
(Formerly M1253 N0479)


101



1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Euler transform of the sequence A001349.
Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.


REFERENCES

P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89102.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 30743077.
R. L. Davis, The numbers of structures of finite relations, Proc. Amer. Math. Soc., 4 (1953), 486494.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. AddisonWesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 25292571.
M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498500. MR0109796 (22 #681).
Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybemetics [in Russian], Moscow 4 (1960): 521.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 1422.
A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405469.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 5378.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, Igraphs and others, Croatica Chem. Acta, 78 (2005), 563567.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Enumeration of nonseparable graphs, J. Combin. Theory 9 (1970), 327356.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Turner, James; Kautz, William H. A survey of progress in graph theory in the Soviet Union. SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 18.


LINKS

Keith M. Briggs, Table of n, a(n) for n = 0..75 (From link below)
R. Absil and H MÃ©lot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993, 2013
Natalie Arkus, Vinothan N. Manoharan, Michael P. Brenner. Deriving Finite Sphere Packings, Nov 24, 2010. (See Table 1.)
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Singlequbit unitary gates by graph scattering, arXiv:1111.5032, 2011
Keith M. Briggs, Combinatorial Graph Theory [Gives first 140 terms]
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur and Hadrien Melot, House of Graphs: a database of interesting graphs, arXiv preprint arXiv:1204.3549, 2012.
P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191  208 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp. [Annotated scanned copy]
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th SE Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259271. (Annotated scanned copy of 3 pages)
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 105
E. Friedman, Illustration of small graphs
Harald Fripertinger, Graphs
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not PRecursive, preprint, 2015.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303, 2012.
S. Hougardy, Home Page
Vladeta Jovovic, Formulae for the number T(n,k) of nmultigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026, 2014
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 1422. [Annotated scanned copy]
Brendan McKay, Maple program (redirects to here.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
E. M. Palmer, Letter to N. J. A. Sloane, no date
Marko Riedel, Nonisomorphic graphs.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
J. M. Tangen and N. J. A. Sloane, Correspondence, 19761976
S. Uijlen, B. Westerbaan, A KochenSpecker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
Index entries for "core" sequences


FORMULA

a(n) = 2^binomial(n, 2)/n!*(1+(n^2n)/2^(n1)+8*n!/(n4)!*(3*n7)*(3*n9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference).  Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{n}+8/3*n$3*(3n7)*2^{2n}+64/3*n$4*(4n^234n+75)*2^{3n}+O(n^8*2^{4*n})] where n$k is the falling factorial: n$k=n(n1)(n2)...(nk+1).  Keith Briggs (keith.briggs(AT)bt.com), Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of tuniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n) per(c)*2^f(c), where:
..per(c) = 1/(Prod_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = LCM{i : c_i>0};
..y(r, k; c) = Sum_{sr : GCD(k, r/s)=1} s*c_(k*s) is the number of kcycles of the rth power of a permutation of type c.
(End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.].  N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18.  N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z)= (1/n!) Sum_g det(Ig z^2)/det(Ig z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83).  Leonid Bedratyuk, May 02 2015


MAPLE

# To produce all graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4, output=graphs, outputform=adjacency):


MATHEMATICA

Needs["Combinatorica`"]
Table[ NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)


PROG

(Sage)
def a(n):
return len(list(graphs(n)))
# Ralf Stephan, May 30 2014


CROSSREFS

Partial sums of A002494.
Cf. A001349 (connected graphs), A002218, A006290.
Second column of A063841.
Row sums of A008406.
Sequence in context: A178944 A076320 A076321 * A071794 A234006 A107378
Adjacent sequences: A000085 A000086 A000087 * A000089 A000090 A000091


KEYWORD

core,nonn,nice


AUTHOR

N. J. A. Sloane


EXTENSIONS

Harary gives an incorrect value for a(8); compare A007149


STATUS

approved



