A000055 -id:A000055 - cp's OEIS frontend

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320

Offset: 1

N. J. A. Sloane and John Riordan

Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014
Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

			G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.
D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
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).

N. J. A. Sloane, First 1001 terms of A000669
Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner, On the generation of rank 3 simple matroids with an application to Terao's freeness conjecture, arXiv:1907.01073 [math.CO], 2019.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See pp. 155, 162, 165, 172. - _N. J. A. Sloane_, Apr 18 2014
Peter J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong, Obstructions for three-coloring graphs without induced paths on six vertices, arXiv preprint arXiv:1504.06979 [math.CO], 2015-2018.
Steven R. Finch, Series-parallel networks
Steven R. Finch, Series-parallel networks, July 7, 2003. [Cached copy, with permission of the author]
Steven R. Finch, Mathematical Constants II, Encyclopedia of Mathematics and Its Applications, Cambridge University Press, Cambridge, 2018.
Philippe Flajolet, A Problem in Statistical Classification Theory
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 72
Daniel L. Geisler, Combinatorics of Iterated Functions
A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 9.
O. Golinelli, Asymptotic behavior of two-terminal series-parallel networks, arXiv:cond-mat/9707023 [cond-mat.stat-mech], 1997.
JiSun Huh and Seonjeong Park, Toric varieties of Schröder type, arXiv:2204.00214 [math.AG], 2022. (Table 1)
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 44 [broken link].
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
P. A. MacMahon, Yoke-trains and multipartite compositions in connexion with the analytical forms called "trees", Proc. London Math. Soc. 22 (1891), 330-346; reprinted in Coll. Papers I, pp. 600-616. Page 333 gives A000084 = 2*A000669.
Arnau Mir, Francesc Rossello, and Lucia Rotger, Sound Colless-like balance indices for multifurcating trees, arXiv:1805.01329 [q-bio.PE], 2018.
V. Modrak and D. Marton, Development of Metrics and a Complexity Scale for the Topology of Assembly Supply Chains, Entropy 2013, 15, 4285-4299.
J. W. Moon, Some enumerative results on series-parallel networks, Annals Discrete Math., 33 (1987), 199-226.
Vlady Ravelomanana and Loys Thimonier, Asymptotic enumeration of cographs, Electronic Notes in Discrete Mathematics, Volume 7, April 2001, pp. 58-61, Theorem 4.
J. Riordan, The blossoming of Schröder's fourth problem, Acta Math., 137 (1976), 1-16. (page 6)
J. Riordan, Letter to N. J. A. Sloane, Sep. 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1970
Audace Amen Vioutou Dossou-Olory, and Stephan Wagner, Inducibility of Topological Trees, arXiv:1802.06696 [math.CO], 2018.
Audace Amen Vioutou Dossou-Olory, The topological trees with extremal Matula numbers, arXiv:1806.03995 [math.CO], 2018.
Wei Wang and Ximei Huang, Almost all cographs have a cospectral mate, arXiv:2507.16730 [math.CO], 2025. See pp. 6, 8.
Eric Weisstein's World of Mathematics, Series-Parallel Network
Index entries for sequences related to rooted trees
Index entries for sequences mentioned in Moon (1987)
Index entries for sequences related to trees

Equals (1/2)*A000084 for n >= 2.
Cf. A000055, A000311, A001678, A007827, A363064.
Cf. A000311, labeled hierarchies on n points.
Column 1 of A319254.
Main diagonal of A292085.
Row sums of A292086.

Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,b); a := [op(a),t3]; od: A000669 := n-> a[n];
Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;
Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)

