login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A046165 Number of minimal covers of n objects. 21
1, 1, 2, 8, 49, 462, 6424, 129425, 3731508, 152424420, 8780782707, 710389021036, 80610570275140, 12815915627480695, 2855758994821922882, 892194474524889501292, 391202163933291014701953, 240943718535427829240708786, 208683398342300491409959279244 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
No edge of a minimal cover can be a subset of any other, so minimal covers are antichains, but the converse is not true. - Gus Wiseman, Jul 03 2019
a(n) is the number of undirected graphs on n nodes for which the intersection number and independence number are equal. See Proposition 2.3.7 and Theorem 2.3.3 of the Deligeorgaki et al. paper below. - Alex Markham, Oct 13 2022
LINKS
Damian Bursztyn, François Goasdoué, and Ioana Manolescu, Optimizing Reformulation-based Query Answering in RDF, [Research Report] RR-8646, INRIA Saclay. 2014. <hal-01091214>
D. Deligeorgaki, A. Markham, P. Misra, and L. Solus, Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks, arXiv:2210.00822 [stat.ME], 2022.
Giovanni Resta, Illustration of a(4)=49.
Eric Weisstein's World of Mathematics, Minimal Cover
FORMULA
E.g.f.: Sum_{n>=0} (exp(x)-1)^n*exp(x*(2^n-n-1))/n!. - Vladeta Jovovic, May 08 2004
a(n) = Sum_{k=1..n} Sum_{i=k..n} C(n,i)*Stirling2(i,k)*(2^k - k - 1)^(n - i). - Geoffrey Critzer, Jun 27 2013
a(n) ~ c * 2^(n^2/4 + n + 1/2) / sqrt(Pi*n), where c = JacobiTheta3(0,1/2) = EllipticTheta[3, 0, 1/2] = 2.1289368272118771586694585485449... if n is even, and c = JacobiTheta2(0,1/2) = EllipticTheta[2, 0, 1/2] = 2.1289312505130275585916134025753... if n is odd. - Vaclav Kotesovec, Mar 10 2014
EXAMPLE
From Gus Wiseman, Jul 02 2019: (Start)
The a(1) = 1 through a(3) = 8 minimal covers:
{{1}} {{1,2}} {{1,2,3}}
{{1},{2}} {{1},{2,3}}
{{2},{1,3}}
{{3},{1,2}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1},{2},{3}}
{{1,3},{2,3}}
(End)
MAPLE
a:= n-> add(add((-1)^i* binomial(k, i) *(2^k-1-i)^n, i=0..k)/k!, k=0..n):
seq(a(n), n=0..20); # Alois P. Heinz, Aug 19 2008
MATHEMATICA
Table[Sum[Sum[Binomial[n, i]StirlingS2[i, k](2^k-k-1)^(n-i), {i, k, n}], {k, 2, n}]+1, {n, 1, 20}] (* Geoffrey Critzer, Jun 27 2013 *)
CROSSREFS
Antichain covers are A006126.
Minimal covering simple graphs are A053530.
Maximal antichains are A326358.
Row sums of A035347 or of A282575.
Sequence in context: A058864 A332237 A136226 * A227264 A373865 A114619
KEYWORD
nonn
AUTHOR
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Feb 18 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 23 21:46 EDT 2024. Contains 374575 sequences. (Running on oeis4.)