A133686 -id:A133686 - cp's OEIS frontend

A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.

1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721, 1439428141044398334941790719839535103, 237725265553410354992180218286376719253505

Offset: 0

N. J. A. Sloane

Also the number of n X n real (0,1)-matrices with all eigenvalues positive. - Conjectured by Eric W. Weisstein, Jul 10 2003 and proved by McKay et al. 2003, 2004
Also the number of n X n real (0,1)-matrices with permanent equal to 1, up to permutation of rows/columns, cf. A089482. - Vladeta Jovovic, Oct 28 2009
Also the number of nilpotent elements in the semigroup of binary relations on [n]. - Geoffrey Critzer, May 26 2022
From Gus Wiseman, Jan 01 2024: (Start)
Also the number of sets of n nonempty subsets of {1..n} such that there is a unique way to choose a different element from each. For example, non-isomorphic representatives of the a(3) = 25 set-systems are:
  {{1},{2},{3}}
  {{1},{2},{1,3}}
  {{1},{2},{1,2,3}}
  {{1},{1,2},{1,3}}
  {{1},{1,2},{2,3}}
  {{1},{1,2},{1,2,3}}
These set-systems have ranks A367908, subset of A367906, for multisets A368101.
The version for no ways is A368600, any length A367903, ranks A367907.
The version for at least one way is A368601, any length A367902.
(End)

			For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.

Alois P. Heinz, Table of n, a(n) for n = 0..77 (first 41 terms from T. D. Noe)
T. E. Allen, J. Goldsmith, and N. Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
Eunice Y.-J. Chen, A. Choi, and A. Darwiche, On Pruning with the MDL Score, JMLR: Workshop and Conference Proceedings vol 52, 98-109, 2016.
S. Engstrom, Random acyclic orientations of graphs, Master's thesis written at the department of Mathematics at the Royal Institute of Technology (KTH) in Stockholm, Jan. 2013.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, Xi Kang, Andrea Valerio Maccio, and Yashar Hezaveh, A Data-driven Discovery of the Causal Connection between Galaxy and Black Hole Evolution, arXiv:2410.00965 [astro-ph.GA], 2024. See p. 33.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Andrea V. Macciò, and Yashar Hezaveh, Beyond Causal Discovery for Astronomy: Learning Meaningful Representations with Independent Component Analysis, arXiv:2410.14775 [astro-ph.GA], 2024. See pp. 2, 4, 10.
Zehao Jin, Mario Pasquato, Benjamin L. Davis, Tristan Deleu, Yu Luo, Changhyun Cho, Pablo Lemos, Laurence Perreault-Levasseur, Yoshua Bengio, and Xi Kang, Causal Discovery in Astrophysics: Unraveling Supermassive Black Hole and Galaxy Coevolution, Astrophys. J. (2025) Vol. 979, 212. See 4.1.
P. L. Krapivsky, Hiring Strategies, arXiv:2412.10490 [cs.GT], 2024. See p. 12.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - _N. J. A. Sloane_, Sep 14 2012
Laphou Lao, Zecheng Li, Songlin Hou, Bin Xiao, Songtao Guo, and Yuanyuan Yang, A Survey of IoT Applications in Blockchain Systems: Architecture, Consensus and Traffic Modeling, ACM Computing Surveys (CSUR, 2020) Vol. 53, No. 1, Article No. 18.
Tobias Ellegaard Larsen, Claus Thorn Ekstrøm, and Anne Helby Petersen, Score-Based Causal Discovery with Temporal Background Information, arXiv:2502.06232 [stat.ME], 2025. See p. 9.
Daniel Mallia, Towards an Unsupervised Bayesian Network Pipeline for Explainable Prediction, Decision Making and Discovery, Master's Thesis, CUNY Hunter College (2023).
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], Oct 28 2003.
A. Motzek and R. Möller, Exploiting Innocuousness in Bayesian Networks, Preprint 2015.
Yisu Peng, Y. Jiang, and P. Radivojac, Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies, arXiv preprint arXiv:1712.09679 [cs.DS], 2017.
J. Peters, J. Mooij, D. Janzing, and B. Schölkopf, Causal Discovery with Continuous Additive Noise Models, arXiv preprint arXiv:1309.6779 [stat.ML], 2013.
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
V. I. Rodionov, On the number of labeled acyclic digraphs, Disc. Math. 105 (1-3) (1992) 319-321
I. Shpitser, T. S. Richardson, J. M. Robins and R. Evans, Parameter and Structure Learning in Nested Markov Models, arXiv preprint arXiv:1207.5058 [stat.ML], 2012.
I. Shpitser, R. J. Evans, T. S. Richardson, and J. M. Robins, Introduction to nested Markov models, Behaviormetrika, Behaviormetrika Vol. 41, No. 1, 2014, 3-39.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Christian Toth, Christian Knoll, Franz Pernkopf, and Robert Peharz, Rao-Blackwellising Bayesian Causal Inference, arXiv:2402.14781 [cs.LG], 2024.
Sumanth Varambally, Yi-An Ma, and Rose Yu, Discovering Mixtures of Structural Causal Models from Time Series Data, arXiv:2310.06312 [cs.LG], 2023.
S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
Daniel Waxman, Kurt Butler, and Petar M. Djuric, Dagma-DCE: Interpretable, Non-Parametric Differentiable Causal Discovery, arXiv:2401.02930 [cs.LG], 2024.
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Acyclic Digraph
Eric Weisstein's World of Mathematics, Positive Eigenvalued Matrix
Eric Weisstein's World of Mathematics, Weisstein's Conjecture
Jun Wu and Mathias Drton, Partial Homoscedasticity in Causal Discovery with Linear Models, arXiv:2308.08959 [math.ST], 2023.
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
Index entries for sequences related to binary matrices