{a(n) = my(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Jul 25 2003 */

from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... [Ravelomanana and Thimonier, 2001]. - Vaclav Kotesovec, Aug 25 2014
Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - Thomas Anton, Nov 22 2018

Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009

A000798 Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.

Original entry on oeis.org

1, 1, 4, 29, 355, 6942, 209527, 9535241, 642779354, 63260289423, 8977053873043, 1816846038736192, 519355571065774021, 207881393656668953041, 115617051977054267807460, 88736269118586244492485121, 93411113411710039565210494095, 134137950093337880672321868725846, 261492535743634374805066126901117203

Offset: 0

N. J. A. Sloane

From Altug Alkan, Dec 18 2015 and Feb 28 2017: (Start)
a(p^k) == k+1 (mod p) for all primes p. This is proved by Kizmaz at On The Number Of Topologies On A Finite Set link. For proof see Theorem 2.4 in page 2 and 3. So a(19) == 2 (mod 19).
a(p+n) == A265042(n) (mod p) for all primes p. This is also proved by Kizmaz at related link, see Theorem 2.7 in page 4. If n=2 and p=17, a(17+2) == A265042(2) (mod 17), that is a(19) == 51 (mod 17). So a(19) is divisible by 17.
In conclusion, a(19) is a number of the form 323*n - 17. (End)
The BII-numbers of finite topologies without their empty set are given by A326876. - Gus Wiseman, Aug 01 2019
From Tian Vlasic, Feb 23 2022: (Start)
Although no general formula is known for a(n), by considering the number of topologies with a fixed number of open sets, it is possible to explicitly represent the sequence in terms of Stirling numbers of the second kind.
For example: a(n,3) = 2*S(n,2), a(n,4) = S(n,2) + 6*S(n,3), a(n,5) = 6*S(n,3) + 24*S(n,4).
Lower and upper bounds are known: 2^n <= a(n) <= 2^(n*(n-1)), n > 1.
This follows from the fact that there are 2^(n*(n-1)) reflexive relations on a set with n elements.
Furthermore: a(n+1) <= a(n)*(3a(n)+1). (End)

			From _Gus Wiseman_, Aug 01 2019: (Start)
The a(3) = 29 topologies are the following (empty sets not shown):
  {123}  {1}{123}   {1}{12}{123}  {1}{2}{12}{123}   {1}{2}{12}{13}{123}
         {2}{123}   {1}{13}{123}  {1}{3}{13}{123}   {1}{2}{12}{23}{123}
         {3}{123}   {1}{23}{123}  {2}{3}{23}{123}   {1}{3}{12}{13}{123}
         {12}{123}  {2}{12}{123}  {1}{12}{13}{123}  {1}{3}{13}{23}{123}
         {13}{123}  {2}{13}{123}  {2}{12}{23}{123}  {2}{3}{12}{23}{123}
         {23}{123}  {2}{23}{123}  {3}{13}{23}{123}  {2}{3}{13}{23}{123}
                    {3}{12}{123}
                    {3}{13}{123}        {1}{2}{3}{12}{13}{23}{123}
                    {3}{23}{123}
(End)

K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 229.
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 243.
Levinson, H.; Silverman, R. Topologies on finite sets. II. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 699--712, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561090 (81c:54006)
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).
For further references concerning the enumeration of topologies and posets see under A001035.
G.H. Patil and M.S. Chaudhary, A recursive determination of topologies on finite sets, Indian Journal of Pure and Applied Mathematics, 26, No. 2 (1995), 143-148.

V. I. Arnautov and A. V. Kochina, Method for constructing one-point expansions of a topology on a finite set and its applications, Bul. Acad. Stiinte Republ. Moldav. Matem. 3 (64) (2010) 67-76.
Moussa Benoumhani, The Number of Topologies on a Finite Set, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.6.
Moussa Benoumhani and Ali Jaballah, Chains in lattices of mappings and finite fuzzy topological spaces, Journal of Combinatorial Theory, Series A (2019) Vol. 161, 99-111.
M. Benoumhani and M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5.
Juliana Bowles and Marco B. Caminati, A Verified Algorithm Enumerating Event Structures, arXiv:1705.07228 [cs.LO], 2017.
Gunnar Brinkmann and Brendan D. McKay, Posets on up to 16 points.
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179 (Table IV).
J. I. Brown and S. Watson, The number of complements of a topology on n points is at least 2^n (except for some special cases), Discr. Math., 154 (1996), 27-39.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
S. D. Chatterji, The number of topologies on n points, Manuscript, 1966 [Annotated scanned copy]
Tyler Clark and Tom Richmond, The Number of Convex Topologies on a Finite Totally Ordered Set, 2013, Involve, Vol. 8 (2015), No. 1, 25-32.
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259.
M. Erné, Struktur- und Anzahlformeln für Topologien auf Endlichen Mengen, Manuscripta Math., 11 (1974), 221-259. (Annotated scanned copy)
M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
M. Erné and K. Stege, Counting Finite Posets and Topologies, Order, 8 (1991), 247-265.
J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313. [Annotated scanned copy]
J. W. Evans, F. Harary and M. S. Lynn, On the computer enumeration of finite topologies, Commun. ACM, 10 (1967), 295-297, 313.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
Loic Foissy, Claudia Malvenuto, and Frederic Patras, B_infinity-algebras, their enveloping algebras, and finite spaces, arXiv preprint arXiv:1403.7488 [math.AT], 2014.
Loic Foissy, Claudia Malvenuto, and Frederic Patras, Infinitesimal and B_infinity-algebras, finite spaces, and quasi-symmetric functions, Journal of Pure and Applied Algebra, Elsevier, 2016, 220 (6), pp. 2434-2458. .
L. Foissy and C. Malvenuto, The Hopf algebra of finite topologies and T-partitions, arXiv preprint arXiv:1407.0476 [math.RA], 2014.
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
S. Giraudo, J.-G. Luque, L. Mignot and F. Nicart, Operads, quasiorders and regular languages, arXiv preprint arXiv:1401.2010 [cs.FL], 2014.
D. J. Greenhoe, Properties of distance spaces with power triangle inequalities, ResearchGate, 2015.
J. Heitzig and J. Reinhold, The number of unlabeled orders on fourteen elements, Order 17 (2000) no. 4, 333-341.
Institut f. Mathematik, Univ. Hanover, Erne/Heitzig/Reinhold papers
G. A. Kamel, Partial Chain Topologies on Finite Sets, Computational and Applied Mathematics Journal. Vol. 1, No. 4, 2015, pp. 174-179.
Dongseok Kim, Young Soo Kwon and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550[math.CO], 2012.
M. Y. Kizmaz, On The Number Of Topologies On A Finite Set, arXiv preprint arXiv:1503.08359 [math.NT], 2015-2019.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
D. J. Kleitman and B. L. Rothschild, The number of finite topologies, Proc. Amer. Math. Soc., 25 (1970), 276-282.
Messaoud Kolli, Direct and Elementary Approach to Enumerate Topologies on a Finite Set, J. Integer Sequences, Volume 10, 2007, Article 07.3.1.
Messaoud Kolli, On the cardinality of the T_0-topologies on a finite set, International Journal of Combinatorics, Volume 2014 (2014), Article ID 798074, 7 pages.
Sami Lazaar, Houssem Sabri, and Randa Tahri, Structural and Numerical Studies of Some Topological Properties for Alexandroff Spaces, Bull. Iran. Math. Soc. (2021).
Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
M. Rayburn, On the Borel fields of a finite set, Proc. Amer. Math.. Soc., 19 (1968), 885-889. [Annotated scanned copy]
M. Rayburn and N. J. A. Sloane, Correspondence, 1974
D. Rusin, More info and references [Broken link]
D. Rusin, More info and references [Cached copy]
A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198. [Annotated scanned copy]
A. Shafaat, On the number of topologies definable for a finite set, J. Austral. Math. Soc., 8 (1968), 194-198.
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
N. J. A. Sloane, Classic Sequences
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 8 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Swartz and Nicholas J. Werner, Zero pattern matrix rings, reachable pairs in digraphs, and Sharp's topological invariant tau, arXiv:1709.05390 [math.CO], 2017.
Ivo Terek, Smooth Manifolds, Williams College (2025). See p. 6.
Wietske Visser, Koen V. Hindriks and Catholijn M. Jonker, Goal-based Qualitative Preference Systems, 2012.
N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
J. A. Wright, Letter to N. J. A. Sloane, Nov 21 1970, with four enclosures
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
J. A. Wright, Two related abstracts, 1970 and 1972 [Annotated scanned copies]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Index entries for "core" sequences

Row sums of A326882.
Cf. A001035 (labeled posets), A001930 (unlabeled topologies), A000112 (unlabeled posets), A006057.
Sequences in the Erné (1974) paper: A000798, A001035, A006056, A006057, A001929, A001927, A006058, A006059, A000110.
Cf. A102894, A102895, A102897, A306445, A326866, A326876, A326878, A326881.

Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&SubsetQ[#,Union[Union@@@Tuples[#,2],DeleteCases[Intersection@@@Tuples[#,2],{}]]]&]],{n,0,3}] (* Gus Wiseman, Aug 01 2019 *)

a(n) = Sum_{k=0..n} Stirling2(n, k)*A001035(k).
E.g.f.: A(exp(x) - 1) where A(x) is the e.g.f. for A001035. - Geoffrey Critzer, Jul 28 2014
It is known that log_2(a(n)) ~ n^2/4. - Tian Vlasic, Feb 23 2022

Two more terms from Jobst Heitzig (heitzig(AT)math.uni-hannover.de), Jul 03 2000

a(17)-a(18) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jun 10 2007

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221, 402, 663, 980, 1312, 1557, 1646, 1557

Offset: 1

N. J. A. Sloane, Mar 15 1996

T(n,k)=1 for n>=2 with k=0, k=1, k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the quadruple {1,1,1,1} marks the transition to the next sublist for a given number of vertices (n>2)). [Edited by Peter Munn, Mar 20 2021]

			Triangle begins:
1,
1,1,
1,1,1,1,
1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
1,1,2,4,6,6,6,4,2,1,1,
1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,
1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,
...

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
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.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, Rows 1 to 20 of triangle, flattened
Leonid Bedratyuk, A new formula for the generating function of the numbers of simple graphs, arXiv:1512.06355 [math.CO], 2015.
FindStat - Combinatorial Statistic Finder, The number of edges of a graph.
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO] (2017) Table 65.
Sriram V. Pemmaraju, Combinatorica 2.0
Marko R. Riedel, Number of distinct connected digraphs
Gordon Royle, Small graphs
S. S. Skiena, Generating graphs
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 11
Peter Steinbach, Field Guide to Simple Graphs, Volume 2, Part 12
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. 19.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Simple Graph
A. E. Yurtsun, Principles of enumeration of the number of graphs, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.

