0,3

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)

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)

Thomas E. Allen, Judy Goldsmith, and Nicholas Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.

Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, Discrete Mathematics, 343(11), 112041.

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, Arthur Choi, and Adnan Darwiche, On Pruning with the MDL Score, JMLR: Wksp., Conf. Proc. (2016) Vol. 52, 98-109.

Weixi Chen, Mee Seong Im, Mikhail Khovanov, Catherine Lillja, and Nicolas Rugo, Pairs of eventually constant maps and nilpotent pairs, arXiv:2512.03367 [math.RT], 2025. See p. 15.

Benjamin L. Davis, Saakshi More, Zehao Jin, Mario Pasquato, Andrea Valerio Macciò, and Feng Yuan, Causal Reversal in the M_dot-sigma_0 Relation: Implications for High-Redshift Supermassive Black Hole Mass Estimates, preprint (2025). See p. 2.

Stefan Engström, Random acyclic orientations of graphs, Master's thesis, Royal Inst. Tech. (KTH, Stockholm, Sweden 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.

Rustem Kakimov and Xing Tan, On Upward Book Embeddability of DAGs, 37th Canad. Conf. Comput. Geom. (CCCG 2025). See p. 5.

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: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, Art. 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).

Brendan D. McKay, Frederique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M. Wanless, Herbert S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Int. Seq. (2004) Vol. 7, Art. 04.3.3.

Brendan D. McKay, Frederique E. Oggier, Gordon F. Royle, N. J. A. Sloane, Ian M. Wanless, and Herbert S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], Oct 28 2003.

Alexander Motzek and Ralf Möller, Exploiting Innocuousness in Bayesian Networks, Preprint 2015.

Yisu Peng, Yuxiang Jiang, and Predrag Radivojac, Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies, arXiv:1712.09679 [cs.DS], 2017.

Jonas Peters, Joris Mooij, Dominik Janzing, and Bernhard Schölkopf, Causal Discovery with Continuous Additive Noise Models, arXiv preprint arXiv:1309.6779 [stat.ML], 2013.

Simon Rittel and Sebastian Tschiatschek, Distributions over DAGs for Causal Discovery: Limitations of Expressiveness, 22nd Int'l Wksp. Mining and Learning with Graphs (2025) Paper 22. See p. 14.

Robert W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)

V. I. Rodionov, On the number of labeled acyclic digraphs, Disc. Math. (1992) Vol. 105, No. 1-3, 319-321.

Ilya Shpitser, Thomas S. Richardson, James M. Robins, and Robin Evans, Parameter and Structure Learning in Nested Markov Models, arXiv preprint arXiv:1207.5058 [stat.ML], 2012.

Ilya Shpitser, Robin J. Evans, Thomas S. Richardson, and James M. Robins, Introduction to nested Markov models, Behaviormetrika (2014) Vol. 41, No. 1, 3-39.

Richard P. Stanley, Acyclic orientation of graphs, Disc. Math., N. Holland Pub. Co. (1973) Vol. 5, 171-178. See also Disc. Math. (2006) Vol. 306, Issues 10-11, 905-909.

Christian Toth, Christian Knoll, Franz Pernkopf, and Robert Peharz, Rao-Blackwellising Bayesian Causal Inference, arXiv:2402.14781 [cs.LG], 2024.

Davi Valério, Chrysoula Zerva, Mariana Pinto, Ricardo Santos, and André Carreiro, Counterfactual Fairness with Graph Uncertainty, arXiv:2601.03203 [cs.LG], 2026. See p. 4, references.

Sumanth Varambally, Yi-An Ma, and Rose Yu, Discovering Mixtures of Structural Causal Models from Time Series Data, arXiv:2310.06312 [cs.LG], 2023.

Stephan Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proc. SIAM Mtg. Anal. Algor. Combin. (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.

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

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

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 *)

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

(PARI) {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

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.

Sequence in context: A136173 A243440 A306783 * A224679 A213599 A179473

Adjacent sequences: A003021 A003022 A003023 * A003025 A003026 A003027

nonn,easy,nice

approved