cp's OEIS Frontend

A046165 Number of minimal covers of n objects.

%I A046165 #58 Feb 16 2025 08:32:39
%S A046165 1,1,2,8,49,462,6424,129425,3731508,152424420,8780782707,710389021036,
%T A046165 80610570275140,12815915627480695,2855758994821922882,
%U A046165 892194474524889501292,391202163933291014701953,240943718535427829240708786,208683398342300491409959279244
%N A046165 Number of minimal covers of n objects.
%C A046165 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 A046165 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 A046165 Alois P. Heinz, <a href="/A046165/b046165.txt">Table of n, a(n) for n = 0..113</a>
%H A046165 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 A046165 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 A046165 Giovanni Resta, <a href="/A046165/a046165.png">Illustration of a(4)=49.</a>
%H A046165 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MinimalCover.html">Minimal Cover</a>
%F A046165 E.g.f.: Sum_{n>=0} (exp(x)-1)^n*exp(x*(2^n-n-1))/n!. - _Vladeta Jovovic_, May 08 2004
%F A046165 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 A046165 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 A046165 From _Gus Wiseman_, Jul 02 2019: (Start)
%e A046165 The a(1) = 1 through a(3) = 8 minimal covers:
%e A046165   {{1}}  {{1,2}}    {{1,2,3}}
%e A046165          {{1},{2}}  {{1},{2,3}}
%e A046165                     {{2},{1,3}}
%e A046165                     {{3},{1,2}}
%e A046165                     {{1,2},{1,3}}
%e A046165                     {{1,2},{2,3}}
%e A046165                     {{1},{2},{3}}
%e A046165                     {{1,3},{2,3}}
%e A046165 (End)
%p A046165 a:= n-> add(add((-1)^i* binomial(k,i) *(2^k-1-i)^n, i=0..k)/k!, k=0..n):
%p A046165 seq(a(n), n=0..20);  # _Alois P. Heinz_, Aug 19 2008
%t A046165 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 A046165 Cf. A035348, A000371, A003465.
%Y A046165 Antichain covers are A006126.
%Y A046165 Minimal covering simple graphs are A053530.
%Y A046165 Maximal antichains are A326358.
%Y A046165 Row sums of A035347 or of A282575.
%Y A046165 Cf. A000372, A003182, A006602, A261005, A305844, A307249, A326359.
%K A046165 nonn
%O A046165 0,3
%A A046165 _Eric W. Weisstein_
%E A046165 a(0)=1 prepended by _Alois P. Heinz_, Feb 18 2017