A035348 -id:A035348 - cp's OEIS frontend

A003469 Number of minimal covers of an (n + 1)-set by a collection of n nonempty subsets, a(n) = A035348(n,n-1).

1, 6, 22, 65, 171, 420, 988, 2259, 5065, 11198, 24498, 53157, 114583, 245640, 524152, 1113959, 2359125, 4980546, 10485550, 22019865, 46137091, 96468716, 201326292, 419430075, 872414881, 1811938950, 3758095978, 7784627789, 16106126895, 33285996048

Offset: 1

N. J. A. Sloane

A cover of a set S is a collection of nonempty subsets of S whose union is S. A cover of S is called minimal if none of its proper subsets covers S. [from the Hearne/Wagner reference]
Partial sums of A053221.
Construct an inverted triangle table with n rows as follows: the first row are numbers from 1 to n; for the other rows, each number is the sum of the two numbers above it. Then a(n) is the sum of all numbers in the table. See examples below. - Jianing Song, Sep 04 2018

			From _Jianing Song_, Sep 04 2018: (Start)
For n = 4 the inverted triangle table is:
1     2     3     4
   3     5     7
      8    12
        20
So a(4) = 1 + 2 + 3 + 4 + 3 + 5 + 7 + 8 + 12 + 20 = 65.
For n = 5 the inverted triangle table is:
1     2     3     4     5
   3     5     7     9
      8    12    16
        20    28
           48
So a(5) = 1 + 2 + 3 + 4 + 5 + 3 + 5 + 7 + 9 + 8 + 12 + 16 + 20 + 28 + 48 = 171. (End)

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 = 1..1000
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
Anthony J. Macula, Lewis Carroll and the Enumeration of Minimal Covers, Math. Mag. vol. 68, n4, p 274 Oct '95.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (7,-19,25,-16,4)

Cf. A053218, A053221 (first differences).

[2^n*(n+1)-(n^2+3*n+2)/2: n in [1..30]]; // Vincenzo Librandi, Aug 19 2011

a := n -> add((n+1)*binomial(n+1, k+1)/2, k=1..n):
seq(a(n), n=1..30); # Zerinvary Lajos, May 08 2007
A003469:=(-1+z+z**2)/(2*z-1)**2/(z-1)**3; # conjectured by Simon Plouffe in his 1992 dissertation