Row sums give A000088.
Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).
Row lengths: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.
Cf. also A000055.

seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # Robert Israel, Dec 22 2015

<< Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* Eric W. Weisstein, Mar 20 2013 *)
<< Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* Eric W. Weisstein, May 17 2017 *)
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_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/ g]^g,{j, 1, i-1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[ c-1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := Module[{s = 0}, Do[s += permcount[p]*edges[p, 1 + x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
Array[row, 8] // Flatten (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

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,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n, A=0) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i+A)); s/n!}
{ for(n=1, 7, print(Vecrev(G(n)))) } \\ Andrew Howroyd, Oct 22 2019, updated  Jan 09 2024

def T(n,k):
    return len(list(graphs(n, size=k)))
# Ralf Stephan, May 30 2014

O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix 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, Sep 23 2014

Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

Text belonging in a different sequence deleted by Peter Munn, Mar 20 2021

A000664 Number of graphs with n edges.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 68, 177, 497, 1476, 4613, 15216, 52944, 193367, 740226, 2960520, 12334829, 53394755, 239544624, 1111261697, 5320103252, 26237509076, 133087001869, 693339241737, 3705135967663, 20286965943329, 113694201046379, 651571521170323, 3815204365835840, 22806847476040913, 139088381010541237, 864777487052916454

Offset: 0

N. J. A. Sloane

These are simple graphs, unlabeled, with no isolated nodes, but are not necessarily connected.

			n=1: o-o (1)
n=2: o-o o-o, o-o-o (2)
n=3: o-o o-o o-o, o-o-o o-o, o-o-o-o, Y, triangle (5)
n=4: o-o o-o o-o o-o, o-o-o o-o o-o, o-o-o o-o-o, o-o o-o-o-o, o-o Y, o-o triangle,
o-o-o-o-o, >o-o-o, ><, square, triangle with tail (11)

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
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).

Max Alekseyev, Table of n, a(n) for n = 0..60
Nicolas Borie, The Hopf Algebra of graph invariants, arXiv preprint arXiv:1511.05843 [math.CO], 2015.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Fran Herr and Legrand Jones II, Iterated Jump Graphs, arXiv:2205.01796 [math.CO], 2022.
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Overview of the 11 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 1
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 2
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 3
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 4
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 6
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 7
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 8
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 9
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 11

Cf. A002905, A008406, A053418.
Row sums of A275421.
Cf. also A000088, A000055.

<< Combinatorica`; Table[NumberOfGraphs[2 n, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)
<< Combinatorica`; Table[Coefficient[GraphPolynomial[2 n, x], x, n], {n, 0, 10}] (* Eric W. Weisstein, Oct 30 2017 *)

a(n) = A008406(2*n,n). - Max Alekseyev, Sep 13 2016

Euler transform of A002905 (ignoring A002905(0)). - Franklin T. Adams-Watters Jul 03 2009

More terms from Vladeta Jovovic, Jan 08 2000, Aug 14 2007
Edited by N. J. A. Sloane, Feb 26 2008
Example for n=2 corrected by Adrian Falcone (falcone(AT)gmail.com), Jan 28 2009
Zeroth term inserted by Franklin T. Adams-Watters, Jul 03 2009
a(25)-a(26) from Max Alekseyev, Sep 19 2009
a(27)-a(60) from Max Alekseyev, Sep 07 2016

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 18, 14, 5, 1, 0, 1, 12, 35, 39, 21, 6, 1, 0, 1, 16, 62, 97, 72, 30, 7, 1, 0, 1, 20, 103, 212, 214, 120, 40, 8, 1, 0, 1, 25, 161, 429, 563, 416, 185, 52, 9, 1, 0, 1, 30, 241, 804, 1344, 1268, 732, 270, 65, 10, 1, 0

Offset: 1

Christian G. Bower, May 09 2000

Harary denotes the g.f. as P(x, y) on page 33 "... , and let P(x,y) = Sum Sum P_{nm} x^ny^m where P_{nm} is the number of planted trees with n points and m endpoints, in which again the plant has not been counted either as a point or as an endpoint." - Michael Somos, Nov 02 2014

			From _Joerg Arndt_, Aug 18 2014: (Start)
