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

A368597 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges.

Original entry on oeis.org

1, 1, 3, 17, 150, 1803, 27364, 501015, 10736010, 263461265, 7283725704, 223967628066, 7581128184175, 280103206674480, 11216492736563655, 483875783716549277, 22371631078155742764, 1103548801569848115255, 57849356643299101021960, 3211439288584038922502820

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

It doesn't matter for this sequence whether we use loops such as {x,x} or half-loops such as {x}.

			The a(0) = 1 through a(3) = 17 set-systems:
  {}  {{1}}  {{1},{2}}    {{1},{2},{3}}
             {{1},{1,2}}  {{1},{2},{1,3}}
             {{2},{1,2}}  {{1},{2},{2,3}}
                          {{1},{3},{1,2}}
                          {{1},{3},{2,3}}
                          {{2},{3},{1,2}}
                          {{2},{3},{1,3}}
                          {{1},{1,2},{1,3}}
                          {{1},{1,2},{2,3}}
                          {{1},{1,3},{2,3}}
                          {{2},{1,2},{1,3}}
                          {{2},{1,2},{2,3}}
                          {{2},{1,3},{2,3}}
                          {{3},{1,2},{1,3}}
                          {{3},{1,2},{2,3}}
                          {{3},{1,3},{2,3}}
                          {{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

This is the covering case of A014068.
Allowing edges of any positive size gives A054780, covering case of A136556.
Allowing any number of edges gives A322661, connected A062740.
The case of just pairs is A367863, covering case of A116508.
The unlabeled version is A368599.
The version contradicting strict AOC is A368730.
The connected case is A368951.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
A058891 counts set-systems, unlabeled A000612.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
Cf. A000272, A000666, A057500, A066383, A333331, A367869, A368596, A368600, A368928, A368951, A369199.

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

a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n)) \\ Andrew Howroyd, Jan 06 2024

a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k+1,2), n). - Andrew Howroyd, Jan 06 2024

Terms a(7) and beyond from Andrew Howroyd, Jan 06 2024

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Original entry on oeis.org

1, 3, 17, 144, 1623, 22804, 383415, 7501422

Offset: 1

Richard Stanley, Mar 15 2020

It is observed by Gus Wiseman in A368596 and A368730 that this sequence appears to be the complement of those sequences. If this is the case, then a(n) is the number of labeled graphs with loops allowed in which each connected component has an equal number of vertices and edges and the conjectured formula holds. Terms for n >= 9 are expected to be 167341283, 4191140394, 116425416531, ... - Andrew Howroyd, Jan 10 2024
From Gus Wiseman, Mar 22 2024: (Start)
An equivalent conjecture is that a(n) is the number of loop-graphs with n vertices and n edges such that it is possible to choose a different vertex from each edge. I call these graphs choosable. For example, the a(3) = 17 choosable loop-graphs are the following (loops shown as singletons):
  {{1},{2},{3}}  {{1},{2},{1,3}}  {{1},{1,2},{1,3}}  {{1,2},{1,3},{2,3}}
                 {{1},{2},{2,3}}  {{1},{1,2},{2,3}}
                 {{1},{3},{1,2}}  {{1},{1,3},{2,3}}
                 {{1},{3},{2,3}}  {{2},{1,2},{1,3}}
                 {{2},{3},{1,2}}  {{2},{1,2},{2,3}}
                 {{2},{3},{1,3}}  {{2},{1,3},{2,3}}
                                  {{3},{1,2},{1,3}}
                                  {{3},{1,2},{2,3}}
                                  {{3},{1,3},{2,3}}
(End)

			For n=2 the parking functions are (1,1), (1,2), (2,1). They are the only integer points in their convex hull. For n=3, in addition to the 16 parking functions, there is the additional point (2,2,2).

R. P. Stanley (Proposer), Problem 12191, Amer. Math. Monthly, 127:6 (2020), 563.

Thomas Selig, The stochastic sandpile model on complete graphs, arXiv:2209.07301 [math.PR], 2022.

All of the following relative references pertain to the conjecture:
The case of unique choice A000272.
The version without the choice condition is A014068, covering A368597.
The case of just pairs A137916.
For any number of edges of any positive size we have A367902.
The complement A368596, covering A368730.
Allowing edges of any positive size gives A368601, complement A368600.
Counting by singletons gives A368924.
For any number of edges we have A368927, complement A369141.
The connected case is A368951.
The unlabeled version is A368984, complement A368835.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
Cf. A000169, A000666, A057500, A062740, A129271, A133686, A367863, A367903, A369146, A369199.