Cf. A086510, A081064 (refined by # arcs), A307049 (by # descents).
Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
Cf. A188457, A135079, A137435 (acyclic 3-multidigraphs), A188490.
For a unique sink we have A003025.
The unlabeled version is A003087.
These are the reverse-alternating sums of rows of A046860.
The weakly connected case is A082402.
A reciprocal version is A334282.
Row sums of A361718.
Cf. A003465, A058877, A058891, A059201, A088957, A133686, A323818.

p:=evalf(solve(sum((-1)^n*x^n/(n!*2^(n*(n-1)/2)), n=0..infinity) = 0, x), 50); M:=evalf(sum((-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)), n=1..infinity), 40); # program for evaluation of constants p and M in the asymptotic formula, Vaclav Kotesovec, Dec 09 2013

a[0] = a[1] = 1; a[n_] := a[n] = Sum[ -(-1)^k * Binomial[n, k] * 2^(k*(n-k)) * a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 13}](* Jean-François Alcover, May 21 2012, after PARI *)
Table[2^(n*(n-1)/2)*n! * SeriesCoefficient[1/Sum[(-1)^k*x^k/k!/2^(k*(k-1)/2),{k,0,n}],{x,0,n}],{n,0,20}] (* Vaclav Kotesovec, May 19 2015 *)
Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,5}] (* Gus Wiseman, Jan 01 2024 *)

a(n)=if(n<1,n==0,sum(k=1,n,-(-1)^k*binomial(n,k)*2^(k*(n-k))*a(n-k)))

