A046165 Number of minimal covers of n objects.

1, 1, 2, 8, 49, 462, 6424, 129425, 3731508, 152424420, 8780782707, 710389021036, 80610570275140, 12815915627480695, 2855758994821922882, 892194474524889501292, 391202163933291014701953, 240943718535427829240708786, 208683398342300491409959279244

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

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

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

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