Displaying 1-10 of 28 results found.
Number of covers of an unlabeled n-set.
+10
108
1, 1, 4, 34, 1952, 18664632, 12813206150470528, 33758171486592987151274638874693632, 1435913805026242504952006868879460423801146743462225386100617731367239680
REFERENCES
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 78 (2.3.39)
LINKS
Eric Weisstein's World of Mathematics, Cover
EXAMPLE
There are 4 nonisomorphic covers of {1,2}, namely {{1},{2}}, {{1,2}}, {{1},{1,2}} and {{1},{2},{1,2}}.
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)
MAPLE
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:
MATHEMATICA
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;
CROSSREFS
Unlabeled set-systems are A000612 (partial sums). The version with empty edges allowed is A003181.
EXTENSIONS
More terms from David Moews (dmoews(AT)xraysgi.ims.uconn.edu) Jul 04 2002
Number of T_0-covers of a labeled n-set.
+10
89
1, 1, 4, 96, 31692, 2147001636, 9223371991763269704, 170141183460469231473432887375376674952, 57896044618658097711785492504343953920509909728243389682424010192567186540224
COMMENTS
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.
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)
FORMULA
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).
MATHEMATICA
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 *)
CROSSREFS
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.
Number of labeled simple graphs with n vertices contradicting a strict version of the axiom of choice.
+10
61
0, 0, 0, 0, 7, 416, 24244, 1951352, 265517333, 68652859502, 35182667175398, 36028748718835272, 73786974794973865449, 302231454853009287213496, 2475880078568912926825399800, 40564819207303268441662426947840, 1329227995784915869870199216532048487
COMMENTS
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.
EXAMPLE
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}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]
CROSSREFS
The connected case is A140638 (graphs with more than one cycle). A143543 counts simple labeled graphs by number of connected components.
Cf. A057500, A116508, A326754, A355739, A355740, A367769, A367770, A367863, A367901, A367902, A367904.
Number of n-vertex labeled simple graphs with n edges and no isolated vertices.
+10
52
1, 0, 0, 1, 15, 222, 3760, 73755, 1657845, 42143500, 1197163134, 37613828070, 1295741321875, 48577055308320, 1969293264235635, 85852853154670693, 4005625283891276535, 199166987259400191480, 10513996906985414443720, 587316057411626070658200, 34612299496604684775762261
FORMULA
a(n) = Sum_{k=0..n} (-1)^(n-k) * binomial(n,k) * binomial(binomial(k,2), n). - Andrew Howroyd, Dec 29 2023
EXAMPLE
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}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Length[#]==n&]], {n, 0, 5}]
PROG
(PARI) a(n) = sum(k=0, n, (-1)^(n-k) * binomial(n, k) * binomial(binomial(k, 2), n)) \\ Andrew Howroyd, Dec 29 2023
CROSSREFS
The non-covering version is A116508. A143543 counts simple labeled graphs by number of connected components.
Cf. A003465, A006126, A305000, A316983, A319559, A323817, A326754, A367769, A367901, A367902, A367903.
Number of labeled simple graphs covering n vertices and satisfying a strict version of the axiom of choice.
+10
42
1, 0, 1, 4, 34, 387, 5596, 97149, 1959938, 44956945, 1154208544, 32772977715, 1019467710328, 34473686833527, 1259038828370402, 49388615245426933, 2070991708598960524, 92445181295983865757, 4376733266230674345874, 219058079619119072854095, 11556990682657196214302036
COMMENTS
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
EXAMPLE
The a(3) = 4 graphs:
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,3},{2,3}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]!={}&]], {n, 0, 5}]
PROG
(PARI) 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
CROSSREFS
A143543 counts simple labeled graphs by number of connected components.
Number of labeled simple graphs covering n vertices and contradicting a strict version of the axiom of choice.
+10
40
0, 0, 0, 0, 7, 381, 21853, 1790135, 250562543, 66331467215, 34507857686001, 35645472109753873, 73356936892660012513, 301275024409580265134121, 2471655539736293803311467943, 40527712706903494712385171632959, 1328579255614092966328511889576785109
COMMENTS
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.
EXAMPLE
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}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Union@@#==Range[n]&&Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 5}]
CROSSREFS
A143543 counts simple labeled graphs by number of connected components.
Number of n-vertex labeled simple graphs with the same number of edges as covered vertices.
+10
33
1, 1, 1, 2, 20, 308, 5338, 105298, 2366704, 60065072, 1702900574, 53400243419, 1836274300504, 68730359299960, 2782263907231153, 121137565273808792, 5645321914669112342, 280401845830658755142, 14788386825536445299398, 825378055206721558026931, 48604149005046792753887416
COMMENTS
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.
EXAMPLE
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}}
MATHEMATICA
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[#]==Length[Union@@#]&]], {n, 0, 5}]
PROG
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
CROSSREFS
Counting all vertices (not just covered) gives A116508. A143543 counts simple labeled graphs by number of connected components.
Number of unlabeled T_0 set-systems on n vertices.
+10
17
1, 2, 5, 34, 1919, 18660178
COMMENTS
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).
EXAMPLE
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}}
MATHEMATICA
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}]
CROSSREFS
The version with empty edges allowed is A326949.
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.
+10
17
COMMENTS
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.
EXAMPLE
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}}
CROSSREFS
The same with T_0 instead of T_1 is A319637. 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.
Number of T_0 set-systems on n vertices.
+10
16
1, 2, 7, 112, 32105, 2147161102, 9223372004645756887, 170141183460469231537996491362807709908, 57896044618658097711785492504343953921871039195927143534469727707459805807105
COMMENTS
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).
EXAMPLE
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}}
MATHEMATICA
dual[eds_]:=Table[First/@Position[eds, x], {x, Union@@eds}];
Table[Length[Select[Subsets[Subsets[Range[n], {1, n}]], UnsameQ@@dual[#]&]], {n, 0, 3}]
CROSSREFS
The non-T_0 version is A058891 shifted to the left. The version with empty edges is A326941.
Search completed in 0.020 seconds
|