{a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Oct 17 2009

a(0) = 1; for n > 0, a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*2^(k*(n-k))*a(n-k).
1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - Vladeta Jovovic, Jun 05 2005
a(n) = Sum_{k=1..n} (-1)^(n-k)*A046860(n,k) = Sum_{k=1..n} (-1)^(n-k)*k!*A058843(n,k). - Vladeta Jovovic, Jun 20 2008
1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - Paul D. Hanna, Oct 17 2009
1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 2^n*x)^(n+m) for m>=1. - Paul D. Hanna, Apr 01 2011
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - Paul D. Hanna, Apr 01 2011
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/E(-x) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + x + 3*x^2/(2!*2) + 25*x^3/(3!*2^3) + 543*x^4/(4!*2^6) + ... (Stanley). Cf. A188457. - Peter Bala, Apr 01 2013
a(n) ~ n!*2^(n*(n-1)/2)/(M*p^n), where p = 1.488078545599710294656246... is the root of the equation Sum_{n>=0} (-1)^n*p^n/(n!*2^(n*(n-1)/2)) = 0, and M = Sum_{n>=1} (-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)) = 0.57436237330931147691667... Both references to the article "Acyclic digraphs and eigenvalues of (0,1)-matrices" give the wrong value M=0.474! - Vaclav Kotesovec, Dec 09 2013 [Response from N. J. A. Sloane, Dec 11 2013: The value 0.474 has a typo, it should have been 0.574. The value was taken from Stanley's 1973 paper.]
exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 + ... appears to have integer coefficients (cf. A188490). - Peter Bala, Jan 14 2016

A057500 Number of connected labeled graphs with n edges and n nodes.

Original entry on oeis.org

0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, 25201854045, 787368574080, 26667815195274, 973672928417280, 38132879409281475, 1594927540549217280, 70964911709203684440, 3347306760024413356032, 166855112441313024389625, 8765006377126199463936000

Offset: 1

Qing-Hu Hou and David C. Torney (dct(AT)lanl.gov), Sep 01 2000

Equivalently, number of connected unicyclic (i.e., containing one cycle) graphs on n labeled nodes. - Vladeta Jovovic, Oct 26 2004

a(n) is the number of trees on vertex set [n] = {1,2,...,n} rooted at 1 with one marked inversion (an inversion is a pair (i,j) with i > j and j a descendant of i in the tree). Here is a bijection from the title graphs (on [n]) to these marked trees. A title graph has exactly one cycle. There is a unique path from vertex 1 to this cycle, first meeting it at k, say (k may equal 1). Let i and j be the two neighbors of k in the cycle, with i the larger of the two. Delete the edge k<->j thereby forming a tree (in which j is a descendant of i) and take (i,j) as the marked inversion. To reverse this map, create a cycle by joining the smaller element of the marked inversion to the parent of the larger element. a(n) = binomial(n-1,2)*A129137(n). This is because, on the above marked trees, the marked inversion is uniformly distributed over 2-element subsets of {2,3,...,n} and so a(n)/binomial(n-1,2) is the number of trees on [n] (rooted at 1) for which (3,2) is an inversion. - David Callan, Mar 30 2007

			E.g., a(4)=15 because there are three different (labeled) 4-cycles and 12 different labeled graphs with a 3-cycle and an attached, external vertex.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.
C. L. Mallows, Letter to N. J. A. Sloane, 1980.
R. J. Riddell, Contributions to the theory of condensation, Dissertation, Univ. of Michigan, Ann Arbor, 1951.

Alois P. Heinz, Table of n, a(n) for n = 1..300 (terms n = 1..50 from Washington G. Bomfim)
Federico Ardila, Matthias Beck, Jodi McWhirter, The Arithmetic of Coxeter Permutahedra, arXiv:2004.02952 [math.CO], 2020.
Steven R. Finch, An exceptional convolutional recurrence, arXiv:2408.12440 [math.CO], 22 Aug 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 133.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, arXiv:math/9310236 [math.PR], 1993.
S. Janson, D. E. Knuth, T. Łuczak and B. Pittel, The Birth of the Giant Component, Random Structures and Algorithms Vol. 4 (1993), 233-358.
Younng-Jin Kim and Woong Kook, Winding number and Cutting number of Harmonic cycle, arXiv:1812.04930 [math.CO], 2018.
C. L. Mallows, Letter to N. J. A. Sloane, 1980
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Proof of closed form by Cauchy Coefficient Formula / Lagrange Inversion.)
Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.

A diagonal of A343088.
Cf. A000272 = labeled trees on n nodes; connected labeled graphs with n nodes and n+k edges for k=0..8: this sequence, A061540, A061541, A061542, A061543, A096117, A061544, A096150, A096224.
Cf. A001429 (unlabeled case), A052121.
For any number of edges we have A001187, unlabeled A001349.
This is the connected and covering case of A116508.
For #edges <= #nodes we have A129271, covering A367869.
For #edges > #nodes we have A140638, covering A367868.
This is the connected case of A367862 and A367863, unlabeled A006649.
The version with loops is A368951, unlabeled A368983.
This is the covering case of A370317.
Counting only covering vertices gives A370318.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
Cf. A062734, A098909, A123527, A129137, A133686, A143543, A323818, A367916, A367917, A369191, A369197.

egf:= -1/2*ln(1+LambertW(-x)) +1/2*LambertW(-x) -1/4*LambertW(-x)^2:
a:= n-> n!*coeff(series(egf, x, n+3), x, n):
seq(a(n), n=1..25);  # Alois P. Heinz, Mar 27 2013

