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

REFERENCES

Damian Bursztyn, Fran¸cois Goasdou´e, Ioana Manolescu. Optimizing Reformulation-based Query Answering in RDF. [Research Report] RR-8646, INRIA Saclay. 2014. <hal-01091214>

LINKS

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

Giovanni Resta, Illustration of a(4)=49.

Eric Weisstein's World of Mathematics, Minimal Cover

FORMULA

E.g.f.: Sum((exp(x)-1)^n*exp(x*(2^n-n-1))/n!, n=0..infinity). - 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

Cf. A035348, A000371, A003465.

Antichain covers are A006126.

Minimal covering simple graphs are A053530.

Maximal antichains are A326358.

Row sums of A035347 or of A282575.

Cf. A000372, A003182, A006602, A261005, A305844, A307249, A326359.

Sequence in context: A058864 A332237 A136226 * A227264 A114619 A027047

Adjacent sequences:  A046162 A046163 A046164 * A046166 A046167 A046168

KEYWORD

nonn

AUTHOR

Eric W. Weisstein

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 September 24 23:43 EDT 2022. Contains 356951 sequences. (Running on oeis4.)