|
%I #57 Oct 17 2022 10:44:48
%S 1,1,2,8,49,462,6424,129425,3731508,152424420,8780782707,710389021036,
%T 80610570275140,12815915627480695,2855758994821922882,
%U 892194474524889501292,391202163933291014701953,240943718535427829240708786,208683398342300491409959279244
%N Number of minimal covers of n objects.
%C 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
%C 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
%H Alois P. Heinz, <a href="/A046165/b046165.txt">Table of n, a(n) for n = 0..113</a>
%H Damian Bursztyn, François Goasdoué, and Ioana Manolescu, <a href="https://team.inria.fr/oak/files/2014/10/techReport-28112014.pdf">Optimizing Reformulation-based Query Answering in RDF</a>, [Research Report] RR-8646, INRIA Saclay. 2014. <hal-01091214>
%H D. Deligeorgaki, A. Markham, P. Misra, and L. Solus, <a href="https://arxiv.org/abs/2210.00822">Combinatorial and algebraic perspectives on the marginal independence structure of Bayesian networks</a>, arXiv:2210.00822 [stat.ME], 2022.
%H Giovanni Resta, <a href="/A046165/a046165.png">Illustration of a(4)=49.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalCover.html">Minimal Cover</a>
%F E.g.f.: Sum_{n>=0} (exp(x)-1)^n*exp(x*(2^n-n-1))/n!. - _Vladeta Jovovic_, May 08 2004
%F 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
%F 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
%e From _Gus Wiseman_, Jul 02 2019: (Start)
%e The a(1) = 1 through a(3) = 8 minimal covers:
%e {{1}} {{1,2}} {{1,2,3}}
%e {{1},{2}} {{1},{2,3}}
%e {{2},{1,3}}
%e {{3},{1,2}}
%e {{1,2},{1,3}}
%e {{1,2},{2,3}}
%e {{1},{2},{3}}
%e {{1,3},{2,3}}
%e (End)
%p a:= n-> add(add((-1)^i* binomial(k,i) *(2^k-1-i)^n, i=0..k)/k!, k=0..n):
%p seq(a(n), n=0..20); # _Alois P. Heinz_, Aug 19 2008
%t 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 *)
%Y Cf. A035348, A000371, A003465.
%Y Antichain covers are A006126.
%Y Minimal covering simple graphs are A053530.
%Y Maximal antichains are A326358.
%Y Row sums of A035347 or of A282575.
%Y Cf. A000372, A003182, A006602, A261005, A305844, A307249, A326359.
%K nonn
%O 0,3
%A _Eric W. Weisstein_
%E a(0)=1 prepended by _Alois P. Heinz_, Feb 18 2017
|