Triangle starts:
01: 1
02: 1    0
03: 1    1    0
04: 1    2    1    0
05: 1    4    3    1    0
06: 1    6    8    4    1    0
07: 1    9   18   14    5    1    0
08: 1   12   35   39   21    6    1    0
09: 1   16   62   97   72   30    7    1    0
10: 1   20  103  212  214  120   40    8    1    0
11: 1   25  161  429  563  416  185   52    9    1    0
12: 1   30  241  804 1344 1268  732  270   65   10    1    0
13: 1   36  348 1427 2958 3499 2544 1203  378   80   11    1    0
...
The trees with n=5 nodes, as (preorder-) level sequences, together with their number of leaves, and an ASCII rendering, are:
:
:     1:  [ 0 1 2 3 4 ]   1
:  O--o--o--o--o
:
:     2:  [ 0 1 2 3 3 ]   2
:  O--o--o--o
:        .--o
:
:     3:  [ 0 1 2 3 2 ]   2
:  O--o--o--o
:     .--o
:
:     4:  [ 0 1 2 3 1 ]   2
:  O--o--o--o
:  .--o
:
:     5:  [ 0 1 2 2 2 ]   3
:  O--o--o
:     .--o
:     .--o
:
:     6:  [ 0 1 2 2 1 ]   3
:  O--o--o
:     .--o
:  .--o
:
:     7:  [ 0 1 2 1 2 ]   2
:  O--o--o
:  .--o--o
:
:     8:  [ 0 1 2 1 1 ]   3
:  O--o--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 ]   4
:  O--o
:  .--o
:  .--o
:  .--o
:
This gives [1, 4, 3, 1, 0], row n=5 of the triangle.
(End)
G.f. = x*(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*x^3 + y^4) + ...).

F. Harary, Recent results on graphical enumeration, pp. 29-36 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees

Row sums give A000081.
Columns 2 through 12: A002620(n-1), A055278-A055287.
Cf. A055288, A055289, A055290.
Cf. A001190, A003238, A004111, A055327, A214575, A290689, A298422, A298426, A301342, A301343, A301344, A301345.