Table[(n+1)2^n-(n+1)(n+2)/2, {n, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
CoefficientList[Series[((2*x + 1)*Exp[2*x] - (x^2/2 + 2*x + 1)*Exp[x])/x, {x, 0, 200}], x]*Table[(k+1)!, {k, 0, 200}] (* Stefano Spezia, Sep 04 2018 *)

PARI
```
a(n) = (n+1)*2^n-(n+1)*(n+2)/2;
```

G.f.: x*(1 - x - x^2)/((1 - x)^3*(1 - 2*x)^2).
a(n) = (n + 1)*2^n - (n + 1)*(n + 2)/2. - Paul Barry, Jan 27 2003
E.g.f.: (2*x + 1)*exp(2*x) - (x^2/2 + 2*x + 1)*exp(x). - Jianing Song, Sep 04 2018

Offset changed from 2 to 1 by Vincenzo Librandi, Aug 19 2011

Title corrected by Geoffrey Critzer, Jun 29 2013

A046165 Number of minimal covers of n objects.

Original entry on oeis.org

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

A055080 Triangle T(n,k) read by rows, giving number of k-member minimal covers of an unlabeled n-set, k=1..n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 9, 4, 1, 1, 9, 23, 17, 5, 1, 1, 12, 51, 65, 28, 6, 1, 1, 16, 103, 230, 156, 43, 7, 1, 1, 20, 196, 736, 863, 336, 62, 8, 1, 1, 25, 348, 2197, 4571, 2864, 664, 86, 9, 1, 1, 30, 590, 6093, 22952, 25326, 8609, 1229, 115, 10, 1, 1, 36, 960

Offset: 1

Vladeta Jovovic, Jun 13 2000

Also number of unlabeled split graphs on n vertices and with a k-element clique (cf. A048194).

			Triangle begins:
  1;
  1,  1;
  1,  2,   1;
  1,  4,   3,   1;
  1,  6,   9,   4,   1;
  1,  9,  23,  17,   5,   1;
  1, 12,  51,  65,  28,   6,  1;
  1, 16, 103, 230, 156,  43,  7, 1;
  1, 20, 196, 736, 863, 336, 62, 8, 1;
  ...
There are four minimal covers of an unlabeled 3-set: one 1-cover {{1,2,3}}, two 2-covers {{1,2},{3}}, {{1,2},{1,3}} and one 3-cover {{1},{2},{3}}.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
Vladeta Jovovic, Binary matrices up to row and column permutations
G. F. Royle, Counting Set Covers and Split Graphs, J. Integer Seqs., 3 (2000), #00.2.6.
Eric Weisstein's World of Mathematics, Minimal covers

Row sums give A048194.
Columns are A000012, A087811, A005783, A005784, A005785 A005786, A055066.
Diagonals are A000012, A000027, A005744, A005745, A005746, A005771, A005747, A005748.
Cf. A035348 for labeled case.
Cf. A002620, A028657.

\\ Needs A(n,m) from A028657.
T(n,k) = A(n-k, k) - if(kAndrew Howroyd, Feb 28 2023

T(n,k) = A028657(n,k) - A028657(n-1,k). - Andrew Howroyd, Feb 28 2023

A046166 Number of minimal covers on n objects with 5 members.

Original entry on oeis.org

0, 0, 0, 0, 1, 171, 17066, 1298346, 83384427, 4762648737, 249485204452, 12226539786912, 568267449522773, 25296121946918823, 1086375882592194558, 45264846407024660598, 1837809636559394481439, 72965749033508656346829

Offset: 1

Eric W. Weisstein

nonn

Indranil Ghosh, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Minimal Cover.
Index entries for linear recurrences with constant coefficients, signature (171,-12175,461985,-9853624,112007964,-530122320).

Cf. A035348.

LinearRecurrence[{171,-12175,461985,-9853624,112007964,-530122320},{0,0,0,0,1,171},18] (* or *) CoefficientList[Series[(x^5)/((1-26x)(1-27x)(1-28x)(1-29x)(1-30x)(1-31x)) ,{x,0,100}],x] (* Indranil Ghosh, Feb 20 2017 *)

G.f.: x^5/[(1-26x)(1-27x)(1-28x)(1-29x)(1-30x)(1-31x)].

A094544 Triangle of a(n,m) = number of m-member minimal T_0-covers of an n-set (n >= 0, 0<= m <=n).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 3, 1, 0, 0, 0, 16, 1, 0, 0, 0, 120, 55, 1, 0, 0, 0, 480, 1650, 156, 1, 0, 0, 0, 840, 34650, 13650, 399, 1, 0, 0, 0, 0, 554400, 873600, 89376, 960, 1, 0, 0, 0, 0, 6985440, 45208800, 14747040, 514080, 2223, 1, 0, 0, 0, 0, 69854400, 1989187200

Offset: 0

Goran Kilibarda and Vladeta Jovovic, May 08 2004

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.

			1;
0, 1;
0, 0, 1;
0, 0, 3,   1;
0, 0, 0,  16,    1;
0, 0, 0, 120,   55,   1;
0, 0, 0, 480, 1650, 156, 1;
...

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Minimal Cover.

Cf. A035348, A046165, A094545 (row sums), A094546 (column sums).

Flatten[Table[n!/m! Binomial[2^m-m-1,n-m],{n,0,10},{m,0,n}]] (* Harvey P. Dale, Jan 16 2012 *)

a(n, m) = n!/m!*binomial(2^m-m-1, n-m).

E.g.f.: Sum_{n>=0} y^n*(1+y)^(2^n-n-1)*x^n/n!.

A094545 Number of minimal T_0-covers of an n-set.

Original entry on oeis.org

1, 1, 1, 4, 17, 176, 2287, 49540, 1518337, 67457584, 4254836111, 376795261844, 46709151254449, 8061849904932136, 1936383997541071639, 646603398091877815516, 300476951799493029958913

Offset: 0

Goran Kilibarda and Vladeta Jovovic, May 08 2004

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.

Row sums of A094544.

Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Minimal Cover.

Cf. A035348, A046165, A094544, A094546.

a(n) = Sum_{m=0..n} (n!/m!)*binomial(2^m-m-1, n-m).
a(n) = Sum_{m=0..n} Stirling1(n, m)*A046165(m).
E.g.f.: Sum_{n>=0} x^n*(1+x)^(2^n-n-1)/n!.

A094546 Number of n-member minimal T_0-covers.

Original entry on oeis.org

1, 1, 4, 1457, 112632827396, 158158632767281777075441633086607, 6800377846899806825426438402771408584453689087636553015800284773113817943589005365456

Offset: 0

Goran Kilibarda and Vladeta Jovovic, May 08 2004

A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.

G. C. Greubel, Table of n, a(n) for n = 0..8
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
Eric Weisstein's World of Mathematics, Minimal Cover.

Cf. A035348, A046165, A094545.

Column sums of A094544.

Table[Sum[(m!/n!)*Binomial[2^n - n - 1, m - n], {m, n, 2^n - 1}], {n, 0, 5}] (* G. C. Greubel, Oct 07 2017 *)

for(n=0,5, print1(sum(m=n,2^n -1, (m!/n!)*binomial(2^n-n-1, m-n)), ", ")) \\ G. C. Greubel, Oct 07 2017

a(n) = Sum_{m=n..2^n-1} m!/n!*binomial(2^n-n-1, m-n).

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

A046169 Number of minimal covers on n objects with 9 members.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 5065, 14109865, 28586753635, 47057782540912, 66738127617591430, 84508389361603849070, 97838285747685771503930, 105306724888534860425617883, 106678207181565103216667658695

Offset: 1

Eric W. Weisstein

nonn

Eric Weisstein's World of Mathematics, Minimal Cover.

Cf. A035348.

G.f.: x^9 / Product_{k=2^9-10..2^9-1} (1-k*x). - Sean A. Irvine, Apr 07 2021

A049055 Triangle read by rows, giving T(n,k) = number of k-member minimal ordered covers of a labeled n-set (1 <= k <= n).

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 50, 132, 24, 1, 180, 1830, 1560, 120, 1, 602, 20460, 60960, 20520, 720, 1, 1932, 201726, 1856400, 2047920, 302400, 5040, 1, 6050, 1832292, 48550824, 155801520, 72586080, 4979520, 40320, 1, 18660, 15717750, 1144994760, 10006131240, 13069123200, 2767474080, 91082880, 362880

Offset: 1

N. J. A. Sloane, Michael Somos

			Triangle starts
  1;
  1,   2;
  1,  12,   6;
  1,  50, 132,  24;
  ...

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.

Row sums are A049056.

Cf. A035348.

t[n_, k_] := Sum[ (-1)^i*Binomial[k, i]*(2^k - 1 - i)^n, {i, 0, k}]; Flatten[ Join[{1}, Table[t[n, k], {n, 1, 9}, {k, 1, n}]]] (* Jean-François Alcover, Dec 12 2011, after Michael Somos *)

{T(n, k)=sum(i=0, k, (-1)^i*binomial(k, i)*(2^k-1-i)^n)} /* Michael Somos, Oct 16 2006 */

T(n,k) = A035348(n,k)*k!, the order in which we cover the n-set is considered. - Geoffrey Critzer, Jun 28 2013

cp's OEIS Frontend

A003469 Number of minimal covers of an (n + 1)-set by a collection of n nonempty subsets, a(n) = A035348(n,n-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A046165 Number of minimal covers of n objects.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A055080 Triangle T(n,k) read by rows, giving number of k-member minimal covers of an unlabeled n-set, k=1..n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A046166 Number of minimal covers on n objects with 5 members.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A094544 Triangle of a(n,m) = number of m-member minimal T_0-covers of an n-set (n >= 0, 0<= m <=n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A094545 Number of minimal T_0-covers of an n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A094546 Number of n-member minimal T_0-covers.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula