A006897 -id:A006897 - cp's OEIS frontend

A000088 Number of simple graphs on n unlabeled nodes.

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768

Offset: 0

N. J. A. Sloane

Euler transform of the sequence A001349.

Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
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 498--500. MR0109796 (22 #681).
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. 14-22.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
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).

Keith M. Briggs, Table of n, a(n) for n = 0..87 (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 [cs.DM], 2013.
Natalie Arkus, Vinothan N. Manoharan and Michael P. Brenner. Deriving Finite Sphere Packings, arXiv:1011.5412 [cond-mat.soft], Nov 24, 2010. (See Table 1.)
Leonid Bedratyuk and Anna Bedratyuk, A new formula for the generating function of the numbers of simple graphs, Comptes rendus de l'Académie Bulgare des Sciences, Tome 69, No 3, 2016, p.259-268.
Benjamin A. Blumer, Michael S. Underwood and David L. Feder, Single-qubit unitary gates by graph scattering, arXiv:1111.5032 [quant-ph], 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 [math.CO], 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, Some sequences of integers, Discrete Math., 75 (1989), 89-102.
P. J. Cameron, Some sequences of integers, in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron and C. R. Johnson, The number of equivalence patterns of symmetric sign patterns, Discr. Math., 306 (2006), 3074-3077.
Gi-Sang Cheon, Jinha Kim, Minki Kim and Sergey Kitaev, On k-11-representable graphs, arXiv:1803.01055 [math.CO], 2018.
CombOS - Combinatorial Object Server, Generate graphs
Karen M. Daehli, Sarah A Obead, Hsuan-Yin Lin, and Eirik Rosnes, Improved Capacity Outer Bound for Private Quadratic Monomial Computation, arXiv:2401.06125 [cs.IR], 2024.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271. (Annotated scanned copy of 3 pages)
Peter Dukes, Notes for Math 422: Enumeration and Ramsey Theory, University of Victoria BC Canada (2019). See page 36.
D. S. Dummit, E. P. Dummit and H. Kisilevsky, Characterizations of quadratic, cubic, and quartic residue matrices, arXiv preprint arXiv:1512.06480 [math.NT], 2015.
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, and Kristina Wicke, Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones, arXiv:1810.06853 [q-bio.PE], 2018.
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 P-Recursive, preprint, 2015.
Lee M. Gunderson and Gecia Bravo-Hermsdorff, Introducing Graph Cumulants: What is the Variance of Your Social Network?, arXiv:2002.03959 [math.ST], 2020.
P. Hegarty, On the notion of balance in social network analysis, arXiv preprint arXiv:1212.4303 [cs.SI], 2012.
S. Hougardy, Home Page
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
Richard Hua and Michael J. Dinneen, Improved QUBO Formulation of the Graph Isomorphism Problem, SN Computer Science (2020) Vol. 1, No. 19.
A. Itzhakov and M. Codish, Breaking Symmetries in Graph Search with Canonizing Sets, arXiv preprint arXiv:1511.08205 [cs.AI], 2015-2016.
Dan-Marian Joiţa and Lorentz Jäntschi, Extending the Characteristic Polynomial for Characterization of C_20 Fullerene Congeners, Mathematics (2017), 5(4), 84.
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes
Maksim Karev, The space of framed chord diagrams as a Hopf module, arXiv preprint arXiv:1404.0026 [math.GT], 2014.
J. M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
Steffen Lauritzen, Alessandro Rinaldo and Kayvan Sadeghi, On Exchangeability in Network Models, arXiv:1709.03885 [math.ST], 2017.
O. B. Lupanov, On asymptotic estimates of the number of graphs and networks with n edges, Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
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. 14-22. [Annotated scanned copy]
B. D. McKay, Maple program (used to redirect to here).
B. D. McKay, Maple program [Cached copy, with permission]
B. D. McKay, Simple graphs
A. Milicevic and N. Trinajstic, Combinatorial Enumeration in Chemistry, Chem. Modell., Vol. 4, (2006), pp. 405-469.
Angelo Monti and Blerina Sinaimeri, Effects of graph operations on star pairwise compatibility graphs, arXiv:2410.16023 [cs.DM], 2024. See p. 16.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
M. Petkovsek and T. Pisanski, Counting disconnected structures: chemical trees, fullerenes, I-graphs and others, Croatica Chem. Acta, 78 (2005), 563-567.
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.
Marko Riedel, Compact Maple code for cycle index, sequence values and ordinary generating function by the number of edges.
R. W. Robinson, Enumeration of non-separable graphs, J. Combin. Theory 9 (1970), 327-356.
Sage, Common Graphs (Graph Generators)
S. S. Skiena, Generating graphs
N. J. A. Sloane, Illustration of initial terms
Quico Spaen, Christopher Thraves Caro and Mark Velednitsky, The Dimension of Valid Distance Drawings of Signed Graphs, Discrete & Computational Geometry (2019), 1-11.
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]
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Overview of the 17 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 12
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 13
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 14
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 15
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 16
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
James Turner and William H. Kautz, 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.
S. Uijlen and B. Westerbaan, A Kochen-Specker system has at least 22 vectors, arXiv preprint arXiv:1412.8544 [cs.DM], 2014.
Mark Velednitsky, New Algorithms for Three Combinatorial Optimization Problems on Graphs, Ph. D. Dissertation, University of California, Berkeley (2020).
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Degree Sequence
E. M. Wright, The number of graphs on many unlabelled nodes, Mathematische Annalen, December 1969, Volume 183, Issue 4, 250-253
E. M. Wright, The number of unlabelled graphs with many nodes and edges Bull. Amer. Math. Soc. Volume 78, Number 6 (1972), 1032-1034.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for "core" sequences

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

# To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019

Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)

permcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=t*k;s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(n): return int(sum(Fraction(1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items()),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 02 2024

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

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/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*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, 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 t-uniform 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/(Product_{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_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th 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(I-g z^2)/det(I-g 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
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
   1+
   2^(  -n +  1)*n$2+
   2^(-2*n +  3)*n$3*(n-7/3)+
   2^(-3*n +  6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
   2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
   2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
   2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

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

A006896 a(n) is the number of hierarchical linear models on n labeled factors allowing 2-way interactions (but no higher order interactions); or the number of simple labeled graphs with nodes chosen from an n-set.

Original entry on oeis.org

1, 2, 5, 18, 113, 1450, 40069, 2350602, 286192513, 71213783666, 35883905263781, 36419649682706466, 74221659280476136241, 303193505953871645562970, 2480118046704094643352358501, 40601989176407026666590990422106, 1329877330167226219547875498464516481

Offset: 0

N. J. A. Sloane, Colin Mallows, Simon Plouffe

From Petros Hadjicostas, Apr 09 2020: (Start)
Hierarchical log-linear models are by definition nonempty because they always include an "intercept" (or "overall effect").
Note that this is different from the number of graphical hierarchical log-linear models on n labeled factors as defined in the referenced Wikipedia article about log-linear models, "A log-linear model is graphical if, whenever the model contains all two-factor terms generated by a higher-order interaction, the model also contains the higher-order interaction." See also Gauraha (2016). (End) (Comment revised by N. J. A. Sloane, Apr 23 2020.)

			From _Petros Hadjicostas_, Apr 09 2020: (Start)
For n = 2, consider the pair of nodes {X, Y}. The simple labeled graphs with nodes from this set are the empty graph G1 = [], G2 = [X], G3 = [Y], G4 = [X, Y], and G5 = [X, Y, X-Y]. Thus a(2) = 5.
For n = 3, consider the three nodes {X, Y, Z}. The simple labeled graphs with nodes from this set are G1 = [], G2 = [X], G3 = [Y], G4 = [Z], G5 = [X, Y], G6 = [X, Z], G7 = [Y, Z], G8 = [X, Y, X-Y], G9 = [X, Z, X-Z], G10 = [Y, Z, Y-Z], G11 = [X, Y, Z], G12 = [X-Y Z], G13 = [X, Y,Z, X-Z], G14 = [X, Y, Z, Y-Z ], G15 = [X, Y, Z, Y-X-Z], G16 = [X, Y, Z, X-Y-Z], G17 = [Z, Y, Z, X-Z-Y], and G18 = [X, Y, Z, triangle with nodes X, Y, Z]. Thus a(3) = 18.
In Wickramasinghe (2008), for n = 2, all A014466(2) = 5 hierarchical log-linear models on two factors X and Y, which appear on p. 18, are trivially graphical; thus a(2) = 5.
For n = 3, among the A014466(3) = 19 hierarchical log-linear models on three factors X, Y, and Z, which appear on p. 36, only Model 18 is not graphical because it contains the X-Y, Y-Z, and Z-X interactions but does not contain the 3-way X-Y-Z interaction; thus a(3) = 19 - 1 = 18. (End)

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

Vincenzo Librandi, Table of n, a(n) for n = 0..80
P. De Causmaecker and S. De Wannemacker, Decomposition of Intervals in the Space of Anti-Monotonic Functions, in Manuel Ojeda-Aciego, Jan Outrata (Eds.): CLA 2013, pp. 57-67, Laboratory L3i, University of La Rochelle, 2013.
Patrick De Causmaecker and Stefan De Wannemacker, On the number of antichains of sets in a finite universe, arXiv:1407.4288 [math.CO], 2014.
Niharika Gauraha, Graphical log-linear models: Fundamental concepts and applications, arXiv:1603.04122 [stat.ME], 2016.
Y. Nardi and A. Rinaldo, The log-linear group-lasso estimator and its asymptotic properties, Bernoulli 18(3) (2012), 945-974; see footnote 1 on p. 953 and Table 2 on p. 954.
Gete Umbrey and Saifur Rahman, Application of Graph Semirings in Decision Networks, Mathematical Forum (2021) Vol. 28, 40-51.
R. I. P. Wickramasinghe, Topics in log-linear models, Master of Science thesis in Statistics, Texas Tech University, Lubbock, TX, 2008.
Wikipedia, Log-linear analysis.

Cf. A004140, A006897 (unlabeled case).

A006896 := proc(n) local k; 1+binomial(n,1) +add(binomial(n,k)*2^(1/2*k*(k-1)), k = 2 .. n) end; seq (A006896(n), n=0..20);

nn=20;g=Sum[2^Binomial[n,2]x^n/n!,{n,0,nn}];Range[0,nn]! CoefficientList[Series[Exp[x]g,{x,0,nn}],x]  (* Geoffrey Critzer, Apr 11 2012 *)

a(n)=sum(k=0,n,binomial(n,k)*2^((k^2-k)/2))

a(n) = 1 + C(n, 1) + C(n, 2)*2 + C(n, 3)*2^3 + C(n, 4)*2^6 + ... + C(n, n)*2^(n*(n-1)/2).
a(n) = 1 + A004140(n).
E.g.f.: exp(x)*A(x) where A(x) is e.g.f. for A006125. - Geoffrey Critzer, Apr 11 2012.

Error in formula line corrected Sep 15 1997 (thanks to R. K. Guy for pointing this out)
Name expanded by Petros Hadjicostas, Apr 08 2020
Edited by N. J. A. Sloane, Apr 23 2020

A371161 Maximum number of unlabeled graphs with at most n nodes such that neither one is a subgraph of another.

Original entry on oeis.org

1, 1, 1, 2, 3, 7, 26, 157, 1687

Offset: 0

Max Alekseyev, Mar 13 2024

Width of the poset of unlabeled graphs of order at most n with the subgraph relationship.

a(n) >= A000717(n).

Cf. A000717, A006897, A371162.

A006898 a(n) = Sum_{k=0..n} C(n,k)2^(k(k+1)/2).

Original entry on oeis.org

1, 3, 13, 95, 1337, 38619, 2310533, 283841911, 70927591153, 35812691480115, 36383765777442685, 74185239630793429775, 303119284294591169426729, 2479814853198140771706795531, 40599509058360322571947638063605

Offset: 0

Colin Mallows

nonn

First differences of A006896.

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

Cf. A006896, A006897, A135748.

Table[Sum[Binomial[n,k]2^((k(k+1))/2),{k,0,n}],{n,0,20}] (* Harvey P. Dale, Apr 01 2023 *)

a(n)=sum(k=0,n,binomial(n,k)*2^(k*(k+1)/2)) \\ Paul D. Hanna, Apr 10 2009

a(n) ~ 2^(n*(n+1)/2). - Vaclav Kotesovec, Nov 27 2017

Formula and more terms from Vladeta Jovovic, Sep 20 2003

Edited by N. J. A. Sloane, Apr 12 2009 at the suggestion of Vladeta Jovovic

A376782 Triangle read by rows: T(n,m) is the number of unlabeled graphs with n vertices having m minimum forbidden subgraphs, n >= 1, 1 <= m <= A371162(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 4, 4, 2, 1, 4, 8, 13, 8, 1, 4, 5, 7, 20, 34, 31, 28, 12, 8, 5, 0, 1, 1, 4, 5, 13, 26, 33, 43, 59, 50, 62, 58, 60, 64, 67, 63, 70, 68, 65, 61, 60, 31, 28, 16, 8, 13, 4, 4, 4, 0, 2, 1, 0, 1, 1, 4, 6, 9, 21, 34, 39, 71, 74, 77, 99, 118, 124, 107, 129

Offset: 1

Max Alekseyev, Oct 03 2024

			Triangle starts with
n = 1: 1
n = 2: 1 1
n = 3: 1 3
n = 4: 1 4 4  2
n = 5: 1 4 8 13  8
n = 6: 1 4 5  7 20 34 31 28 12 8 5 0 1
...

Max Alekseyev, Table of k, a(k) for k = 1..209 (rows n = 1..8 flattened)
Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A000088 (row sums), A371162 (row lengths), A000012 (column m=1), A113311 (column m=2).

Cf. A002865, A006897, A103221, A371161, A376780, A376781.

A353213 Number of simple unlabeled non-null graphs on <= n nodes.

Original entry on oeis.org

1, 3, 7, 18, 52, 208, 1252, 13598, 288266, 12293434, 1031291298, 166122463890, 50668153831842, 29104823811067330, 31455590793615376098, 64032471295321173271026, 245999896624828253856990802, 1787823725042236528801735181650, 24639597076850046760911809226614418, 645514762392876691902925550299969363858

Offset: 1

Eric W. Weisstein, Apr 30 2022

nonn

Also the number of (non-null) graph minors of the complete graph K_n.

Eric W. Weisstein, Table of n, a(n) for n = 1..87
Eric Weisstein's World of Mathematics, Graph Minor
Eric Weisstein's World of Mathematics, Simple Graph

Cf. A000088 (number of simple graphs on n nodes).

Cf. A006897 (number of simple graphs on 0 to n nodes).

a(n) = A006897(n) - 1.

a(n) = Sum_{k=1..n} A000088(k).

A376780 Triangular table read by rows: T(n,k) is the minimum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 1, 2, 3, 2, 3, 2, 2, 1, 2, 3, 2, 3, 3, 4, 3, 3, 2, 2, 1, 2, 3, 3, 2, 4, 3, 4, 5, 5, 4, 5, 5, 4, 2, 2, 1, 2, 3, 3, 2, 4, 4, 3, 4, 5, 4, 5, 5, 7, 6, 6, 5, 5, 4, 4, 2, 2, 1, 2, 3, 3, 3, 2, 4, 4, 3, 5, 6, 5, 6, 5, 5, 7, 6, 7, 10, 9, 9, 9, 8, 10, 5, 5, 4, 2, 2, 1

Offset: 1

Max Alekseyev, Oct 03 2024

			Table starts with
n = 1: 1
n = 2: 2, 1
n = 3: 2, 2, 2, 1
n = 4: 2, 3, 2, 3, 2, 2, 1
...

Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A002865, A006897, A103221, A371161, A371162, A376781, A376782.

A376781 Triangular table read by rows: T(n,k) is the maximum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Original entry on oeis.org

1, 2, 1, 2, 2, 2, 1, 2, 3, 4, 4, 3, 2, 1, 2, 3, 4, 5, 5, 5, 5, 4, 3, 2, 1, 2, 3, 4, 6, 8, 8, 9, 13, 11, 11, 9, 6, 5, 3, 2, 1, 2, 3, 4, 6, 8, 8, 11, 16, 20, 23, 28, 31, 30, 33, 24, 22, 15, 10, 7, 3, 2, 1, 2, 3, 4, 6, 8, 9, 14, 21, 24, 31, 41, 57, 78, 86, 106, 123, 134, 149, 143, 138, 133, 75, 46, 37, 18, 11, 3, 2, 1

Offset: 1

Max Alekseyev, Oct 03 2024

			Table starts with
n = 1: 1
n = 2: 2, 1
n = 3: 2, 2, 2, 1
n = 4: 2, 3, 4, 4, 3, 2, 1
...

Max A. Alekseyev and Allan Bickle, Forbidden Subgraphs of Single Graphs, 2024.

Cf. A371162 (row maximums).

Cf. A002865, A006897, A103221, A371161, A376780, A376782.

A217653 Triangular array read by rows: T(n,k) is the number of unlabeled simple graphs with n nodes that have exactly k isolated nodes, (n>=0, 0<=k<=n).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 7, 2, 1, 0, 1, 23, 7, 2, 1, 0, 1, 122, 23, 7, 2, 1, 0, 1, 888, 122, 23, 7, 2, 1, 0, 1, 11302, 888, 122, 23, 7, 2, 1, 0, 1, 262322, 11302, 888, 122, 23, 7, 2, 1, 0, 1, 11730500, 262322, 11302, 888, 122, 23, 7, 2, 1, 0, 1

Offset: 0

Geoffrey Critzer, Oct 09 2012

Row sums = A000088.
Sum_{k=1..n} T(n,k)*k = A006897(n).
Column k = 0 is A002494.

			1,
0, 1,
1, 0, 1,
2, 1, 0, 1,
7, 2, 1, 0, 1,
23, 7, 2, 1, 0, 1,
122, 23, 7, 2, 1, 0, 1

Cf. A000088, A002494, A006897.

Needs["Combinatorica`"]; nn=10; s=Sum[NumberOfGraphs[n]x^n, {n,0,nn}]; CoefficientList[Series[s (1-x)/(1-y x), {x,0,nn}], {x,y}] //Grid

O.g.f.: A(x)/(1-y*x) where A(x) is o.g.f. for A002494.

A386399 Number of forests with at most n unlabeled nodes.

Original entry on oeis.org

1, 2, 4, 7, 13, 23, 43, 80, 156, 309, 638, 1348, 2949, 6607, 15206, 35720, 85625, 208588, 515787, 1291316, 3269194, 8355832, 21539988, 55942920, 146271594, 384746580, 1017522228, 2704227858, 7219183490, 19351410860, 52068524665, 140588391713, 380824067016

Offset: 0

Max Alekseyev, Jul 20 2025

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Partial sums of A005195.

Cf. A000272, A002807, A006897, A054548, A137917, A367863, A372176.

G.f.: exp(sum_{k>0} B(x^k)/k ) / (1-x), where B(x) = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + ... = C(x)-1 and C is the g.f. for A000055.

cp's OEIS Frontend

A000088 Number of simple graphs on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A006896 a(n) is the number of hierarchical linear models on n labeled factors allowing 2-way interactions (but no higher order interactions); or the number of simple labeled graphs with nodes chosen from an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A371161 Maximum number of unlabeled graphs with at most n nodes such that neither one is a subgraph of another.

Views

Author

Keywords

Comments

Crossrefs

A006898 a(n) = Sum_{k=0..n} C(n,k)*2^(k*(k+1)/2).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A376782 Triangle read by rows: T(n,m) is the number of unlabeled graphs with n vertices having m minimum forbidden subgraphs, n >= 1, 1 <= m <= A371162(n).

Views

Author

Keywords

Examples

Links

Crossrefs

A353213 Number of simple unlabeled non-null graphs on <= n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A376780 Triangular table read by rows: T(n,k) is the minimum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

A376781 Triangular table read by rows: T(n,k) is the maximum number of minimal forbidden subgraphs of a graph with n vertices and k edges, n >= 1, 0 <= k <= n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

A217653 Triangular array read by rows: T(n,k) is the number of unlabeled simple graphs with n nodes that have exactly k isolated nodes, (n>=0, 0<=k<=n).

A006898 a(n) = Sum_{k=0..n} C(n,k)2^(k(k+1)/2).