nn=20; t=Sum[n^(n-1) x^n/n!, {n,1,nn}]; Drop[Range[0,nn]! CoefficientList[Series[Log[1/(1-t)]/2-t^2/4-t/2, {x,0,nn}], x], 1]  (* Geoffrey Critzer, Oct 07 2012 *)
a[n_] := (n-1)!*n^n/2*Sum[1/(n^k*(n-k)!), {k, 3, n}]; Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jan 15 2014, after Vladeta Jovovic *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[#]==n&&Length[csm[#]]<=1&]],{n,0,5}] (* Gus Wiseman, Feb 19 2024 *)

# Warning: Floating point calculation. Adjust precision as needed!
from mpmath import mp, chop, gammainc
mp.dps = 200; mp.pretty = True
for n in (1..100):
    print(chop((n^(n-2)*(1-3*n)+exp(n)*gammainc(n+1, n)/n)/2))
# Peter Luschny, Jan 27 2016

The number of labeled connected graphs with n nodes and m edges is Sum_{k=1..n} (-1)^(k+1)/k*Sum_{n_1+n_2+..n_k=n, n_i>0} n!/(Product_{i=1..k} (n_i)!)* binomial(s, m), s=Sum_{i..k} binomial(n_i, 2). - Vladeta Jovovic, Apr 10 2001
E.g.f.: (1/2) Sum_{k>=3} T(x)^k/k, with T(x) = Sum_{n>=1} n^(n-1)/n! x^n. R. J. Riddell's thesis contains a closed-form expression for the number of connected graphs with m nodes and n edges. The present series applies to the special case m=n.
E.g.f.: -1/2*log(1+LambertW(-x))+1/2*LambertW(-x)-1/4*LambertW(-x)^2. - Vladeta Jovovic, Jul 09 2001
Asymptotic expansion (with xi=sqrt(2*Pi)): n^(n-1/2)*[xi/4-7/6*n^(-1/2)+xi/48* n^(-1)+131/270*n^(-3/2)+xi/1152*n^(-2)+4/2835*n^(-5/2)+O(n^(-3))]. - Keith Briggs, Aug 16 2004
Row sums of A098909: a(n) = (n-1)!*n^n/2*Sum_{k=3..n} 1/(n^k*(n-k)!). - Vladeta Jovovic, Oct 26 2004
a(n) = Sum_{k=0..C(n-1,2)} k*A052121(n,k). - Alois P. Heinz, Nov 29 2015
a(n) = (n^(n-2)*(1-3*n)+exp(n)*Gamma(n+1,n)/n)/2. - Peter Luschny, Jan 27 2016
a(n) = A062734(n,n+1) = A123527(n,n). - Gus Wiseman, Feb 19 2024

More terms from Vladeta Jovovic, Jul 09 2001

A367902 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice.

Original entry on oeis.org

1, 2, 7, 61, 1771, 187223, 70038280, 90111497503, 397783376192189

Offset: 0

Gus Wiseman, Dec 05 2023

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

			The a(2) = 7 set-systems:
  {}
  {{1}}
  {{2}}
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}

Wikipedia, Axiom of choice.

The version for simple graphs is A133686, covering A367869.
The version without singletons is A367770.
The complement allowing empty edges is A367901.
The complement is A367903, without singletons A367769, ranks A367907.
For a unique choice we have A367904, ranks A367908.
These set-systems have ranks A367906.
A000372 counts antichains, covering A006126, nonempty A014466.
A003465 counts covering set-systems, unlabeled A055621.
A058891 counts set-systems, unlabeled A000612.
A059201 counts covering T_0 set-systems.
A323818 counts covering connected set-systems.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367862, A367905, A370636.