Conjectured e.g.f.: exp(-log(1-T(x))/2 + T(x)/2 - T(x)^2/4) where T(x) = -LambertW(-x) is the e.g.f. of A000169. - Andrew Howroyd, Jan 10 2024

A368596 Number of n-element sets of singletons or pairs of distinct elements of {1..n}, or loop graphs with n edges, such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 3, 66, 1380, 31460, 800625, 22758918, 718821852, 25057509036, 957657379437, 39878893266795, 1799220308202603, 87502582432459584, 4566246347310609247, 254625879822078742956, 15115640124974801925030, 952050565540607423524658, 63425827673509972464868323

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

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}}

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

The version without the choice condition is A014068, covering A368597.
The complement appears to be A333331.
For covering pairs we have A367868.
Allowing edges of any positive size gives A368600, any length A367903.
The covering case is A368730.
The unlabeled version is A368835.
A000085 counts set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
A322661 counts covering half-loop-graphs, connected A062740.
A369141 counts non-choosable loop-graphs, covering A369142.
A369146 counts unlabeled non-choosable loop-graphs, covering A369147.
Cf. A000272, A000666, A057500, A129271, A133686, A367769, A367863, A367867, A367869, A367901, A367907, A368097, A369199.

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

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Original entry on oeis.org

1, 2, 15, 316, 16885, 2174586, 654313415, 450179768312, 696979588034313, 2398044825254021110, 18151895792052235541515, 299782788128536523836784628, 10727139906233315197412684689421

Offset: 1

N. J. A. Sloane

nonn

From Gus Wiseman, Jan 02 2024: (Start)
Also the number of n-element sets of finite nonempty subsets of {1..n}, including a unique singleton, such that there is exactly one way to choose a different element from each. For example, the a(0) = 0 through a(3) = 15 set-systems are:
  .  {{1}}  {{1},{1,2}}  {{1},{1,2},{1,3}}
            {{2},{1,2}}  {{1},{1,2},{2,3}}
                         {{1},{1,3},{2,3}}
                         {{2},{1,2},{1,3}}
                         {{2},{1,2},{2,3}}
                         {{2},{1,3},{2,3}}
                         {{3},{1,2},{1,3}}
                         {{3},{1,2},{2,3}}
                         {{3},{1,3},{2,3}}
                         {{1},{1,2},{1,2,3}}
                         {{1},{1,3},{1,2,3}}
                         {{2},{1,2},{1,2,3}}
                         {{2},{2,3},{1,2,3}}
                         {{3},{1,3},{1,2,3}}
                         {{3},{2,3},{1,2,3}}
These set-systems are all connected.
The case of labeled graphs is A000169.
(End)

			a(2) = 2: o-->--o (2 ways)
a(3) = 15: o-->--o-->--o (6 ways) and
o ... o o-->--o
.\ . / . \ . /
. v v ... v v
.. o ..... o
(3 ways) (6 ways)

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

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

A diagonal of A058876.
Row sums of A350487.
The unlabeled version is A350415.
Column k=1 of A361718.
Cf. A003026, A003028, A345258.
For any number of sinks we have A003024, unlabeled A003087.
For n-1 sinks we have A058877.
For a fixed sink we have A134531 (up to sign), column k=1 of A368602.
Cf. A000169, A058891, A059201, A082402, A088957, A323818, A334282, A367904, A368600, A368601.

Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Count[#,{}]==1&&Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,4}] (* _Gus Wiseman, Jan 02 2024 *)

\\ requires A058876.
my(T=A058876(20)); vector(#T, n, T[n][1]) \\ Andrew Howroyd, Dec 27 2021

\\ see Marcel et al. link (formula for a').
seq(n)={my(a=vector(n)); a[1]=1; for(n=2, #a, a[n]=sum(k=1, n-1, (-1)^(k-1) * binomial(n,k) * (2^(n-k)-1)^k * a[n-k])); a} \\ Andrew Howroyd, Jan 01 2022

a(n) = (-1)^(n-1) * n * A134531(n). - Gus Wiseman, Jan 02 2024

More terms from Vladeta Jovovic, Apr 10 2001

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

A369142 Number of labeled loop-graphs covering {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 22, 616, 26084, 1885323, 253923163, 66619551326, 34575180977552, 35680008747431929, 73392583275070667841, 301348381377662031986734, 2471956814761854578316988092, 40530184362443276558060719358471, 1328619783326799871747200601484790193

Offset: 0

Gus Wiseman, Jan 20 2024

nonn

Also labeled loop-graphs covering n vertices with at least one connected component containing more edges than vertices.

			The a(0) = 0 through a(3) = 22 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{3},{1,2}}
                         {{1},{2},{3},{1,3}}
                         {{1},{2},{3},{2,3}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,2},{2,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3}}
                         {{1},{3},{1,2},{2,3}}
                         {{1},{3},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3}}
                         {{2},{3},{1,2},{2,3}}
                         {{2},{3},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{2},{1,2},{1,3},{2,3}}
                         {{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{3},{1,2},{2,3}}
                         {{1},{2},{3},{1,3},{2,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{3},{1,2},{1,3},{2,3}}
                         {{2},{3},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

The version for a unique choice is A000272, unlabeled A000055.
Without the choice condition we have A006125, unlabeled A000088.
The case without loops is A367868, covering case of A367867.
For exactly n edges we have A368730, covering case of A368596.
The complement is counted by A369140, covering case of A368927.
This is the covering case of A369141.
For n edges and no loops we have A369144, covering A369143.
The unlabeled version is A369147, covering case of A369146.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable graphs, unlabeled A005703.
A133686 counts choosable graphs, covering A367869.
A322661 counts covering loop-graphs, connected A062740, unlabeled A322700.
A367902 counts choosable set-systems, complement A367903.
Cf. A000666, A003465, A006649, A116508, A137916, A333331, A368600, A368924, A368984, A369145, A369194.

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

Inverse binomial transform of A369141.

a(n) = A322661(n) - A369140(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A368951 Number of connected labeled graphs with n edges and n vertices and with loops allowed.

Original entry on oeis.org

1, 1, 2, 10, 79, 847, 11436, 185944, 3533720, 76826061, 1880107840, 51139278646, 1530376944768, 49965900317755, 1767387701671424, 67325805434672100, 2747849045156064256, 119626103584870552921, 5533218319763109888000, 270982462739224265922466

Offset: 0

Andrew Howroyd, Jan 10 2024

nonn

Exponential transform appears to be A333331. - Gus Wiseman, Feb 12 2024

			From _Gus Wiseman_, Feb 12 2024: (Start)
The a(0) = 1 through a(3) = 10 loop-graphs:
  {}  {11}  {11,12}  {11,12,13}
            {22,12}  {11,12,23}
                     {11,13,23}
                     {22,12,13}
                     {22,12,23}
                     {22,13,23}
                     {33,12,13}
                     {33,12,23}
                     {33,13,23}
                     {12,13,23}
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.

Cf. A000169, A333331, A063170, A053506.
This is the connected covering case of A014068.
The case without loops is A057500, covering case of A370317.
Allowing any number of edges gives A062740, connected case of A322661.
This is the connected case of A368597.
The unlabeled version is A368983, connected case of A368984.
For at most n edges we have A369197.
A000085 counts set partitions into singletons or pairs.
A006129 counts covering graphs, connected A001187.
Cf. A000272, A000666, A054780, A116508, A136556, A367863, A368600.

egf:= (L-> 1-L/2-log(1+L)/2-L^2/4)(LambertW(-x)):
a:= n-> n!*coeff(series(egf, x, n+1), x, n):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 10 2024

seq(n)={my(t=-lambertw(-x + O(x*x^n))); Vec(serlaplace(-log(1-t)/2 + t/2 - t^2/4 + 1))}

a(n) = A000169(n) + A057500(n) for n > 0.
E.g.f.: 1 - log(1-T(x))/2 + T(x)/2 - T(x)^2/4 where T(x) = -LambertW(-x) is the e.g.f. of A000169.
From Peter Luschny, Jan 10 2024: (Start)
a(n) = (exp(n)*Gamma(n + 1, n) - (n - 1)*n^(n - 1))/(2*n) for n > 0.
a(n) = (1/2)*(A063170(n)/n - A053506(n)) for n > 0.  (End)

A369146 Number of unlabeled loop-graphs with up to n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 1, 8, 60, 471, 4911, 78797, 2207405, 113740613, 10926218807, 1956363413115, 652335084532025, 405402273420833338, 470568642161119515627, 1023063423471189429817807, 4178849203082023236054797465, 32168008290073542372004072630072, 468053896898117580623237189882068990

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

			The a(0) = 0 through a(3) = 8 loop-graphs (loops shown as singletons):
  .  .  {{1},{2},{1,2}}  {{1},{2},{1,2}}
                         {{1},{2},{3},{1,2}}
                         {{1},{2},{1,2},{1,3}}
                         {{1},{2},{1,3},{2,3}}
                         {{1},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3}}
                         {{1},{2},{1,2},{1,3},{2,3}}
                         {{1},{2},{3},{1,2},{1,3},{2,3}}

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

Without the choice condition we have A000666, labeled A006125 (shifted).
For a unique choice we have A087803, labeled A088957.
The case without loops is A140637, labeled A367867 (covering A367868).
For exactly n edges we have A368835, labeled A368596.
The labeled complement is A368927, covering A369140.
The labeled version is A369141, covering A369142.
The complement is counted by A369145, covering A369200.
The covering case is A369147.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A322661 counts labeled covering loop-graphs, unlabeled A322700.
Cf. A000088, A000612, A006649, A062740, A134964, A137917, A140638, A368600, A368984, A369199.

brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{(Union@@m)[[i]],p[[i]]}, {i,Length[p]}])], {p,Permutations[Range[Length[Union@@m]]]}]]];
Table[Length[Union[brute /@ Select[Subsets[Subsets[Range[n],{1,2}]], Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,4}]

Partial sums of A369147.

a(n) = A000666(n) - A369145(n). - Andrew Howroyd, Feb 02 2024

a(6) onwards from Andrew Howroyd, Feb 02 2024

A368730 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges, such that it is not possible to choose a different element from each.

Original entry on oeis.org

0, 0, 0, 0, 6, 180, 4560, 117600, 3234588, 96119982, 3092585310, 107542211535, 4029055302855, 162040513972623, 6970457656110039, 319598974394563500, 15568332397812799920, 803271954062642638830, 43778508937914677872788, 2513783434620146896920843

Offset: 0

Gus Wiseman, Jan 04 2024

nonn

			The a(4) = 6 set-systems:
  {{1},{2},{1,2},{3,4}}
  {{1},{3},{1,3},{2,4}}
  {{1},{4},{1,4},{2,3}}
  {{2},{3},{1,4},{2,3}}
  {{2},{4},{1,3},{2,4}}
  {{3},{4},{1,2},{3,4}}

Andrew Howroyd, Table of n, a(n) for n = 0..200
Eric Weisstein's World of Mathematics, Graph Loop.
ProofWiki, Definition:Loop-Graph

The case of a unique choice appears to be A000272.
The version without the choice condition is A368597, non-covering A014068.
The complement appears to be A333331.
The non-covering case is A368596, allowing edges of any size A368600.
Allowing any number of edges of any size gives A367903, ranks A367907.
Allowing any number of non-singletons gives A367868, non-covering A367867.
A000085 counts set partitions into singletons or pairs.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A100861 counts set partitions into singletons or pairs by number of pairs.
A111924 counts set partitions into singletons or pairs by length.
A322661 counts labeled covering half-loop-graphs, connected A062740.
Cf. A000666, A116508, A133686, A367863, A367869, A367901, A368532.

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

a(n) = A368596(n) + A368597(n) - A014068(n). - Andrew Howroyd, Jan 10 2024

Terms a(7) and beyond from Andrew Howroyd, Jan 10 2024

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

A368597 Number of n-element sets of singletons or pairs of distinct elements of {1..n} with union {1..n}, or loop-graphs covering n vertices with n edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A333331 Number of integer points in the convex hull in R^n of parking functions of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A368596 Number of n-element sets of singletons or pairs of distinct elements of {1..n}, or loop graphs with n edges, such that it is not possible to choose a different element from each.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A003025 Number of n-node labeled acyclic digraphs with 1 out-point.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

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

A369142 Number of labeled loop-graphs covering {1..n} such that it is not possible to choose a different vertex from each edge (non-choosable).

Views