A129271 -id:A129271 - cp's OEIS frontend

A369193 Number of labeled simple graphs with n vertices and at most as many edges as covered (non-isolated) vertices.

1, 1, 2, 8, 57, 608, 8614, 151365, 3162353, 76359554, 2088663444, 63760182536, 2147325661180, 79051734050283, 3157246719905273, 135938652662043977, 6275929675565965599, 309242148569525451140, 16197470691388774460758, 898619766673014862321176, 52639402023471657682257626

Offset: 0

Gus Wiseman, Jan 17 2024

nonn

			The a(0) = 1 through a(3) = 8 graphs:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}

The case of equality is A367862, covering case of A116508, also A367863.
The covering case is A369191, for loop-graphs A369194.
The version counting all vertices is A369192.
The version for loop-graphs is A369196, counting all vertices A066383.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A133686 counts choosable graphs, covering A367869.
A367867 counts non-choosable graphs, covering A367868.
Cf. A000169, A000272, A000666, A001187, A006649, A053530, A129271, A143543, A322661, A367916.

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

Binomial transform of A369191.

A368412 Number of non-isomorphic connected multiset partitions of weight n satisfying a strict version of the axiom of choice.

Original entry on oeis.org

0, 1, 2, 4, 11, 25, 75, 206, 650, 2049, 6895

Offset: 0

Gus Wiseman, Dec 26 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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.

			Non-isomorphic representatives of the a(1) = 1 through a(4) = 11 multiset partitions:
  {{1}}  {{1,1}}  {{1,1,1}}    {{1,1,1,1}}
         {{1,2}}  {{1,2,2}}    {{1,1,2,2}}
                  {{1,2,3}}    {{1,2,2,2}}
                  {{2},{1,2}}  {{1,2,3,3}}
                               {{1,2,3,4}}
                               {{1},{1,2,2}}
                               {{1,2},{1,2}}
                               {{1,2},{2,2}}
                               {{1,3},{2,3}}
                               {{2},{1,2,2}}
                               {{3},{1,2,3}}

Wikipedia, Axiom of choice.

The case of labeled graphs is A129271, connected case of A133686.
The complement for labeled graphs is A140638, connected case of A367867.
This is the connected case of A368098, ranks A368100.
Complement set-systems: A368409, connected case of A368094, ranks A367907.
For set-systems we have A368410, connected case of A368095, ranks A367906.
The complement is A368411, connected case of A368097, ranks A355529.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
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. A140637, A302545, A316983, A317533, A319616, A367902, A367905, A368187.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]], {s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}],Length[Intersection@@s[[#]]]>0&]}, If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute /@ Select[mpm[n],Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]!={}&]]],{n,0,6}]

A369144 Number of labeled simple graphs with n edges covering 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, 0, 0, 0, 0, 90, 4935, 200970, 7636860, 291089610, 11459170800, 471932476290, 20447369179380, 933942958593645, 44981469288560805, 2282792616992648670, 121924195590795244920, 6843305987751060036720, 403003907531795513467260, 24861219342100679072572470

Offset: 0

Gus Wiseman, Jan 21 2024

nonn

			The term a(6) = 90 counts all permutations of the (non-connected) graph {{1,2},{1,3},{1,4},{2,3},{2,4},{5,6}}.

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

The covering complement is counted by A137916.
Without the choice condition we have A367863, covering case of A116508.
Allowing any number of edges gives A367868, covering case of A367867.
With loops we have A368730, covering case of A368596, unlabeled A368835.
This is the covering case of A369143.
A003465 counts covering set-systems, unlabeled A055621.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A058891 counts set-systems, unlabeled A000612.
A322661 counts covering loop-graphs, connected A062740.
Cf. A000085, A057500, A129271, A133686, A333331, A367869, A367901, A367903, A367907, A368600.

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

a(n) = A367863(n) - A137916(n). - Andrew Howroyd, Feb 02 2024

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

A368411 Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.

Original entry on oeis.org

0, 0, 1, 2, 6, 15, 50, 148, 509, 1725, 6218

Offset: 0

Gus Wiseman, Dec 26 2023

A set-system is a finite set of finite nonempty sets. The weight of a set-system is the sum of cardinalities of its elements. Weight is generally not the same as number of vertices.

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.

			Non-isomorphic representatives of the a(2) = 1 through a(5) = 15 multiset partitions:
  {{1},{1}}  {{1},{1,1}}    {{1},{1,1,1}}      {{1},{1,1,1,1}}
             {{1},{1},{1}}  {{1,1},{1,1}}      {{1,1},{1,1,1}}
                            {{1},{1},{1,1}}    {{1},{1},{1,1,1}}
                            {{1},{2},{1,2}}    {{1},{1,1},{1,1}}
                            {{2},{2},{1,2}}    {{1},{1},{1,2,2}}
                            {{1},{1},{1},{1}}  {{1},{1,2},{2,2}}
                                               {{1},{2},{1,2,2}}
                                               {{2},{1,2},{1,2}}
                                               {{2},{1,2},{2,2}}
                                               {{2},{2},{1,2,2}}
                                               {{3},{3},{1,2,3}}
                                               {{1},{1},{1},{1,1}}
                                               {{1},{2},{2},{1,2}}
                                               {{2},{2},{2},{1,2}}
                                               {{1},{1},{1},{1},{1}}

Wikipedia, Axiom of choice.

The case of labeled graphs is A140638, connected case of A367867.
The complement for labeled graphs is A129271, connected case of A133686.
This is the connected case of A368097.
For set-systems we have A368409, connected case of A368094, ranks A367907.
Complement set-systems: A368410, connected case of A368095, ranks A367906.
The complement is A368412, connected case of A368098, ranks A368100.
A000110 counts set partitions, non-isomorphic A000041.
A003465 counts covering set-systems, unlabeled A055621.
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. A140637, A302545, A316983, A317533, A319616, A367903, A367905, A368187.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mpm[n_]:=Join@@Table[Union[Sort[Sort /@ (#/.x_Integer:>s[[x]])]&/@sps[Range[n]]],{s,Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n]}];
brute[m_]:=First[Sort[Table[Sort[Sort /@ (m/.Rule@@@Table[{i,p[[i]]},{i,Length[p]}])], {p,Permutations[Union@@m]}]]];
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}],Length[Intersection@@s[[#]]]>0&]}, If[c=={},s,csm[Sort[Append[Delete[s,List /@ c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Union[brute /@ Select[mpm[n],Length[csm[#]]==1&&Select[Tuples[#], UnsameQ@@#&]=={}&]]],{n,0,6}]

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Original entry on oeis.org

1, 1, 3, 7, 18, 43, 112, 282, 740, 1940, 5182, 13916, 37826, 103391, 284815, 788636, 2195414, 6137025, 17223354, 48495640, 136961527, 387819558, 1100757411, 3130895452, 8922294498, 25470279123, 72823983735, 208515456498, 597824919725, 1716072103910, 4931540188084

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are covering loop-graphs with at most one cycle (unicyclic) in each connected component.

			Representatives of the a(1) = 1 through a(4) = 18 loop-graphs (loops shown as singletons):
  {{1}}  {{1,2}}      {{1},{2,3}}          {{1,2},{3,4}}
         {{1},{2}}    {{1,2},{1,3}}        {{1},{2},{3,4}}
         {{1},{1,2}}  {{1},{2},{3}}        {{1},{1,2},{3,4}}
                      {{1},{2},{1,3}}      {{1},{2,3},{2,4}}
                      {{1},{1,2},{1,3}}    {{1},{2},{3},{4}}
                      {{1},{1,2},{2,3}}    {{1,2},{1,3},{1,4}}
                      {{1,2},{1,3},{2,3}}  {{1,2},{1,3},{2,4}}
                                           {{1},{2},{3},{1,4}}
                                           {{1},{2},{1,3},{1,4}}
                                           {{1},{2},{1,3},{2,4}}
                                           {{1},{2},{1,3},{3,4}}
                                           {{1},{1,2},{1,3},{1,4}}
                                           {{1},{1,2},{1,3},{2,4}}
                                           {{1},{1,2},{2,3},{2,4}}
                                           {{1},{1,2},{2,3},{3,4}}
                                           {{1},{2,3},{2,4},{3,4}}
                                           {{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..500

Without the choice condition we have A322700, labeled A322661.
Without loops we have A368834, covering case of A134964.
For exactly n edges we have A368984, labeled A333331 (maybe).
The labeled version is A369140, covering case of A368927.
The labeled complement is A369142, covering case of A369141.
This is the covering case of A369145.
The complement is counted by A369147, covering case of A369146.
The complement without loops is A369202, covering case of A140637.
A000085, A100861, A111924 count set partitions into singletons or pairs.
A000666 counts unlabeled loop-graphs, labeled A006125 (shifted left).
A006129 counts covering graphs, unlabeled A002494.
A007716 counts non-isomorphic multiset partitions, connected A007718.
A129271 counts connected choosable simple graphs, unlabeled A005703.
A133686 counts choosable labeled graphs, covering A367869.
Cf. A000088, A000612, A006649, A014068, A055621, A137916, A137917, A368835, A369194, 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}]], Union@@#==Range[n]&&Length[Select[Tuples[#], UnsameQ@@#&]]!=0&]]],{n,0,4}]

First differences of A369145.

Euler transform of A369289 with A369289(1) = 1. - Andrew Howroyd, Feb 02 2024

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

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

Original entry on oeis.org

1, 0, 0, 1, 15, 252, 4905, 110715, 2864148, 83838720, 2744568522, 99463408335, 3955626143040, 171344363805582, 8031863998136355, 405150528051451000, 21884686370917378050, 1260420510502767861840, 77105349570138633021624, 4993117552678619556356085

Offset: 0

Gus Wiseman, Feb 17 2024

nonn

			The a(0) = 0 through a(4) = 15 graphs:
  {}  .  .  {{1,2},{1,3},{2,3}}  {{1,2},{1,3},{1,4},{2,3}}
                                 {{1,2},{1,3},{1,4},{2,4}}
                                 {{1,2},{1,3},{1,4},{3,4}}
                                 {{1,2},{1,3},{2,3},{2,4}}
                                 {{1,2},{1,3},{2,3},{3,4}}
                                 {{1,2},{1,3},{2,4},{3,4}}
                                 {{1,2},{1,4},{2,3},{2,4}}
                                 {{1,2},{1,4},{2,3},{3,4}}
                                 {{1,2},{1,4},{2,4},{3,4}}
                                 {{1,2},{2,3},{2,4},{3,4}}
                                 {{1,3},{1,4},{2,3},{2,4}}
                                 {{1,3},{1,4},{2,3},{3,4}}
                                 {{1,3},{1,4},{2,4},{3,4}}
                                 {{1,3},{2,3},{2,4},{3,4}}
                                 {{1,4},{2,3},{2,4},{3,4}}

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

The covering case is A057500.
This is the connected case of A116508.
Allowing any number of edges gives A287689.
Counting only covered vertices gives A370318.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, connected A001187.
A369192 counts graphs with at most n edges, covering A369191.
Cf. A000169, A001862, A054780, A062740, A129271, A367863, A369193, A369197.

csm[s_]:=With[{c=Select[Subsets[Range[Length[s]], {2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s, csm[Sort[Append[Delete[s,List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]],Length[#]==n&&Length[csm[#]]<=1&]], {n,0,5}]

a(n)=n!*polcoef(polcoef(exp(x + O(x*x^n))*(1 + log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k,2)*x^k/k!, O(x*x^n)))), n), n) \\ Andrew Howroyd, Feb 19 2024

a(n) = n!*[x^n][y^n] exp(x)*(1 + log(Sum_{k>=0} (1 + y)^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Feb 19 2024

a(8) onwards from Andrew Howroyd, Feb 19 2024

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 7, 30, 124, 507, 2036, 8216, 33515, 138557, 583040, 2503093, 10985364, 49361893, 227342301, 1073896332, 5204340846, 25874724616, 131937166616, 689653979583, 3693193801069, 20247844510508, 113564665880028, 651138092719098, 3813739129140469

Offset: 0

Gus Wiseman, Jan 22 2024

nonn

These are graphs with n vertices and n edges having at least two cycles in the same component.

			The a(0) = 0 through a(6) = 7 simple graphs:
  .  .  .  .  .  {{12}{13}{14}{23}{24}}  {{12}{13}{14}{15}{23}{24}}
                                         {{12}{13}{14}{15}{23}{45}}
                                         {{12}{13}{14}{23}{24}{34}}
                                         {{12}{13}{14}{23}{24}{35}}
                                         {{12}{13}{14}{23}{24}{56}}
                                         {{12}{13}{14}{23}{25}{45}}
                                         {{12}{13}{14}{25}{35}{45}}

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(6) = 7 unlabeled non-choosable graphs with 6 vertices and 6 edges.

Without the choice condition we have A001434, covering A006649.
The labeled version without choice is A116508, covering A367863, A367862.
The complement is counted by A137917, labeled A137916.
For any number of edges we have A140637, complement A134964.
For labeled set-systems we have A368600.
The case with loops is A368835, labeled A368596.
The labeled version is A369143, covering A369144.
A006129 counts covering graphs, unlabeled A002494.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A129271 counts connected choosable simple graphs, unlabeled A005703.
Cf. A000088, A000612, A014068, A053530, A133686, A140638, A368601, A369141, A369146.

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}],{n}],Select[Tuples[#],UnsameQ@@#&]=={}&]]],{n,0,5}]

a(n) = A001434(n) - A137917(n).

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

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

Original entry on oeis.org

1, 0, 1, 2, 5, 10, 28, 68, 193, 534, 1568, 4635, 14146, 43610, 137015, 435227, 1400058, 4547768, 14917504, 49348612, 164596939, 553177992, 1872805144, 6385039022, 21917878860, 75739158828, 263438869515, 922219844982, 3249042441125, 11519128834499, 41097058489426

Offset: 0

Gus Wiseman, Feb 18 2024

nonn

			The a(0) = 1 through a(5) = 10 simple graphs:
  {}  .  {12}  {12-13}     {12-34}        {12-13-45}
               {12-13-23}  {12-13-14}     {12-13-14-15}
                           {12-13-24}     {12-13-14-25}
                           {12-13-14-23}  {12-13-23-45}
                           {12-13-24-34}  {12-13-24-35}
                                          {12-13-14-15-23}
                                          {12-13-14-23-25}
                                          {12-13-14-23-45}
                                          {12-13-14-25-35}
                                          {12-13-24-35-45}

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

The connected case is A005703, labeled A129271.
The case of exactly n edges is A006649, covering case of A001434.
The labeled version is A369191.
Partial row sums of A370167, covering case of A008406.
The non-covering version with loops is A370168, labeled A066383.
The version with loops is A370169, labeled A369194.
The non-covering version is A370315, labeled A369192.
A006125 counts graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
A322661 counts covering loop-graphs, unlabeled A322700.
Cf. A054548, A062734, A116508, A367862, A367863, A368599, A369193.

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}],{0,n}], Union@@#==Range[n]&]]],{n,0,5}]

\\ G defined in A008406.
a(n)=my(A=O(x*x^n)); if(n==0, 1, polcoef((G(n,A)-G(n-1,A))/(1-x), n)) \\ Andrew Howroyd, Feb 19 2024

a(8) onwards from Andrew Howroyd, Feb 19 2024

A144228 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph has at most one cycle.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 15, 1, 10, 45, 120, 210, 222, 1, 15, 105, 455, 1365, 2913, 3670, 1, 21, 210, 1330, 5985, 20139, 49294, 68820, 1, 28, 378, 3276, 20475, 97860, 362670, 976560, 1456875, 1, 36, 630, 7140, 58905, 376236, 1914276, 7663500, 22089870, 34506640

Offset: 0

Alois P. Heinz, Sep 15 2008

			T(4,4) = 15, because there are 15 simple graphs on 4 labeled nodes with 4 edges where each maximally connected subgraph has at most one cycle:
  1-2  1-2  1-2  1-2  1-2  1-2  1 2  1 2  1-2  1 2  1 2  1-2  1-2  1-2  1 2
  |/|  |X   |/   |\|   X|   \|  |/|   X|   /|  |\|  |X   |\   | |   X   |X|
  4 3  4 3  4-3  4 3  4 3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4-3  4 3
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,  15;
  1, 10, 45, 120, 210, 222;
  ...

Alois P. Heinz, Table of n, a(n) for n = 0..140, flattened

Columns k=0-3 give: A000012, A000217, A050534, A093566.
Main diagonal gives A137916.
Row sums give: A133686.
T(2n,n) gives A369828.
Cf. A000272, A057500, A007318, A000142, A129271.

cy:= proc(n) option remember; local t; 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; local j; if k=0 then 1 elif k<0 or n

t[, 0] = 1; t[n, k_] /; (k<0 || nJean-François Alcover, Jan 15 2014, after Maple *)

T(n,0) = 1, T(n,k) = 0 if k<0 or nA000272(j+1) T(n-j-1,k-j) + A057500(j+1) T(n-j-1,k-j-1)).

E.g.f.: exp(B(x,y)), where B(x,y) = Sum(Sum(A062734(n,k)*y^k*x^n/n!, k=0..n), n=1..infinity) = -1/2*log(1+LambertW(-x*y))+1/2*LambertW(-x*y) -1/4*LambertW(-x*y)^2-1/y *(LambertW(-x*y)+1/2 *LambertW(-x*y)^2). - Vladeta Jovovic, Sep 16 2008

A369202 Number of unlabeled simple graphs covering 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, 0, 0, 2, 13, 95, 826, 11137, 261899, 11729360, 1006989636, 164072166301, 50336940172142, 29003653625802754, 31397431814146891910, 63969589218557753075156, 245871863137828405124380563, 1787331789281458167615190373076, 24636021675399858912682459601585276

Offset: 0

Gus Wiseman, Jan 23 2024

nonn

These are simple graphs covering n vertices such that some connected component has at least two cycles.

			Representatives of the a(4) = 2 and a(5) = 13 simple graphs:
  {12}{13}{14}{23}{24}      {12}{13}{14}{15}{23}{24}
  {12}{13}{14}{23}{24}{34}  {12}{13}{14}{15}{23}{45}
                            {12}{13}{14}{23}{24}{35}
                            {12}{13}{14}{23}{25}{45}
                            {12}{13}{14}{25}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}
                            {12}{13}{14}{15}{23}{24}{34}
                            {12}{13}{14}{15}{23}{24}{35}
                            {12}{13}{14}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}
                            {12}{13}{14}{15}{23}{24}{35}{45}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}
                            {12}{13}{14}{15}{23}{24}{25}{34}{35}{45}

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

Without the choice condition we have A002494, labeled A006129.
The connected case is A140636.
This is the covering case of A140637, complement A134964.
The labeled version is A367868, complement A367869.
The complement is counted by A368834.
The version with loops is A369147, complement A369200.
A005703 counts unlabeled connected choosable simple graphs, labeled A129271.
A007716 counts unlabeled multiset partitions, connected A007718.
A054548 counts graphs covering n vertices with k edges, with loops A369199.
A283877 counts unlabeled set-systems, connected A300913.
Cf. A000088, A000612, A006649, A001434, A055621, A137916, A137917, A140638, A368596, A369141, A369146.

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}]],Union@@#==Range[n] && Length[Select[Tuples[#],UnsameQ@@#&]]==0&]]],{n,0,5}]

First differences of A140637.

a(n) = A002494(n) - A368834(n).

cp's OEIS Frontend

A369193 Number of labeled simple graphs with n vertices and at most as many edges as covered (non-isolated) vertices.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A368412 Number of non-isomorphic connected multiset partitions of weight n satisfying a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A369144 Number of labeled simple graphs with n edges covering n vertices such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A368411 Number of non-isomorphic connected multiset partitions of weight n contradicting a strict version of the axiom of choice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A369200 Number of unlabeled loop-graphs covering n vertices such that it is possible to choose a different vertex from each edge (choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370317 Number of labeled graphs with n vertices (allowing isolated vertices) and n edges, such that the edge set is connected.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A369201 Number of unlabeled simple graphs with n vertices and n edges such that it is not possible to choose a different vertex from each edge (non-choosable).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A370316 Number of unlabeled simple graphs covering n vertices with at most n edges.

Views

Author