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

A367907 Numbers n such that it is not possible to choose a different binary index of each binary index of n.

Original entry on oeis.org

7, 15, 23, 25, 27, 29, 30, 31, 39, 42, 43, 45, 46, 47, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 63, 71, 75, 77, 78, 79, 83, 85, 86, 87, 89, 90, 91, 92, 93, 94, 95, 99, 101, 102, 103, 105, 106, 107, 108, 109, 110, 111, 113, 114, 115, 116, 117, 118, 119, 120, 121

Offset: 1

Gus Wiseman, Dec 11 2023

Also BII-numbers of set-systems (sets of nonempty sets) contradicting a strict version of the axiom of choice.
A binary index of n (row n 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 n to be obtained by taking the binary indices of each binary index of n. 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 {{1},{2},{1,2},{1,3}} with BII-number 23 has choices (1,2,1,1), (1,2,1,3), (1,2,2,1), (1,2,2,3), but none of these has all different elements, so 23 is in the sequence.
The terms together with the corresponding set-systems begin:
   7: {{1},{2},{1,2}}
  15: {{1},{2},{1,2},{3}}
  23: {{1},{2},{1,2},{1,3}}
  25: {{1},{3},{1,3}}
  27: {{1},{2},{3},{1,3}}
  29: {{1},{1,2},{3},{1,3}}
  30: {{2},{1,2},{3},{1,3}}
  31: {{1},{2},{1,2},{3},{1,3}}
  39: {{1},{2},{1,2},{2,3}}
  42: {{2},{3},{2,3}}
  43: {{1},{2},{3},{2,3}}
  45: {{1},{1,2},{3},{2,3}}
  46: {{2},{1,2},{3},{2,3}}
  47: {{1},{2},{1,2},{3},{2,3}}
  51: {{1},{2},{1,3},{2,3}}

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

These set-systems are counted by A367903, non-isomorphic A368094.
Positions of zeros in A367905, firsts A367910, sorted A367911.
The complement is A367906.
If there is one unique choice we get A367908, counted by A367904.
If there are multiple choices we get A367909, counted by A367772.
A048793 lists binary indices, length A000120, reverse A272020, sum A029931.
A058891 counts set-systems, covering A003465, connected A323818.
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, A072639, A083323, A309326, A326702, A326753, A367769, A367901, A367902, 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):
        p = list(product(*[bin_i(k) for k in bin_i(n)]))
        x = len(p)
        for j in range(x):
            if len(set(p[j])) == len(p[j]): break
            if j+1 == x: yield(n)
A367907_list = list(islice(a_gen(), 100)) # John Tyler Rascoe, Feb 10 2024

A367907 U A367908 U A367909 = A000027.

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

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

A368413 Number of factorizations of n into positive integers > 1 such that it is not possible to choose a different prime factor of each factor.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 1, 0, 0, 0, 3, 1, 0, 2, 1, 0, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0, 3, 0, 0, 0, 1, 1, 0, 0, 7, 1, 1, 0, 1, 0, 3, 0, 3, 0, 0, 0, 2, 0, 0, 1, 10, 0, 0, 0, 1, 0, 0, 0, 10, 0, 0, 1, 1, 0, 0, 0, 7, 4, 0, 0, 2, 0, 0

Offset: 1

Gus Wiseman, Dec 27 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is counted under a(36).

			The a(1) = 0 through a(24) = 3 factorizations:
 ... 2*2 ... 2*4   3*3 .. 2*2*3 ... 2*8     . 2*3*3 . 2*2*5 ... 2*2*6
             2*2*2                  4*4                         2*3*4
                                    2*2*4                       2*2*2*3
                                    2*2*2*2

For unlabeled graphs: A140637, complement A134964.
For labeled graphs: A367867, A367868, A140638, complement A133686.
For set-systems: A367903, ranks A367907, complement A367902, ranks A367906.
For non-isomorphic set-systems: A368094, A368409, complement A368095.
For non-isomorphic multiset partitions: A368097, A355529, A368411.
Complement for non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368414.
For non-isomorphic set multipartitions: A368421, complement A368422.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A340596, A340653, A367769, A367901, A368187, A368412.

facs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&, Select[facs[n/d],Min@@#>=d&]],{d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]=={}&]],{n,100}]

a(n) + A368414(n) = A001055(n).

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

A368414 Number of factorizations of n into positive integers > 1 such that it is possible to choose a different prime factor of each factor.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 1, 2, 2, 2, 5, 1, 2, 2, 4, 1, 5, 1, 3, 3, 2, 1, 5, 1, 3, 2, 3, 1, 4, 2, 4, 2, 2, 1, 9, 1, 2, 3, 1, 2, 5, 1, 3, 2, 5, 1, 6, 1, 2, 3, 3, 2, 5, 1, 5, 1, 2, 1, 9, 2, 2, 2

Offset: 1

Gus Wiseman, Dec 29 2023

nonn

For example, the factorization f = 2*3*6 has two ways to choose a prime factor of each factor, namely (2,3,2) and (2,3,3), but neither of these has all different elements, so f is not counted under a(36).

			The a(n) factorizations for selected n:
  1    6      12     24      30       60        72      120
       2*3    2*6    2*12    2*15     2*30      2*36    2*60
              3*4    3*8     3*10     3*20      3*24    3*40
                     4*6     5*6      4*15      4*18    4*30
                             2*3*5    5*12      6*12    5*24
                                      6*10      8*9     6*20
                                      2*3*10            8*15
                                      2*5*6             10*12
                                      3*4*5             2*3*20
                                                        2*5*12
                                                        2*6*10
                                                        3*4*10
                                                        3*5*8
                                                        4*5*6

For labeled graphs: A133686, complement A367867, A367868, A140638.
For unlabeled graphs: A134964, complement A140637.
For set-systems: A367902, ranks A367906, complement A367903, ranks A367907.
For non-isomorphic set-systems: A368095, complement A368094, A368409.
Complementary non-isomorphic multiset partitions: A368097, A355529, A368411.
For non-isomorphic multiset partitions: A368098, A368100.
The complement is counted by A368413.
For non-isomorphic set multipartitions: A368422, complement A368421.
For divisors instead of prime factors: A370813, complement A370814.
A001055 counts factorizations, strict A045778.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A058891 counts set-systems, unlabeled A000612, connected A323818.
A283877 counts non-isomorphic set-systems, connected A300913.
Cf. A340596, A340653, A367769, A367901, A368187, A368412, A368413.

facs[n_]:=If[n<=1,{{}},Join @@ Table[Map[Prepend[#,d]&,Select[facs[n/d],Min@@#>=d&]], {d,Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], Select[Tuples[First/@FactorInteger[#]&/@#], UnsameQ@@#&]!={}&]],{n,100}]

a(n) = A001055(n) - A368413(n).

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

A367907 Numbers n such that it is not possible to choose a different binary index of each binary index of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

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

Views

Author

Keywords

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