Table[Length[Select[Subsets[Subsets[Range[n]]], Select[Tuples[#],UnsameQ@@#&]!={}&]],{n,0,3}]

a(n) = A370636(2^n-1). - Alois P. Heinz, Mar 09 2024

a(6)-a(8) from Christian Sievers, Jul 25 2024

A367867 Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 0, 0, 7, 416, 24244, 1951352, 265517333, 68652859502, 35182667175398, 36028748718835272, 73786974794973865449, 302231454853009287213496, 2475880078568912926825399800, 40564819207303268441662426947840, 1329227995784915869870199216532048487

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

In the connected case, these are just graphs with more than one cycle.

			Non-isomorphic representatives of the a(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..50

The complement is A133686, connected A129271, covering A367869.
The connected case is A140638 (graphs with more than one cycle).
The covering case is A367868.
For set-systems we have A367903, ranks A367907.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A326754, A355739, A355740, A367769, A367770, A367863, A367901, A367902, A367904.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Select[Tuples[#],UnsameQ@@#&]=={}&]],{n,0,5}]

a(n) = A006125(n) - A133686(n). - Andrew Howroyd, Dec 30 2023

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023

A116508 a(n) = C( C(n,2), n).

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 5005, 116280, 3108105, 94143280, 3190187286, 119653565850, 4922879481520, 220495674290430, 10682005290753420, 556608279578340080, 31044058215401404845, 1845382436487682488000, 116475817125419611477660, 7779819801401934344268210

Offset: 0

Christopher Hanusa (chanusa(AT)math.binghamton.edu), Mar 21 2006

a(n) is the number of simple labeled graphs with n nodes and n edges. - Geoffrey Critzer, Nov 02 2014

These graphs are not necessarily covering, but the covering case is A367863, unlabeled A006649, and the unlabeled version is A001434. - Gus Wiseman, Dec 22 2023

			a(5) = C(C(5,2),5) = C(10,5) = 252.

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

Main diagonal of A084546.
The unlabeled version is A001434, covering case A006649.
The connected case is A057500, unlabeled A001429.
For set-systems we have A136556, covering case A054780.
The covering case is A367863.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A133686 counts graphs satisfying a strict AOC, connected A129271.
A367867 counts graphs contradicting a strict AOC, connected A140638.
Cf. A001187, A003465, A143543, A305000, A367916, A367917.

[0] cat [(Binomial(Binomial(n+2, n), n+2)): n in [0..20]]; // Vincenzo Librandi, Nov 03 2014

a:= n-> binomial(binomial(n, 2), n):
seq(a(n), n=0..20);

nn = 18; f[x_, y_] :=
Sum[(1 + y)^Binomial[n, 2] x^n/n!, {n, 1, nn}]; Table[
n! Coefficient[Series[f[x, y], {x, 0, nn}], x^n y^n], {n, 1, nn}] (* Geoffrey Critzer, Nov 02 2014 *)
Table[Length[Subsets[Subsets[Range[n],{2}],{n}]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)
Table[SeriesCoefficient[(1 + x)^(n*(n-1)/2), {x, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, Aug 06 2025 *)

from math import comb
def A116508(n): return comb(n*(n-1)>>1,n) # Chai Wah Wu, Jul 02 2024

[(binomial(binomial(n+2,n),n+2)) for n in range(-1, 17)] # Zerinvary Lajos, Nov 30 2009

a(n) ~ exp(n - 2) * n^(n - 1/2) / (sqrt(Pi) * 2^(n + 1/2)). - Vaclav Kotesovec, May 19 2020

a(n) = [x^n] (1+x)^(n*(n-1)/2). - Vaclav Kotesovec, Aug 06 2025

a(0)=1 prepended by Alois P. Heinz, Feb 02 2024

A367863 Number of n-vertex labeled simple graphs with n edges and no isolated vertices.

Original entry on oeis.org

1, 0, 0, 1, 15, 222, 3760, 73755, 1657845, 42143500, 1197163134, 37613828070, 1295741321875, 48577055308320, 1969293264235635, 85852853154670693, 4005625283891276535, 199166987259400191480, 10513996906985414443720, 587316057411626070658200, 34612299496604684775762261

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

			Non-isomorphic representatives of the a(4) = 15 graphs:
  {{1,2},{1,3},{1,4},{2,3}}
  {{1,2},{1,3},{2,4},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

The connected case is A057500, unlabeled A001429.
The unlabeled version is A006649.
The non-covering version is A116508.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A133686 = graphs satisfy strict AoC, connected A129271, covering A367869.
A143543 counts simple labeled graphs by number of connected components.
A323818 counts connected set-systems, unlabeled A323819, ranks A326749.
A367867 = graphs contradict strict AoC, connected A140638, covering A367868.
Cf. A003465, A006126, A305000, A316983, A319559, A323817, A326754, A367769, A367901, A367902, A367903.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Length[#]==n&]],{n,0,5}]

a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n)) \\ Andrew Howroyd, Dec 29 2023

Binomial transform is A367862.

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n). - Andrew Howroyd, Dec 29 2023

Terms a(8) and beyond from Andrew Howroyd, Dec 29 2023

A129271 Number of labeled n-node connected graphs with at most one cycle.

Original entry on oeis.org

1, 1, 1, 4, 31, 347, 4956, 85102, 1698712, 38562309, 980107840, 27559801736, 849285938304, 28459975589311, 1030366840792576, 40079074477640850, 1666985134587145216, 73827334760713500233, 3468746291121007607808, 172335499299097826575564, 9027150377126199463936000

Offset: 0

Washington Bomfim, May 10 2008

The majority of those graphs of order 4 are trees since we have 16 trees and only 9 unicycles. See example.

Also connected graphs covering n vertices with at most n edges. The unlabeled version is A005703. - Gus Wiseman, Feb 19 2024

			a(4) = 16 + 3*3 = 31.
From _Gus Wiseman_, Feb 19 2024: (Start)
The a(0) = 1 through a(3) = 4 graph edge sets:
  {}  .  {{1,2}}  {{1,2},{1,3}}
                  {{1,2},{2,3}}
                  {{1,3},{2,3}}
                  {{1,2},{1,3},{2,3}}
(End)

J. Riordan, An Introduction to Combinatorial Analysis, Dover, 2002, p. 2.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Wikipedia, PseudoForest.

Cf. A129137, A000272.
For any number of edges we have A001187, unlabeled A001349.
The unlabeled version is A005703.
The case of equality is A057500, covering A370317, cf. A370318.
The non-connected non-covering version is A133686.
The connected complement is A140638, unlabeled A140636, covering A367868.
The non-connected covering version is A367869 or A369191.
The version with loops is A369197, non-connected A369194.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A062734 counts connected graphs by number of edges.
Cf. A006649, A116508, A134964, A143543, A323818, A367862, A367863, A367867, A367916, A367917, A368951.

a := n -> `if`(n=0,1,((n-1)*exp(n)*GAMMA(n-1,n)+n^(n-2)*(3-n))/2):
seq(simplify(a(n)),n=0..16); # Peter Luschny, Jan 18 2016

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[Series[ Log[1/(1-t)]/2+t/2-3t^2/4+1,{x,0,nn}],x]  (* Geoffrey Critzer, Mar 23 2013 *)

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(log(1/(1-t))/2 + t/2 - 3*t^2/4 + 1))} \\ Andrew Howroyd, Nov 07 2019

a(0) = 1, for n >=1, a(n) = A000272(n) + A057500(n) = n^{n-2} + (n-1)(n-2)/2Sum_{r=1..n-2}( (n-3)!/(n-2-r)! )n^(n-2-r)
E.g.f.: log(1/(1-T(x)))/2 + T(x)/2 - 3*T(x)^2/4 + 1, where T(x) is the e.g.f. for A000169. - Geoffrey Critzer, Mar 23 2013
a(n) = ((n-1)*e^n*GAMMA(n-1,n)+n^(n-2)*(3-n))/2 for n>=1. - Peter Luschny, Jan 18 2016

Terms a(17) and beyond from Andrew Howroyd, Nov 07 2019

A054548 Triangular array giving number of labeled graphs on n unisolated nodes and k=0...n*(n-1)/2 edges.

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 3, 16, 15, 6, 1, 0, 0, 0, 30, 135, 222, 205, 120, 45, 10, 1, 0, 0, 0, 15, 330, 1581, 3760, 5715, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 0, 0, 0, 0, 315, 4410, 23604, 73755, 159390, 259105, 331716, 343161, 290745, 202755, 116175

Offset: 0

Vladeta Jovovic, Apr 09 2000

			From _Gus Wiseman_, Feb 14 2024: (Start)
Triangle begins:
   1
   0
   0   1
   0   0   3   1
   0   0   3  16  15   6   1
   0   0   0  30 135 222 205 120  45  10   1
Row n = 4 counts the following graphs:
  .  .  12-34  12-13-14  12-13-14-23  12-13-14-23-24  12-13-14-23-24-34
        13-24  12-13-24  12-13-14-24  12-13-14-23-34
        14-23  12-13-34  12-13-14-34  12-13-14-24-34
               12-14-23  12-13-23-24  12-13-23-24-34
               12-14-34  12-13-23-34  12-14-23-24-34
               12-23-24  12-13-24-34  13-14-23-24-34
               12-23-34  12-14-23-24
               12-24-34  12-14-23-34
               13-14-23  12-14-24-34
               13-14-24  12-23-24-34
               13-23-24  13-14-23-24
               13-23-34  13-14-23-34
               13-24-34  13-14-24-34
               14-23-24  13-23-24-34
               14-23-34  14-23-24-34
               14-24-34
(End)

F. Harary and E. Palmer, Graphical Enumeration, Academic Press, 1973, Page 29, Exercise 1.4.

Michael De Vlieger, Table of n, a(n) for n = 0..10700
A. N. Bhavale and B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.
Ashok Nivrutti Bhavale, Equivalence of labeled graphs and lattices, arXiv:2501.05064 [math.CO], 2025. See pp. 1-2, 13.
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.

Row sums give A006129. Cf. A054547.
The connected case is A062734, with loops A369195.
This is the covering case of A084546.
Column sums are A121251, with loops A173219.
The version with loops is A369199, row sums A322661.
The unlabeled version is A370167, row sums A002494.
A006125 counts simple graphs; also loop-graphs if shifted left.
Cf. A000666, A006649, A062740, A066383, A121252, A133686, A322700, A368597, A369196, A369197.

nn=5; s=Sum[(1+y)^Binomial[n,2]  x^n/n!, {n,0,nn}]; Range[0,nn]! CoefficientList[Series[ s Exp[-x], {x,0,nn}], {x,y}] //Grid  (* returns triangle indexed at n = 0, Geoffrey Critzer, Oct 07 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n],{2}],{k}],Union@@#==Range[n]&]],{n,0,5},{k,0,Binomial[n,2]}] (* Gus Wiseman, Feb 14 2024 *)

T(n, k) = Sum_{i=0..n} (-1)^(n-i)*C(n, i)*C(C(i, 2), k), k=0...n*(n-1)/2.

E.g.f.: exp(-x)*Sum_{n>=0} (1 + y)^C(n,2)*x^n/n!. - Geoffrey Critzer, Oct 07 2012

a(0) prepended by Gus Wiseman, Feb 14 2024

A367869 Number of labeled simple graphs covering n vertices and satisfying a strict version of the axiom of choice.

Original entry on oeis.org

1, 0, 1, 4, 34, 387, 5596, 97149, 1959938, 44956945, 1154208544, 32772977715, 1019467710328, 34473686833527, 1259038828370402, 49388615245426933, 2070991708598960524, 92445181295983865757, 4376733266230674345874, 219058079619119072854095, 11556990682657196214302036

Offset: 0

Gus Wiseman, Dec 08 2023

nonn

Number of labeled n-node graphs with at most one cycle in each component and no isolated vertices. - Andrew Howroyd, Dec 30 2023

			The a(3) = 4 graphs:
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200

The connected case is A129271.
The non-covering case is A133686, complement A367867.
The complement is A367868, connected A140638 (unlabeled A140636).
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems, unlabeled A000612, without singletons A016031.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A355740, A367770, A367863, A367902.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,5}]

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(sqrt(1/(1-t))*exp(t/2 - 3*t^2/4 - x)))} \\ Andrew Howroyd, Dec 30 2023

E.g.f.: exp(B(x) - x - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023

Terms a(7) and beyond from Andrew Howroyd, Dec 30 2023

A001429 Number of n-node connected unicyclic graphs.

Original entry on oeis.org

1, 2, 5, 13, 33, 89, 240, 657, 1806, 5026, 13999, 39260, 110381, 311465, 880840, 2497405, 7093751, 20187313, 57537552, 164235501, 469406091, 1343268050, 3848223585, 11035981711, 31679671920, 91021354454, 261741776369, 753265624291, 2169441973139, 6252511838796

Offset: 3

N. J. A. Sloane

Also unlabeled connected simple graphs with n vertices and n edges. The labeled version is A057500. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
Representatives of the a(3) = 1 through a(6) = 13 simple graphs:
  {12,13,23}  {12,13,14,23}  {12,13,14,15,23}  {12,13,14,15,16,23}
              {12,13,24,34}  {12,13,14,23,25}  {12,13,14,15,23,26}
                             {12,13,14,23,45}  {12,13,14,15,23,46}
                             {12,13,14,25,35}  {12,13,14,15,26,36}
                             {12,13,24,35,45}  {12,13,14,23,25,36}
                                               {12,13,14,23,25,46}
                                               {12,13,14,23,45,46}
                                               {12,13,14,23,45,56}
                                               {12,13,14,25,26,35}
                                               {12,13,14,25,35,46}
                                               {12,13,14,25,35,56}
                                               {12,13,14,25,36,56}
                                               {12,13,24,35,46,56}
(End)

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 150.
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).

Andrew Howroyd, Table of n, a(n) for n = 3..500
Washington G. Bomfim, A picture of the twenty one unicycles with 3,4,5 and 6 vertices
Audace A. V. Dossou-Olory, Graphs and unicyclic graphs with extremal connected subgraphs, arXiv:1812.02422 [math.CO], 2018.
R. K. Guy, Letter to N. J. A. Sloane, 1988-04-12 (annotated scanned copy) Includes illustrations for n <= 6.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
S. Karim, J. Sawada, Z. Alamgirz and S. M. Husnine, Generating bracelets with fixed content, Theoretical Computer Science, Volume 475, 4 March 2013, Pages 103-112.
Richard J. Mathar, Counting Connected Graphs without Overlapping Cycles, arXiv:1808.06264 [math.CO], 2018.
Marko Riedel et al., Non-isomorphic, connected, unicyclic graphs, Math Stackexchange, November 2018. (Derivation of algorithm and Maple implementation using PET.)
Marko Riedel, Maple implementation using PET.
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. doi: 10.2172/4180737.
Eric Weisstein's World of Mathematics, Unicyclic Graph

For at most one cycle we have A005703, labeled A129271, complement A140637.
Next-to-main diagonal of A054924. Cf. A000055.
The labeled version is A057500, connected case of A137916.
This is the connected case of A137917 and A236570.
Row k = 1 of A137918.
The version with loops is A368983.
A001349 counts unlabeled connected graphs.
A001434 and A006649 count unlabeled graphs with # vertices = # edges.
A006129 counts covering graphs, unlabeled A002494.
Cf. A014068, A054548, A116508, A133686, A140638, A369143, A369201.

Needs["Combinatorica`"];
nn=30;s[n_,k_]:=s[n,k]=a[n+1-k]+If[n<2k,0,s[n-k,k]];a[1]=1;a[n_]:=a[n]=Sum[a[i]s[n-1,i]i,{i,1,n-1}]/(n-1);rt=Table[a[i],{i,1,nn}];Apply[Plus,Table[Take[CoefficientList[CycleIndex[DihedralGroup[n],s]/.Table[s[j]->Table[Sum[rt[[i]]x^(k*i),{i,1,nn}],{k,1,nn}][[j]],{j,1,nn}],x],nn],{n,3,nn}]]  (* Geoffrey Critzer, Oct 12 2012, after code given by Robert A. Russell in A000081 *)
(* Second program: *)
TreeGf[nn_] := Module[{A}, A = Table[1, {nn}]; For[n = 1, n <= nn 1, n++, A[[n + 1]] = 1/n * Sum[Sum[ d*A[[d]], {d, Divisors[k]}]*A[[n - k + 1]], {k, 1, n}]]; x A.x^Range[0, nn-1]];
seq[n_] := Module[{t, g}, If[n < 3, {}, t = TreeGf[n - 2]; g[e_] := Normal[t + O[x]^(Quotient[n, e]+1)] /. x -> x^e  + O[x]^(n+1); Sum[Sum[ EulerPhi[d]*g[d]^(k/d), {d, Divisors[k]}]/k + If[OddQ[k], g[1]* g[2]^Quotient[k, 2], (g[1]^2 + g[2])*g[2]^(k/2-1)/2], {k, 3, n}]]/2 // Drop[CoefficientList[#, x], 3]&];
seq[32] (* Jean-François Alcover, Oct 05 2019, after Andrew Howroyd's PARI code *)

\\ TreeGf gives gf of A000081
TreeGf(N)={my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1] ) ); x*Ser(A)}
seq(n)={if(n<3, [], my(t=TreeGf(n-2)); my(g(e)=subst(t + O(x*x^(n\e)),x,x^e) + O(x*x^n)); Vec(sum(k=3, n, sumdiv(k, d, eulerphi(d)*g(d)^(k/d))/k + if(k%2, g(1)*g(2)^(k\2), (g(1)^2+g(2))*g(2)^(k/2-1)/2))/2))} \\ Andrew Howroyd, May 05 2018

a(n) = A068051(n) - A027852(n) - A000081(n).

More terms from Ronald C. Read
a(27) corrected, more terms, formula from Christian G. Bower, Feb 12 2002
Edited by Charles R Greathouse IV, Oct 05 2009
Terms a(30) and beyond from Andrew Howroyd, May 05 2018

cp's OEIS Frontend

A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A057500 Number of connected labeled graphs with n edges and n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions

A367902 Number of sets of nonempty subsets of {1..n} satisfying a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A367867 Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A116508 a(n) = C( C(n,2), n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Sage

Formula

Extensions

A367863 Number of n-vertex labeled simple graphs with n edges and no isolated vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica