login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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.

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 17:23 EDT 2020. Contains 333116 sequences. (Running on oeis4.)