A003025 -id:A003025 - 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

A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.

Original entry on oeis.org

0, 2, 9, 28, 75, 186, 441, 1016, 2295, 5110, 11253, 24564, 53235, 114674, 245745, 524272, 1114095, 2359278, 4980717, 10485740, 22020075, 46137322, 96468969, 201326568, 419430375, 872415206, 1811939301, 3758096356, 7784628195, 16106127330, 33285996513

Offset: 1

N. J. A. Sloane, Jan 07 2001

Convolution of 2^n+1 (A000051) and 2^n-1 (A000225). - Graeme McRae, Jun 07 2006
Let Q be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all nonempty elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = |Q|. - Ross La Haye, Feb 20 2008, Oct 21 2008
Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). - R. J. Mathar, Jan 25 2009
The La Haye binary relation Q is more clearly stated as x is nonempty and y has one more element than x. If x is a k-set than the number of such pairs is binomial( n, k) * (n-k). - Michael Somos, Mar 29 2012
Select one of the n nodes of the digraph and select a nonempty subset of the rest to connect to the selected node. This can be done in n * (2^(n-1) - 1) ways. - Michael Somos, Mar 29 2012
Column 1 of A198204. - Peter Bala, Aug 01 2012
a(n) is the number of ternary sequences of length n that contain one 0 and at least one 1.  For example, a(3)=9 since the sequences are the 3 permutations of 011 and the 6 permutations of 012. - Enrique Navarrete, Apr 05 2021
a(n) is also the number of multiplications required to compute the permanent of general n X n matrices using canonical trellis method (see Theorem 5, p. 10 in Kiah et al.). - Stefano Spezia, Nov 02 2021

			G.f. = 2*x^2 + 9*x^3 + 28*x^4 + 75*x^5 + 186*x^6 + 441*x^7 + 1016*x^8 + ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
Gerta Rucker and Christoph Rucker, "Walk counts, Labyrinthicity and complexity of acyclic and cyclic graphs and molecules", J. Chem. Inf. Comput. Sci., 40 (2000), 99-106. See Table 1 on page 101. [From Parthasarathy Nambi, Sep 26 2008]

Vincenzo Librandi, Table of n, a(n) for n = 1..2001
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 12.
Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.
Tamás Szakács, Convolution of second order linear recursive sequences. II. Commun. Math. 25, No. 2, 137-148 (2017), remark 3.
Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 36.
Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Second column of A058876. Cf. A003025, A003026.
Column k=1 of A133399.
Cf. A198204.

[(n+1)*2^n-n-1: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011

[seq (stirling2(n,2)*n,n=1..29)]; # Zerinvary Lajos, Dec 06 2006
a:=n->sum(k*binomial(n,k), k=2..n): seq(a(n), n=1..29); # Zerinvary Lajos, May 08 2007

Table[(n+1)*2^n-n-1, {n, 0, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
a[ n_] := Sum[ Binomial[ n, k] (n - k), {k, n-1}]; (* Michael Somos, Mar 29 2012 *)

{a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* Michael Somos, Mar 29 2012 */

[stirling_number2(i,2)*i for i in range(1,26)] # Zerinvary Lajos, Jun 27 2008

[(n+1)*gaussian_binomial(n,1,2) for n in range(0,29)] # Zerinvary Lajos, May 31 2009

a(n+1) = (n+1)*2^n - n - 1 = Sum_{j=0..n} (n+j)*2^(n-j-1) = A048493(n)-1 = Column sum of A062111. - Henry Bottomley, May 30 2001
From R. J. Mathar, Jan 25 2009: (Start)
G.f.: x^2*(2-3*x)/((1-2*x)*(1-x))^2.
a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). (End)
a(n) = Sum_{k=1..n-1} binomial(n, k) * (n-k). - Michael Somos, Mar 29 2012
E.g.f: x*exp(x)*(exp(x)-1). - Enrique Navarrete, Apr 05 2021

More terms from Vladeta Jovovic, Apr 10 2001

A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 164, 18625, 5491851, 4649088885, 12219849683346

Offset: 0

Gus Wiseman, Jan 01 2024

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(3) = 3 set-systems:
  {{1},{2},{1,2}}
  {{1},{3},{1,3}}
  {{2},{3},{2,3}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367903, ranks A367907, no singletons A367769.
The complement is A368601, any length A367902 (see also A367770, 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, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367868, A367901, A368094, A368097.

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

from itertools import combinations, product, chain
from scipy.special import comb
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(int(comb(2**n-1,n) - a(n))) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) = A136556(n) - A368601(n).

a(6) from Robert P. P. McKone, Jan 02 2024

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

A368601 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.

Original entry on oeis.org

1, 1, 3, 32, 1201, 151286, 62453670, 84707326890, 384641855115279

Offset: 0

Gus Wiseman, Jan 01 2024

			The a(2) = 3 set-systems:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
Non-isomorphic representatives of the a(3) = 32 set-systems:
  {{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}}
  {{1},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}

Wikipedia, Axiom of choice.

For a unique choice we have A003024, any length A367904 (ranks A367908).
Sets of n nonempty subsets of {1..n} are counted by A136556.
For any length we have A367902, ranks A367906, no singletons A367770.
The complement is A368600, any length A367903 (see also A367907, A367769).
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, unlabeled A323819.
Cf. A003025, A088957, A133686, A334282, A355529, A355740, A367862, A367867, A367901, A367905, A368094, A368097.

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

from itertools import combinations, product, chain
def v(c):
    for elements in product(*c):
        if len(set(elements)) == len(elements):
            return True
    return False
def a(n):
    if n == 0:
        return 1
    subsets = list(chain.from_iterable(combinations(range(1, n + 1), r) for r in
range(1, n + 1)))
    cs = combinations(subsets, n)
    c = sum(1 for c in cs if v(c))
    return c
[print(a(n)) for n in range(7)] # Robert P. P. McKone, Jan 02 2024

a(n) + A368600(n) = A136556(n).

a(6) from Robert P. P. McKone, Jan 02 2024

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

A134531 G.f.: Sum_{n>=0} a(n)x^n/(n!2^(n(n-1)/2)) = log( Sum_{n>=0} x^n/(n!2^(n*(n-1)/2)) ).

Original entry on oeis.org

0, 1, -1, 5, -79, 3377, -362431, 93473345, -56272471039, 77442176448257, -239804482525402111, 1650172344732021412865, -24981899010711376986398719, 825164608171793476724052668417, -59053816996641612758331731690504191, 9102696765174239045811746247171452452865

Offset: 0

Paul D. Hanna, Oct 30 2007

			Let g.f. G(x) = Sum_{n>=0} a(n)*x^n/[ n! * 2^(n*(n-1)/2) ]
then exp(G(x)) = Sum_{n>=0} x^n/[ n! * 2^(n*(n-1)/2) ];
G.f.: G(x) = x - x^2/4 + 5x^3/48 - 79x^4/1536 + 3377x^5/122880 + ...
exp(G(x)) = 1 + x + x^2/4 + x^3/48 + x^4/1536 + x^5/122880 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..77
Kimmo Berg, Complexity of solution structures in nonlinear pricing, Ann. Oper. Res. 206, 23-37 (2013).
Sergei Chmutov, Maxim Kazarian and Sergey Lando, Polynomial graph invariants and the KP hierarchy, arXiv:1803.09800 [math.CO], 2018.

Cf. related triangles: A134530, A111636.

Cf. A003025, A011266, A118197 (variant).

a[0] = 0;
a[n_] := a[n] = 1 - Sum[2^(k(n-k)) Binomial[n-1, k-1] a[k], {k, 1, n-1}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 26 2018 *)

{a(n)=n!*2^(n*(n-1)/2)*polcoeff(log(sum(k=0,n,x^k/(k!*2^(k*(k-1)/2)))+x*O(x^n)),n)}

Equals column 0 of triangle A134530, which is the matrix log of triangle A111636, where A111636(n,k) = (2^k)^(n-k)*C(n,k).
From Peter Bala, Apr 01 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with a different offset) is E(x)/E(2*x) = Sum_{n >= 0} a(n-1)*x^n/(n!*2^C(n,2)) = 1 - x + 5*x^2/(2!*2) - 79*x^3/(3!*2^3) + 3377*x^4/(4!*2^6) - ....
Recurrence equation:
a(n) = 1 - Sum_{k = 1..n-1} 2^(k*(n-k))*C(n-1,k-1)*a(k) with a(1) = 1. (End)
a(n) = (-1)^(n-1)*A003025(n)/n. - Andrew Howroyd, Jan 07 2022

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

A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Sage

Formula

Extensions

A368600 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is not possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A368601 Number of ways to choose a set of n nonempty subsets of {1..n} such that it is possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A134531 G.f.: Sum_{n>=0} a(n)*x^n/(n!*2^(n*(n-1)/2)) = log( Sum_{n>=0} x^n/(n!*2^(n*(n-1)/2)) ).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A350415 Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A134531 G.f.: Sum_{n>=0} a(n)x^n/(n!2^(n(n-1)/2)) = log( Sum_{n>=0} x^n/(n!2^(n*(n-1)/2)) ).