A319637 -id:A319637 - cp's OEIS frontend

A055621 Number of covers of an unlabeled n-set.

1, 1, 4, 34, 1952, 18664632, 12813206150470528, 33758171486592987151274638874693632, 1435913805026242504952006868879460423801146743462225386100617731367239680

Offset: 0

Vladeta Jovovic, Jun 04 2000

			There are 4 nonisomorphic covers of {1,2}, namely {{1},{2}}, {{1,2}}, {{1},{1,2}} and {{1},{2},{1,2}}.
From _Gus Wiseman_, Aug 14 2019: (Start)
Non-isomorphic representatives of the a(3) = 34 covers:
  {123}  {1}{23}    {1}{2}{3}      {1}{2}{3}{23}
         {13}{23}   {1}{3}{23}     {1}{2}{13}{23}
         {3}{123}   {2}{13}{23}    {1}{2}{3}{123}
         {23}{123}  {2}{3}{123}    {2}{3}{13}{23}
                    {3}{13}{23}    {1}{3}{23}{123}
                    {12}{13}{23}   {2}{3}{23}{123}
                    {1}{23}{123}   {3}{12}{13}{23}
                    {3}{23}{123}   {2}{13}{23}{123}
                    {13}{23}{123}  {3}{13}{23}{123}
                                   {12}{13}{23}{123}
.
  {1}{2}{3}{13}{23}     {1}{2}{3}{12}{13}{23}    {1}{2}{3}{12}{13}{23}{123}
  {1}{2}{3}{23}{123}    {1}{2}{3}{13}{23}{123}
  {2}{3}{12}{13}{23}    {2}{3}{12}{13}{23}{123}
  {1}{2}{13}{23}{123}
  {2}{3}{13}{23}{123}
  {3}{12}{13}{23}{123}
(End)

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 78 (2.3.39)

Alois P. Heinz, Table of n, a(n) for n = 0..12
Heller, Jürgen Identifiability in probabilistic knowledge structures. J. Math. Psychol. 77, 46-57 (2017).
Eric Weisstein's World of Mathematics, Cover

Unlabeled set-systems are A000612 (partial sums).
The version with empty edges allowed is A003181.
The labeled version is A003465.
The T_0 case is A319637.
The connected case is A323819.
The T_1 case is A326974.
Cf. A058891, A319559, A326946, A326973.

b:= proc(n, i, l) `if`(n=0, 2^(w-> add(mul(2^igcd(t, l[h]),
      h=1..nops(l)), t=1..w)/w)(ilcm(l[])), `if`(i<1, 0,
      add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i)))
    end:
a:= n-> `if`(n=0, 2, b(n$2, [])-b(n-1$2, []))/2:
seq(a(n), n=0..8);  # Alois P. Heinz, Aug 14 2019

b[n_, i_, l_] := b[n, i, l] = If[n==0, 2^Function[w, Sum[Product[2^GCD[t, l[[h]]], {h, 1, Length[l]}], {t, 1, w}]/w][If[l=={}, 1, LCM@@l]], If[i<1, 0, Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]]];
a[n_] := If[n==0, 2, b[n, n, {}] - b[n-1, n-1, {}]]/2;
a /@ Range[0, 8] (* Jean-François Alcover, Jan 31 2020, after Alois P. Heinz *)

a(n) = (A003180(n) - A003180(n-1))/2 = A000612(n) - A000612(n-1) for n>0.

Euler transform of A323819. - Gus Wiseman, Aug 14 2019

More terms from David Moews (dmoews(AT)xraysgi.ims.uconn.edu) Jul 04 2002

a(0) = 1 prepended by Gus Wiseman, Aug 14 2019

A059201 Number of T_0-covers of a labeled n-set.

Original entry on oeis.org

1, 1, 4, 96, 31692, 2147001636, 9223371991763269704, 170141183460469231473432887375376674952, 57896044618658097711785492504343953920509909728243389682424010192567186540224

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Jan 16 2001

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.
From Gus Wiseman, Aug 13 2019: (Start)
A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges). For example, the a(2) = 4 covers are:
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}
(End)

G. C. Greubel, Table of n, a(n) for n = 0..11
Vladeta Jovovic, T_0-covers of a labeled 3-set

Row sums of A059202.
Cf. A059203, A059084, A059085, A059086, A059087, A059088, A059089.
Covering set-systems are A003465.
The unlabeled version is A319637.
The version with empty edges allowed is A326939.
The non-covering version is A326940.
BII-numbers of T_0 set-systems are A326947.
The same with connected instead of covering is A326948.
The T_1 version is A326961.
Cf. A245567, A316978, A319559, A319564, A323818, A326941, A326946, A326970.

