A367770 -id:A367770 - cp's OEIS frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

1, 1, 2, 8, 57, 608, 8524, 145800, 2918123, 66617234, 1704913434, 48300128696, 1499864341015, 50648006463048, 1847622972848648, 72406232075624192, 3033607843748296089, 135313823447621913500, 6402077421524339766058, 320237988317922139148736

Offset: 0

Washington Bomfim, May 12 2008

The total number of those graphs of order 5 is 608. The number of forests of trees on n labeled nodes of order 5 is 291, so the majority of the graphs of that kind have one or more unicycles.

Also the number of labeled graphs with n vertices satisfying a strict version of the axiom of choice. 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 connected case is A129271, complement A140638. The unlabeled version is A134964. - Gus Wiseman, Dec 22 2023

			Below we see the 7 partitions of n=5 in the form c_1 + 2c_2 + ... + nc_n followed by the corresponding number of graphs. We consider the values of A129271(j) given by the table
   j|1|2|3| 4|  5|
----+-+-+-+--+---+
a(j)|1|1|4|31|347|
1*5 -> 5!1^5 / (1!^5 * 5!) = 1
2*1 + 1*3 -> 5!1^1 * 1^3 / (2!^1 * 1! * 1!^3 * 3!) = 10
2*2 + 1*1 -> 5!1^2 * 1^1 / (2!^2 * 2! * 1!^1 * 1!) = 15
3*1 + 1*2 -> 5!4^1 * 1^2 / (3!^1 * 1! * 1!^2 * 2!) = 40
3*1 + 2*1 -> 5!4^1 * 1^1 / (3!^1 * 1! * 2!^1 * 1!) = 40
4*1 + 1*1 -> 5!31^1 * 1^1 / (4!^1 * 1! * 1!^1 * 1!) = 155
5*1 -> 5!347^1 / (5!^1 * 1!) = 347
Total 608

Alois P. Heinz, Table of n, a(n) for n = 0..386
Wikipedia, Pseudoforest

Cf. A129137, A005703, A000272, A057500, A137916, A001858.
Row sums of triangle A144228. - Alois P. Heinz, Sep 15 2008
Cf. A137352. - Vladeta Jovovic, Sep 16 2008
The unlabeled version is A134964.
The complement is counted by A367867, covering A367868, connected A140638.
The covering case is A367869, connected A129271.
For set-systems we have A367902, ranks A367906.
The complement for set-systems is A367903, ranks A367907.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A143543 counts graphs by number of connected components.
Cf. A001187, A058891, A116508, A355740, A367769, A367770, A367863, A367901.

cy:= proc(n) option remember; binomial(n-1, 2)*
        add((n-3)!/(n-2-t)! *n^(n-2-t), t=1..n-2)
     end:
T:= proc(n,k) option remember;
      if k=0 then 1
    elif k<0 or n add(T(n,k), k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Sep 15 2008

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[ Exp[t/2-3t^2/4]/(1-t)^(1/2),{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Select[Tuples[#], UnsameQ@@#&]!={}&]],{n,0,5}] (* Gus Wiseman, Dec 22 2023 *)

x='x+O('x^50); Vec(serlaplace(sqrt(-lambertw(-x)/(x*(1+ lambertw(-x))))*exp(-(3/4)*lambertw(-x)^2))) \\ G. C. Greubel, Nov 16 2017

a(0) = 1; for n >=1, a(n) = Sum of n!prod_{j=1}^n\{ frac{ A129271(j)^{c_j} } { j!^{c_j}c_j! } } over all the partitions of n, c_1 + 2c_2 + ... + nc_n; c_1, c_2, ..., c_n >= 0.
a(n) = Sum_{k=0..n} A144228(n,k). - Alois P. Heinz, Sep 15 2008
E.g.f.: sqrt(-LambertW(-x)/(x*(1+LambertW(-x))))*exp(-3/4 * LambertW(-x)^2). - Vladeta Jovovic, Sep 16 2008
E.g.f.: A(x)*B(x) where A(x) is the e.g.f. for A137916 and B(x) is the e.g.f. for A001858. - Geoffrey Critzer, Mar 23 2013
a(n) ~ 2^(-1/4) * Gamma(3/4) * exp(-1/4) * n^(n-1/4) / sqrt(Pi) * (1-7*Pi/(12*Gamma(3/4)^2*sqrt(n))). - Vaclav Kotesovec, Oct 08 2013
E.g.f.: exp(B(x) - 1) where B(x) is the e.g.f. of A129271. - Andrew Howroyd, Dec 30 2023

Corrected and extended by Alois P. Heinz and Vladeta Jovovic, Sep 15 2008

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

Original entry on oeis.org

0, 0, 1, 67, 30997, 2147296425, 9223372036784737528, 170141183460469231731687303625772608225, 57896044618658097711785492504343953926634992332820282019728791606173188627779

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) = 1 set-system is {{1},{2},{1,2}}.
The a(3) = 67 set-systems have following 21 non-isomorphic representatives:
  {{1},{2},{1,2}}
  {{1},{2},{3},{1,2}}
  {{1},{2},{3},{1,2,3}}
  {{1},{2},{1,2},{1,3}}
  {{1},{2},{1,2},{1,2,3}}
  {{1},{2},{1,3},{2,3}}
  {{1},{2},{1,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3}}
  {{1},{1,2},{1,3},{1,2,3}}
  {{1},{1,2},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3}}
  {{1},{2},{3},{1,2},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3}}
  {{1},{2},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,3},{2,3},{1,2,3}}
  {{1},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3}}
  {{1},{2},{3},{1,2},{1,3},{1,2,3}}
  {{1},{2},{1,2},{1,3},{2,3},{1,2,3}}
  {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Wikipedia, Axiom of choice.

Multisets of multisets of this type are ranked by A355529.
The version without singletons is A367769.
The version for simple graphs is A367867, covering A367868.
The version allowing empty edges is A367901.
The complement is A367902, without singletons A367770, ranks A367906.
For a unique choice (instead of none) we have A367904, ranks A367908.
These set-systems have ranks A367907.
An unlabeled version is A368094, for multiset partitions A368097.
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, A368409, A368413.

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

a(n) + A367904(n) + A367772(n) = A058891(n+1) = 2^(2^n-1).

a(5)-a(8) from Christian Sievers, Jul 26 2024

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

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.

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

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 26, 28, 32, 33, 34, 35, 36, 37, 38, 40, 41, 44, 48, 49, 50, 52, 56, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 80, 81, 82, 84, 88, 96, 97, 98, 100, 104, 112, 128, 129, 130, 131, 132

Offset: 1

Gus Wiseman, Dec 11 2023

Also BII-numbers of set-systems (sets of nonempty sets) satisfying a strict version of the axiom of choice.
A binary index of k (row k of A048793) is any position of a 1 in its reversed binary expansion. A set-system is a finite set of finite nonempty sets. We define the set-system with BII-number k to be obtained by taking the binary indices of each binary index of k. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary digits (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.
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 set-system {{2,3},{1,2,3},{1,4}} with BII-number 352 has choices such as (2,1,4) that satisfy the axiom, so 352 is in the sequence.
The terms together with the corresponding set-systems begin:
   1: {{1}}
   2: {{2}}
   3: {{1},{2}}
   4: {{1,2}}
   5: {{1},{1,2}}
   6: {{2},{1,2}}
   8: {{3}}
   9: {{1},{3}}
  10: {{2},{3}}
  11: {{1},{2},{3}}
  12: {{1,2},{3}}
  13: {{1},{1,2},{3}}
  14: {{2},{1,2},{3}}
  16: {{1,3}}
  17: {{1},{1,3}}

John Tyler Rascoe, Table of n, a(n) for n = 1..10000
Wikipedia, Axiom of choice.

These set-systems are counted by A367902, non-isomorphic A368095.
Positions of positive terms in A367905, firsts A367910, sorted A367911.
The complement is A367907.
If there is one unique choice we get A367908, counted by A367904.
If there are multiple choices we get A367909, counted by A367772.
Unlabeled multiset partitions of this type are A368098, complement A368097.
A version for MM-numbers of multisets is A368100, complement A355529.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A058891 counts set-systems, A003465 covering, A323818 connected.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326031 gives weight of the set-system with BII-number n.
Cf. A000612, A055621, A059519, A072639, A083323, A309326, A326702, A326753, A367770, A367912.
BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326751 (blobs), A326752 (hypertrees), A326754 (covers), A326783 (uniform), A326784 (regular), A326788 (simple), A330217 (achiral).

bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
Select[Range[100], Select[Tuples[bpe/@bpe[#]], UnsameQ@@#&]!={}&]

from itertools import count, islice, product
def bin_i(n): #binary indices
    return([(i+1) for i, x in enumerate(bin(n)[2:][::-1]) if x =='1'])
def a_gen(): #generator of terms
    for n in count(1):
        for j in list(product(*[bin_i(k) for k in bin_i(n)])):
            if len(set(j)) == len(j):
                yield(n); break
A367906_list = list(islice(a_gen(),100)) # John Tyler Rascoe, Dec 23 2023

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

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.

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

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

Original entry on oeis.org

0, 0, 0, 0, 7, 381, 21853, 1790135, 250562543, 66331467215, 34507857686001, 35645472109753873, 73356936892660012513, 301275024409580265134121, 2471655539736293803311467943, 40527712706903494712385171632959, 1328579255614092966328511889576785109

Offset: 0

Gus Wiseman, Dec 08 2023

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(4) = 7 graphs:
  {{1,2},{1,3},{1,4},{2,3},{2,4}}
  {{1,2},{1,3},{1,4},{2,3},{3,4}}
  {{1,2},{1,3},{1,4},{2,4},{3,4}}
  {{1,2},{1,3},{2,3},{2,4},{3,4}}
  {{1,2},{1,4},{2,3},{2,4},{3,4}}
  {{1,3},{1,4},{2,3},{2,4},{3,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 connected case is A140638, unlabeled A140636.
The non-covering case is A367867.
The complement is A367869, connected A129271, non-covering A133686.
The version for set-systems is A367903, ranks A367907.
A001187 counts connected graphs, A001349 unlabeled.
A006125 counts graphs, A000088 unlabeled.
A006129 counts covering graphs, A002494 unlabeled.
A058891 counts set-systems (without singletons A016031), unlabeled A000612.
A059201 counts covering T_0 set-systems, unlabeled A319637, ranks A326947.
A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A367769, A367770, A367863, A367901, A367902, A367904.

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

a(n) = A006129(n) - A367869(n). - Andrew Howroyd, Dec 30 2023

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

A140637 Number of unlabeled graphs of positive excess with n nodes.

Original entry on oeis.org

0, 0, 0, 2, 15, 110, 936, 12073, 273972, 12003332, 1018992968, 165091159269, 50502031331411, 29054155657134165, 31426485969804026075, 64001015704527557101231, 245935864153532932681481794, 1787577725145611700547871854870, 24637809253125004524383007473440146

Offset: 1

Washington Bomfim, May 21 2008

nonn

We can find in "The Birth of the Giant Component" p. 53, see the link, the following: "The excess of a graph or multigraph is the number of edges plus the number of acyclic components, minus the number of vertices."
If G has just one complex component with 4 nodes, the "non-complex part" of G can be,
a) One forest of order 4. There are 6 forests, so 2*6=12 graphs.
b) One triangle and one isolated vertex, or 2*1=2 graphs.
c) One unicyclic graph of order 4, so 2*2=4 graphs.
Also the number of unchoosable unlabeled graphs with up to n vertices, where a graph is choosable iff it is possible to choose a different vertex from each edge. The labeled version is A367867, covering A367868, connected A140638. - Gus Wiseman, Feb 13 2024

			Below we show that a(8) = 12073. Note that A140636(n) is the number of connected graphs of positive excess with n nodes.
Let G be a disconnected graph of positive excess with 8 nodes. In this case, G has one or two complex components. We have 3 graphs of order 8 with two complex components. One of those graphs is depicted in the figure below:
  O---O...O---O
  |\..|...|\./|
  |.\.|...|.X.|
  |..\|...|/.\|
  O---O...O---O
If G has one complex component with 5 nodes, the non-complex part of G can be,
a) One forest of order 3. There are 3 forests, so A140636(5) * 3 = 39 graphs.
b) One triangle, so A140636(5) = 13 graphs.
If G has one complex component with 6 nodes, the non-complex part of G is a forest of order 2. There are 2 forests. We have A140636(6) * 2, or 186 graphs.
If G has one complex component with 7 nodes, the non-complex part of G is one isolated vertex. We have A140636(7), or 809 graphs.
Finally if G is connected, we have A140636(8), or 11005 graphs.
The total is 3 + 12 + 2 + 4 + 39 + 13 + 186 + 809 + 11005 = 12073.

Svante Janson, Donald E. Knuth, Tomasz Łuczak and Boris Pittel, The Birth of the Giant Component.

Cf. A000088, A005195, A001429.
The labeled complement is A133686, covering A367869, connected A129271.
The complement is A134964, connected A005703.
The connected covering case is A140636.
The labeled version is A367867, covering A367868, connected A140638.
Set-systems not of this type are A367902, ranks A367906.
Set-systems of this type are A367903, ranks A367907.
For set-systems we have A368094, complement A368095.
For multiset partitions we have A368097, complement A368098.
Factorizations of this type are A368413, complement A368414.
Cf. A001349, A002494, A006125, A055621, A367769, A367770, A367901.

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],{2}]],Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,5}] (* Gus Wiseman, Feb 14 2024 *)

a(n) = A000088(n) - A134964(n).

A367901 Number of sets of subsets of {1..n} contradicting a strict version of the axiom of choice.

Original entry on oeis.org

1, 2, 9, 195, 63765, 4294780073, 18446744073639513336, 340282366920938463463374607341656713953, 115792089237316195423570985008687907853269984665640564039457583610129753447747

Offset: 0

Gus Wiseman, Dec 05 2023

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(2) = 9 sets of sets:
  {{}}
  {{},{1}}
  {{},{2}}
  {{},{1,2}}
  {{},{1},{2}}
  {{},{1},{1,2}}
  {{},{2},{1,2}}
  {{1},{2},{1,2}}
  {{},{1},{2},{1,2}}

Wikipedia, Axiom of choice.

The version for simple graphs is A367867, covering A367868.
The complement is counted by A367902, no singletons A367770, ranks A367906.
The version without empty edges is A367903, ranks A367907.
For a unique choice (instead of none) we have A367904, ranks A367908.
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.
A326031 gives weight of the set-system with BII-number n.
Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367769, A367862, A367905.

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

a(n) = 2^2^n - A367902(n). - Christian Sievers, Aug 01 2024

a(5)-a(8) from Christian Sievers, Aug 01 2024

A367862 Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.

Original entry on oeis.org

1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416

Offset: 0

Gus Wiseman, Dec 07 2023

nonn

Unlike the connected case (A057500), these graphs may have more than one cycle; for example, the graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}} has multiple cycles.

			Non-isomorphic representatives of the a(4) = 20 graphs:
  {}
  {{1,2},{1,3},{2,3}}
  {{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.
Counting all vertices (not just covered) gives A116508.
The covering case is A367863, unlabeled A006649.
For set-systems we have A367916, ranks A367917.
A001187 counts connected graphs, A001349 unlabeled.
A003465 counts covering set-systems, unlabeled A055621, ranks A326754.
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. A006126, A316983, A321405, A326754, A326870, A326877, A367770, A367901, A367902, A367903.

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

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

Binomial transform of A367863.

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

cp's OEIS Frontend

A133686 Number of labeled n-node graphs with at most one cycle in each connected component.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A367906 Numbers k such that it is possible to choose a different binary index of each binary index of k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments