A035347 -id:A035347 - cp's OEIS frontend

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

Eric W. Weisstein

nonn

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

			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)

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

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.

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

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 *)

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

a(0)=1 prepended by Alois P. Heinz, Feb 18 2017

A056885 Triangle T(n,k) = number of minimal covers of an unlabeled n-set that cover k points of that set uniquely, k=0..n.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 0, 0, 1, 3, 0, 0, 1, 3, 5, 0, 0, 1, 5, 8, 7, 0, 0, 1, 8, 19, 17, 11, 0, 0, 1, 12, 45, 56, 35, 15, 0, 0, 1, 17, 107, 194, 151, 65, 22, 0, 0, 1, 24, 244, 713, 728, 365, 118, 30, 0, 0, 1, 32, 547, 2697, 3996, 2413, 835, 203, 42, 0, 0, 1, 42, 1173, 10356, 24446

Offset: 0

Vladeta Jovovic, Sep 04 2000

Row sums give A048194.

			[1], [0,1], [0,0,2], [0,0,1,3], [0,0,1,3,5], [0,0,1,5,8,7], ...; There are 21=1+5+8+7 minimal covers of an unlabeled 5-set.

Sean A. Irvine, Java program (github)
V. Jovovic, Formula for T(n,k).

Cf. A035347 for labeled case.

A057963 Triangle T(n,k) of number of minimal 2-covers of a labeled n-set that cover k points of that set uniquely (k=2,..,n).

Original entry on oeis.org

1, 3, 3, 6, 12, 7, 10, 30, 35, 15, 15, 60, 105, 90, 31, 21, 105, 245, 315, 217, 63, 28, 168, 490, 840, 868, 504, 127, 36, 252, 882, 1890, 2604, 2268, 1143, 255, 45, 360, 1470, 3780, 6510, 7560, 5715, 2550, 511, 55, 495, 2310, 6930, 14322, 20790, 20955, 14025

Offset: 2

Vladeta Jovovic, Oct 17 2000

Row sums give A000392.

			There are 90=10+30+35+15 minimal 2-covers of a labeled 5-set.
Triangle starts:
1;
3, 3;
6, 12, 7;
10, 30, 35, 15;
15, 60, 105, 90, 31;
...

Robert Israel, Table of n, a(n) for n = 2..10012 (rows 2 to 142, flattened)
Octavio A. Agustín-Aquino, Archimedes' quadrature of the parabola and minimal covers, arXiv:1602.05279 [math.CO], 2016.
Eric Weisstein's World of Mathematics, Minimal cover

Cf. A022166, A035347, A057669, A057964, A057965, A057966, A057967, A057968.

/* As triangle: */ [[Binomial(n, k)*(2^(k-1)-1): k in [2..n]]: n in [1.. 15]]; // Vincenzo Librandi, Feb 19 2016

seq(seq(binomial(n,k)*(2^(k-1)-1),k=2..n), n=2..13); # Robert Israel, Feb 18 2016

Table[ Binomial[n, k] (2^(k-1)-1), {n, 2, 13}, {k, 2, n}] // Flatten (* Jean-François Alcover, Sep 18 2018, from Maple *)

T(n,k) = m=2; binomial(n, k)*stirling(k, m, 2)*(2^m-m-1)^(n-k); \\ Michel Marcus, Feb 18 2016

Number of minimal m-covers of a labeled n-set that cover k points of that set uniquely is C(n, k)*S(k, m)*(2^m-m-1)^(n-k), where S(k, m) are Stirling numbers of the second kind. Here m=2.
From Robert Israel, Feb 18 2016: (Start)
T(n,k) = C(n,k) * (2^(k-1)-1).
G.f. of triangle: x^2*y^2/((1-x)*(1-x-x*y)*(1-x-2*x*y)). (End)

A057965 Triangle T(n,k) of number of minimal 4-covers of a labeled n-set that cover k points of that set uniquely (k=4,..,n).

Original entry on oeis.org

1, 55, 10, 1815, 660, 65, 46585, 25410, 5005, 350, 1024870, 745360, 220220, 30800, 1701, 20292426, 18447660, 7267260, 1524600, 168399, 7770, 372027810, 405848520, 199849650, 55902000, 9261945, 854700, 34105, 6430766430

Offset: 4

Vladeta Jovovic, Oct 17 2000

Row sums give A016111.

			[1], [55, 10], [1815, 660, 65], [46585, 25410, 5005, 350], ...; there are 1815 minimal 4-covers of a labeled 6-set that cover 4 points of that set uniquely.

Eric Weisstein's World of Mathematics, Minimal cover

Cf. A035347, A057669, A057963, A057964, A057966, A057967(unlabeled case), A057968.

Number of minimal m-covers of a labeled n-set that cover k points of that set uniquely is C(n, k)*S(k, m)*(2^m-m-1)^(n-k), where S(k, m) are Stirling numbers of the second kind.

A057964 Triangle T(n,k) of number of minimal 3-covers of a labeled n-set that cover k points of that set uniquely (k=3,..,n).

Original entry on oeis.org

1, 16, 6, 160, 120, 25, 1280, 1440, 600, 90, 8960, 13440, 8400, 2520, 301, 57344, 107520, 89600, 40320, 9632, 966, 344064, 774144, 806400, 483840, 173376, 34776, 3025, 1966080, 5160960, 6451200, 4838400, 2311680, 695520, 121000, 9330

Offset: 3

Vladeta Jovovic, Oct 17 2000

Row sums give A003468.

			[1], [16, 6], [160, 120, 25], [1280, 1440, 600, 90], ...; There are 305=160+120+25 minimal 3-covers of a labeled 5-set.

Eric Weisstein's World of Mathematics, Minimal cover

Cf. A035347, A057669 (unlabeled case), A057963, A057965-A057968.

Number of minimal m-covers of a labeled n-set that cover k points of that set uniquely is C(n, k)*S(k, m)*(2^m-m-1)^(n-k), where S(k, m) are Stirling numbers of the second kind.

A057966 Triangle T(n,k) of number of minimal 5-covers of a labeled n-set that cover k points of that set uniquely (k=5,..,n).

Original entry on oeis.org

1, 156, 15, 14196, 2730, 140, 984256, 283920, 29120, 1050, 57578976, 22145760, 3407040, 245700, 6951, 2994106752, 1439474400, 295276800, 31941000, 1807260, 42525, 142719088512, 82337935680, 21112291200, 3045042000, 258438180

Offset: 5

Vladeta Jovovic, Oct 17 2000

Row sums give A046166.

			[1], [156, 15], [14196, 2730, 140], [984256, 283920, 29120, 1050], ...; there are 15 minimal 5-covers of a labeled 6-set that cover 6 points of that set uniquely.

Eric Weisstein's World of Mathematics, Minimal cover

Cf. A035347, A057669, A057963-A057965, A057967, A057968(unlabeled case).

Number of minimal m-covers of a labeled n-set that cover k points of that set uniquely is C(n, k)*S(k, m)*(2^m-m-1)^(n-k), where S(k, m) are Stirling numbers of the second kind.

A282575 Triangular array read by rows. T(n,k) is the number of minimal covers of an n-set with exactly k points that are in more than one set of the cover, n>=0, 0<=k<=max(0,n-2).

Original entry on oeis.org

1, 1, 2, 5, 3, 15, 28, 6, 52, 210, 190, 10, 203, 1506, 3360, 1340, 15, 877, 10871, 48321, 60270, 9065, 21, 4140, 80592, 636300, 1820056, 1132880, 57512, 28, 21147, 618939, 8081928, 45455676, 76834926, 21067452, 344316, 36, 115975, 4942070, 101684115, 1027544400, 3860929170, 3406410252, 377190240, 1966440, 45

Offset: 0

Geoffrey Critzer, Feb 18 2017

			Triangle T(n,k) begins:
:    1;
:    1;
:    2;
:    5,     3;
:   15,    28,      6;
:   52,   210,    190,      10;
:  203,  1506,   3360,    1340,      15;
:  877, 10871,  48321,   60270,    9065,    21;
: 4140, 80592, 636300, 1820056, 1132880, 57512, 28;

Alois P. Heinz, Rows n = 0..100, flattened
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.

Cf. A035348. Row sums A046165. Column k=0 A000110. Column k=1 A003466.

Mirrored triangle gives A035347.

T:= (n, k)-> binomial(n, k)*add(Stirling2(n-k, j)*(2^j-j-1)^k, j=0..n-k):
seq(seq(T(n,k), k=0..max(0,n-2)), n=0..12);  # Alois P. Heinz, Feb 18 2017

nn = 8; Drop[Map[Select[#, # > 0 &] &,Range[0, nn]! CoefficientList[Series[Sum[ (Exp[x] - 1)^n/n! Exp[y (2^n - n - 1) x], {n, 0,nn}], {x, 0, nn}], {x, y}]], 1] // Grid

E.g.f.: (exp(x) - 1)^n/n!*exp(y*(2^n - n - 1)*x).

A003467 Number of minimal covers of an n-set that cover exactly 3 points uniquely.

Original entry on oeis.org

5, 28, 190, 1340, 9065, 57512, 344316, 1966440, 10813935, 57672340, 299893594, 1526727748, 7633634645, 37580965520, 182536112120, 876173330832, 4161823312731, 19585050873180, 91396904062870, 423311976698380, 1947235092796609, 8901646138480568

Offset: 3

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
Index entries for linear recurrences with constant coefficients, signature (20, -166, 740, -1921, 2960, -2656, 1280, -256).

Cf. A035347.

[5] cat [n*(n-1)*(n-2)*(4^n+192)/384: n in [4..30]]; // Vincenzo Librandi, May 03 2013

Table[SeriesCoefficient[x^3*(1+(1-4*x)^(-4)+3*(1-x)^(-4)),{x,0,n}],{n,3,25}] (* Vaclav Kotesovec, Oct 04 2012 *)

G.f.: x^3*(1 + (1-4*x)^(-4) + 3*(1-x)^(-4)). - corrected by Vaclav Kotesovec, Oct 04 2012
Recurrence (for n>3): 4*(n-1)*n*a(n-2)-5*(n-4)*n*a(n-1)+(n-4)*(n-3)*a(n)=0. - Vaclav Kotesovec, Oct 04 2012
For n>3, a(n) = n*(n-1)*(n-2)*(4^n+192)/384. - Vaclav Kotesovec, Oct 26 2012

Name clarified by Geoffrey Critzer, Apr 23 2017

cp's OEIS Frontend

A046165 Number of minimal covers of n objects.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A056885 Triangle T(n,k) = number of minimal covers of an unlabeled n-set that cover k points of that set uniquely, k=0..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A057963 Triangle T(n,k) of number of minimal 2-covers of a labeled n-set that cover k points of that set uniquely (k=2,..,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A057965 Triangle T(n,k) of number of minimal 4-covers of a labeled n-set that cover k points of that set uniquely (k=4,..,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A057964 Triangle T(n,k) of number of minimal 3-covers of a labeled n-set that cover k points of that set uniquely (k=3,..,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A057966 Triangle T(n,k) of number of minimal 5-covers of a labeled n-set that cover k points of that set uniquely (k=5,..,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A282575 Triangular array read by rows. T(n,k) is the number of minimal covers of an n-set with exactly k points that are in more than one set of the cover, n>=0, 0<=k<=max(0,n-2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A003467 Number of minimal covers of an n-set that cover exactly 3 points uniquely.

Views

Author

Keywords

References

Links