Table[Sum[StirlingS1[n + 1, k]*2^(2^(k - 1) - 1), {k, 0, n + 1}], {n,0,5}] (* G. C. Greubel, Dec 28 2016 *)
dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],Union@@#==Range[n]&&UnsameQ@@dual[#]&]],{n,0,3}] (* Gus Wiseman, Aug 13 2019 *)

a(n) = Sum_{i=0..n+1} stirling1(n+1, i)*2^(2^(i-1)-1).
a(n) = Sum_{m=0..2^n-1} A059202(n,m).
Inverse binomial transform of A326940 and exponential transform of A326948. - Gus Wiseman, Aug 13 2019

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

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

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

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

A326946 Number of unlabeled T_0 set-systems on n vertices.

Original entry on oeis.org

1, 2, 5, 34, 1919, 18660178

Offset: 0

Gus Wiseman, Aug 08 2019

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

			Non-isomorphic representatives of the a(0) = 1 through a(2) = 5 set-systems:
  {}  {}     {}
      {{1}}  {{1}}
             {{1},{2}}
             {{2},{1,2}}
             {{1},{2},{1,2}}

The non-T_0 version is A000612.
The antichain case is A245567.
The covering case is A319637.
The labeled version is A326940.
The version with empty edges allowed is A326949.
Cf. A003180, A055621, A059052, A059201, A316978, A319559, A319564, A326942.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Union[normclut/@Select[Subsets[Subsets[Range[n],{1,n}]],UnsameQ@@dual[#]&]]],{n,0,3}]

Partial sums of A319637.

a(n) = A326949(n)/2.

a(5) from Max Alekseyev, Oct 11 2023

A326974 Number of unlabeled set-systems covering n vertices where every vertex is the unique common element of some subset of the edges, also called unlabeled covering T_1 set-systems.

Original entry on oeis.org

1, 1, 2, 16, 1212

Offset: 0

Gus Wiseman, Aug 11 2019

Alternatively, these are unlabeled set-systems covering n vertices whose dual is a (strict) antichain. A set-system is a finite set of finite nonempty sets. The dual of a set-system has, for each vertex, one edge consisting of the indices (or positions) of the edges containing that vertex. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. An antichain is a set-system where no edge is a subset of any other.

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 16 set-systems:
  {}  {{1}}  {{1},{2}}        {{1},{2},{3}}
             {{1},{2},{1,2}}  {{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{2,3}}
                              {{1},{2},{1,3},{2,3}}
                              {{1},{2},{3},{1,2,3}}
                              {{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{3},{1,3},{2,3}}
                              {{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3}}
                              {{1},{2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3}}
                              {{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,3},{2,3},{1,2,3}}
                              {{2},{3},{1,2},{1,3},{2,3},{1,2,3}}
                              {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Unlabeled covers are A055621.
The same with T_0 instead of T_1 is A319637.
The labeled version is A326961.
The non-covering version is A326972 (partial sums).
Unlabeled covering set-systems whose dual is a weak antichain are A326973.
Cf. A000612, A059523, A319559, A326946, A326951, A326965, A326970, A326971, A326976, A326977, A326979.

a(n > 0) = A326972(n) - A326972(n - 1).

A326940 Number of T_0 set-systems on n vertices.

Original entry on oeis.org

1, 2, 7, 112, 32105, 2147161102, 9223372004645756887, 170141183460469231537996491362807709908, 57896044618658097711785492504343953921871039195927143534469727707459805807105

Offset: 0

Gus Wiseman, Aug 07 2019

nonn

The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. For example, the dual of {{1,2},{2,3}} is {{1},{1,2},{2}}. The T_0 condition means that the dual is strict (no repeated edges).

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

The non-T_0 version is A058891 shifted to the left.
The covering case is A059201.
The version with empty edges is A326941.
The unlabeled version is A326946.
Cf. A003180, A316978, A319559, A319564, A319637, A326939, A326947, A326949.

dual[eds_]:=Table[First/@Position[eds,x],{x,Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n],{1,n}]],UnsameQ@@dual[#]&]],{n,0,3}]

Binomial transform of A059201.

cp's OEIS Frontend

A055621 Number of covers of an unlabeled n-set.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A059201 Number of T_0-covers of a labeled n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

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

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

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links