rut[n_]:=rut[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rut/@c]]]/@IntegerPartitions[n-1]];
Table[Length[Select[rut[n],Count[#,{},{-2}]===k&]],{n,13},{k,n}] (* Gus Wiseman, Mar 19 2018 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*(y - 1  + exp( sum(i=1, j, 1/i * subst( subst( A + x * O(x^(j\i)), x, x^i), y, y^i) ) ))); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*y + x*EULER(A(x, y)) - x. Shifts up under EULER transform.
G.f. satisfies A(x, y) = x*y - x + x * exp(Sum_{i>0} A(x^i, y^i) / i). [Harary, p. 34, equation (10)]. - Michael Somos, Nov 02 2014
Sum_k T(n, k) = A000081(n). - Michael Somos, Aug 24 2015

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

Original entry on oeis.org

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

Offset: 1

David Broadhurst

A000055(n) ~ A086308 * A051491^n * n^(-5/2), A000081(n) ~ A187770 * A051491^n * n^(-3/2). - Vaclav Kotesovec, Jan 04 2013

Analytic Combinatorics (Flajolet and Sedgewick, 2009, p. 481) has a wrong value of this constant (2.9955765856). - Vaclav Kotesovec, Jan 04 2013

			2.95576528565199497471481752412319458837549230466359659535...

S. R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.

David Broadhurst, Resurgent Integer Sequences, Rutgers Experimental Math Seminar, Feb 06 2025; Slides.
Amirmohammad Farzaneh, Mihai-Alin Badiu, and Justin P. Coon, On Random Tree Structures, Their Entropy, and Compression, arXiv:2309.09779 [cs.IT], 2023.
S. R. Finch, Otter's Tree Enumeration Constants [Broken link]
S. R. Finch, Otter's Tree Enumeration Constants [Wayback Machine]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, p. 481
Simon Plouffe, Tree-growth constant to 1800 digits
Eric Weisstein's World of Mathematics, Rooted Tree
Eric Weisstein's World of Mathematics, Tree
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A000081, A051492, A187770, A000055, A086308, A215978, A274082.

digits = 99; max = 250; s[n_, k_] := s[n, k] = a[n+1-k] + If[n < 2*k, 0, s[n-k, k]]; a[1] = 1; a[n_] := a[n] = Sum[a[k]*s[n-1, k]*k, {k, 1, n-1}]/(n-1); A[x_] := Sum[a[k]*x^k, {k, 0, max}]; eq = Log[c] == 1+Sum[A[c^-k]/k, {k, 2, max}]; alpha = c /. FindRoot[eq, {c, 3}, WorkingPrecision -> digits+5]; RealDigits[alpha, 10, digits] // First (* Jean-François Alcover, Sep 24 2014 *)

A000112 Number of partially ordered sets ("posets") with n unlabeled elements.

Original entry on oeis.org

1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087

Offset: 0

N. J. A. Sloane

Also number of fixed effects ANOVA models with n factors, which may be both crossed and nested.

			R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, page 98, Fig. 3-1 (or 2nd. ed., Fig. 3.1, p. 243) shows the unlabeled posets with <= 4 points.
From _Gus Wiseman_, Aug 14 2019: (Start)
Also the number of unlabeled T_0 topologies with n points. For example, non-isomorphic representatives of the a(4) = 16 topologies are:
  {}{1}{12}{123}{1234}
  {}{1}{2}{12}{123}{1234}
  {}{1}{12}{13}{123}{1234}
  {}{1}{12}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{1234}
  {}{1}{2}{12}{123}{124}{1234}
  {}{1}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{124}{1234}
  {}{1}{2}{12}{13}{123}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{1234}
  {}{1}{2}{12}{13}{24}{123}{124}{1234}
  {}{1}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{23}{123}{124}{1234}
  {}{1}{2}{12}{13}{14}{123}{124}{134}{1234}
  {}{1}{2}{3}{12}{13}{14}{23}{123}{124}{134}{1234}
  {}{1}{2}{3}{4}{12}{13}{14}{23}{24}{34}{123}{124}{134}{234}{1234}
(End)

G. Birkhoff, Lattice Theory, 1961, p. 4.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 60.
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date.
J. L. Davison, Asymptotic enumeration of partial orders. Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986). Congr. Numer. 53 (1986), 277--286. MR0885256 (88c:06001)
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961.
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).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, Chap. 3, pages 96ff; Vol. I, 2nd. ed., Chap. 3, pp. 241ff; Vol. 2, Problem 5.39, p. 88.
For further references concerning the enumeration of topologies and posets see under A001035.

David Wasserman, Table of n, a(n) for n = 0..16
R. Bayon, N. Lygeros, and J.-S. Sereni, New progress in enumeration of mixed models, Applied Mathematics E-Notes, 5 (2005), 60-65.
R. Bayon, N. Lygeros, and J.-S. Sereni, Nouveaux progrès dans l'énumération des modèles mixtes, in Knowledge discovery and discrete mathematics: JIM'2003, INRIA, Université de Metz, France, 2003, pp. 243-246.
Gunnar Brinkmann and Brendan D. McKay, Counting unlabeled topologies and transitive relations.
G. Brinkmann and B. D. McKay, Counting unlabeled topologies and transitive relations, J. Integer Sequences, Volume 8, 2005.
G. Brinkmann and B. D. McKay, Posets on up to 16 Points [On Brendan McKay's home page]
G. Brinkmann and B. D. McKay, Posets on up to 16 Points, Order 19 (2) (2002) 147-179.
Kim Ki-Hang Butler, The number of partially ordered sets, Journal of Combinatorial Theory, Series B 13.3 (1972): 276-289.
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184
K. K.-H. Butler and G. Markowsky, Enumeration of finite topologies, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 169-184. [Annotated scan of pages 180 and 183 only]
Kim Ki-Hang Butler and Gaoacs Markowsky. The number of partially ordered sets. II., J. Korean Math. Soc 11 (1974): 7-17.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
C. Chaunier, Letter to N. J. A. Sloane, Jun 22 1993, with several attachments
C. Chaunier and N. Lygeros, The Number of Orders with Thirteen Elements, Order 9:3 (1992) 203-204. [See Chaunier letter]
C. Chaunier and N. Lygeros, Le nombre de posets à isomorphie près ayant 12 éléments Theoretical Computer Science, 123 p. 89-94, 1994.
C. Chaunier and N. Lygeros, Progrès dans l'énumération des posets, C. R. Acad. Sci. Paris 314 série I (1992) 691-694. [See Chaunier letter]
E. D. Cooper, Representation and generation of finite partially ordered sets, Manuscript, no date [Annotated scanned copy]
Gábor Czédli, Minimum-sized generating sets of the direct powers of free distributive lattices, arXiv:2309.13783 [math.CO], 2023. See p. 14. See also CUBO, A Mathematical Journal, Vol. 26, no. 2, pp. 217-237, August 2024.
M. Erné and K. Stege, The number of partially ordered (labeled) sets, Preprint, 1989. (Annotated scanned copy)
Uli Fahrenberg, Christian Johansen, Georg Struth, and Ratan Bahadur Thapa, Generating Posets Beyond N, arXiv:1910.06162 [cs.FL], 2019.
S. R. Finch, Transitive relations, topologies and partial orders, June 5, 2003. [Cached copy, with permission of the author]
FindStat - Combinatorial Statistic Finder, Posets
R. Fraisse and N. Lygeros, Petits posets: dénombrement, représentabilité par cercles et compenseurs C. R. Acad. Sci. Paris, 313, I, 417-420, 1991.
E. N. Gilbert, A catalog of partially ordered systems, unpublished memorandum, Aug 08, 1961. [Annotated scanned copy]
G. Grekos, Letter to N. J. A. Sloane, Oct 31 1994, with attachments
M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
Ann Marie Hess, Mixed Models Site
C. Joslyn, E. Hogan, and A. Pogel, Conjugacy and Iteration of Standard Interval Rank in Finite Ordered Sets, arXiv preprint arXiv:1409.6684 [math.CO], 2014.
Dongseok Kim, Young Soo Kwon, and Jaeun Lee, Enumerations of finite topologies associated with a finite graph, arXiv preprint arXiv:1206.0550 [math.CO], 2012.
D. J. Kleitman and B. L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205 (1975) 205-220.
N. Lygeros, Calculs exhaustifs sur les posets d'au plus 7 éléments, SINGULARITE, vol. 2 n4 p. 10-24, avril 1991.
N. Lygeros and P. Zimmermann, Computation of P(14), the number of posets with 14 elements: 1.338.193.159.771
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Bob Proctor, Chapel Hill Poset Atlas
D. Rusin, Further information and references [Broken link]
D. Rusin, Further information and references [Cached copy]
Henry Sharp, Jr., Quasi-orderings and topologies on finite sets, Proceedings of the American Mathematical Society 17.6 (1966): 1344-1349. [Annotated scanned copy]
N. J. A. Sloane, List of sequences related to partial orders, circa 1972
N. J. A. Sloane, Classic Sequences
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Szilárd Szalay, The classification of multipartite quantum correlation, arXiv:1806.04392 [quant-ph], 2018.
N. L. White, Two letters to N. J. A. Sloane, 1970, with hand-drawn enclosure
J. A. Wright, There are 718 6-point topologies, quasiorderings and transgraphs, Preprint, 1970 [Annotated scanned copy]
J. A. Wright, Two related abstracts, 1970 and 1972 [Annotated scanned copies]
J. A. Wright, Letter to N. J. A. Sloane, Apr 06 1972, listing 18 sequences
Stav Zalel, Covariant Growth Dynamics, arXiv:2302.10582 [gr-qc], 2023.
Index entries for sequences related to posets
Index entries for "core" sequences

Cf. A000798 (labeled topologies), A001035 (labeled posets), A001930 (unlabeled topologies), A006057.
Cf. A079263, A079265, A065066 (refined by maximal elements), A342447 (refined by number of arcs).
Row sums of A263859. Euler transform of A000608.
Cf. A316978, A319559, A326939, A326943, A326944, A326947.

a(15)-a(16) are from Brinkmann's and McKay's paper. - Vladeta Jovovic, Jan 04 2006

A005195 Number of forests with n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 37, 76, 153, 329, 710, 1601, 3658, 8599, 20514, 49905, 122963, 307199, 775529, 1977878, 5086638, 13184156, 34402932, 90328674, 238474986, 632775648, 1686705630, 4514955632, 12132227370, 32717113805, 88519867048, 240235675303

Offset: 0

N. J. A. Sloane

Same as "Number of forests with n nodes that are perfect graphs" [see Hougardy]. - N. J. A. Sloane, Dec 04 2015

Number of unlabeled acyclic graphs on n vertices. The labeled version is A001858. The covering case is A144958, connected A000055. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of non-isomorphic representatives of the a(0) = 1 through a(5) = 10 forests:
  {}  {}  {}    {}       {}          {}
          {12}  {12}     {12}        {12}
                {13,23}  {12,34}     {12,34}
                         {13,23}     {13,23}
                         {13,24,34}  {12,35,45}
                         {14,24,34}  {13,24,34}
                                     {14,24,34}
                                     {13,24,35,45}
                                     {14,25,35,45}
                                     {15,25,35,45}
(End)

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
E. M. Palmer and A. J. Schwenk, On the number of trees in a random forest, J. Combin. Theory, B 27 (1979), 109-121.
N. J. A. Sloane, Transforms
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 5 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Forest.
Index entries for sequences related to forests

Cf. A095133 (by number of trees), A136605 (by number of edges).
A diagonal of A144215.
The connected case is A000055.
The labeled version is A001858.
The covering case is A144958, labeled A105784.
For triangles instead of cycles we have A006785, covering A372169.
Unique cycle: A236570 (labeled A372193), covering A372191 (labeled A372195).
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A000272, A002807, A054548, A137917, A367863, A372176.

EulerTransform[ seq_List ] := With[{m = Length[seq]}, CoefficientList[ Series[ Times @@ (1/(1 - x^Range[m])^seq), {x, 0, m}], x]];
b[n_] := b[n] = If[n <= 1, n, Sum[ Sum[ d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}]/(n - 1)];
a55[n_] := a55[n] = If[n == 0, 1, b[n] - (Sum[ b[k]*b[n - k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; A000055 = Table[ a55[n], {n, 1, 31}]; EulerTransform[ A000055 ] (* Jean-François Alcover, Mar 15 2012 *)

Euler transform of A000055: Product_{n>0} (1-x^n)^(-A000055(n)). a(n) = 1/n*Sum_{k=1..n} b(k)*a(n-k), where b(k) = Sum_{d divides k} d*A000055(d). - Vladeta Jovovic, Sep 05 2002
G.f.: exp(sum_{k>0} B(x^k)/k ), 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.
a(n) ~ c * d^n / n^(5/2), where d = A051491 = 2.9557652856519949747148..., c = 1.023158422... . - Vaclav Kotesovec, Nov 16 2014
First differences are A144958. - Gus Wiseman, Apr 29 2024

More terms from Vladeta Jovovic, Sep 05 2002

A003216 Number of Hamiltonian graphs with n nodes.

Original entry on oeis.org

1, 0, 1, 3, 8, 48, 383, 6196, 177083, 9305118, 883156024, 152522187830, 48322518340547

Offset: 1

N. J. A. Sloane

a(1) could also be taken to be 0, but I prefer a(1) = 1. - N. J. A. Sloane, Oct 15 2006

J. P. Dolch, Names of Hamiltonian graphs, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 259-271.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 219.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

John Asplund, N. Bradley Fox, and Arran Hamm, New Perspectives on Neighborhood-Prime Labelings of Graphs, arXiv:1804.02473 [math.CO], 2018.
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)
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, preprint, 2015.
Scott Garrabrant and Igor Pak, Pattern Avoidance is Not P-Recursive, arXiv:1505.06508 [math.CO], 2015.
Jan Goedgebeur, Barbara Meersman, and Carol T. Zamfirescu, Graphs with few Hamiltonian Cycles, arXiv:1812.05650 [math.CO], 2018-2019.
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Hamiltonian Graph
Wikipedia, Hamiltonian path
Gus Wiseman, Non-isomorphic representatives of the a(5) = 8 simple graphs containing a Hamiltonian cycle.

Main diagonal of A325455 and of A325447 (for n>=3).
The labeled case is A326208.
The directed case is A326226 (with loops) or A326225 (without loops).
The case without loops is A326215.
Unlabeled simple graphs not containing a Hamiltonian cycle are A246446.
Unlabeled simple graphs containing a Hamiltonian path are A057864.
Cf. A000088, A006125, A283420.

A000088(n) = a(n) + A246446(n). - Gus Wiseman, Jun 17 2019

Extended to n=11 by Brendan McKay, Jul 15 1996
a(12) from Sean A. Irvine, Mar 17 2015
a(13) from A246446 added by Jan Goedgebeur, Sep 07 2019

A034781 Triangle of number of rooted trees with n >= 2 nodes and height h >= 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 18, 13, 5, 1, 1, 14, 38, 36, 19, 6, 1, 1, 21, 76, 93, 61, 26, 7, 1, 1, 29, 147, 225, 180, 94, 34, 8, 1, 1, 41, 277, 528, 498, 308, 136, 43, 9, 1, 1, 55, 509, 1198, 1323, 941, 487, 188, 53, 10, 1

Offset: 2

N. J. A. Sloane

			Triangle begins:
  1;
  1  1;
  1  2  1;
  1  4  3  1;
  1  6  8  4  1;
  1 10 18 13  5  1;
  1 14 38 36 19  6 1;
thus there are 10 trees with 7 nodes and height 2.

Alois P. Heinz, Rows n = 2..142, flattened
Marko Riedel, Counting the number of rooted trees of a certain height
Marko Riedel, Maple code for sequence (OGF)
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 10 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Columns h=2-10 give: A000065, A000235, A000299, A000342, A000393, A000418, A000429, A126085, A245068.
T(2n,n) = A245102(n), T(2n+1,n) = A245103(n).
Row sums give A000081.
Cf. A001853, A227819, A375467.

b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1 or k<1, 0,
     add(binomial(b((i-1)$2, k-1)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
T:= (n, k)-> b((n-1)$2, k) -b((n-1)$2, k-1):
seq(seq(T(n, k), k=1..n-1), n=2..16);  # Alois P. Heinz, Jul 31 2013

Drop[Map[Select[#, # > 0 &] &,
   Transpose[
    Prepend[Table[
      f[n_] :=
       Nest[CoefficientList[
          Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x,
            0, 10}], x] &, {1}, n]; f[m] - f[m - 1], {m, 2, 10}],
Prepend[Table[1, {10}], 0]]]], 1] // Grid (* Geoffrey Critzer, Aug 01 2013 *)
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i<1 || k<1, 0, Sum[Binomial[b[i-1, i-1, k-1]+j-1, j]*b[n-i*j, i-1, k], {j, 0, n/i}]]]; T[n_, k_] := b[n-1, n-1, k]-b[n-1, n-1, k-1]; Table[T[n, k], {n, 2, 16}, {k, 1, n-1}] // Flatten (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

def A034781(n, k): return A375467(n, k) - A375467(n, k - 1)
for n in range(2, 10): print([A034781(n, k) for k in range(2, n + 1)])
# Peter Luschny, Aug 30 2024

Reference gives recurrence.

T(n, k) = A375467(n, k) - A375467(n, k - 1). - Peter Luschny, Aug 30 2024

More terms from Victoria A Sapko (vsapko(AT)canes.gsw.edu), Sep 19 2003

cp's OEIS Frontend

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A000798 Number of different quasi-orders (or topologies, or transitive digraphs) with n labeled elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A008406 Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A000664 Number of graphs with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055277 Triangle T(n,k) of number of rooted trees with n nodes and k leaves, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A051491 Decimal expansion of Otter's rooted tree constant: lim_{n->inf} A000081(n+1)/A000081(n).

Views

Author

Keywords

Comments

Examples

References

Links