A005786 -id:A005786 - cp's OEIS frontend

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

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

A003468 Number of minimal 3-covers of a labeled n-set.

Original entry on oeis.org

1, 22, 305, 3410, 33621, 305382, 2619625, 21554170, 171870941, 1337764142, 10216988145, 76862115330, 571247591461, 4203844925302, 30687029023865, 222518183370890, 1604626924403181, 11518132293452862

Offset: 3

N. J. A. Sloane

nonn

This is also the fourth column of the Sheffer triangle A143496 (4-restricted Stirling2 numbers). See the e.g.f. given below. See also the Sheffer comments in A193685. - Wolfdieter Lang, Oct 08 2011

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.
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
Eric Weisstein's World of Mathematics, Minimal cover.
Index entries for linear recurrences with constant coefficients, signature (22, -179, 638, -840).

Cf. A000392, A003468, A016111, A046166-A046169, A057668, A005783-A005786, A055066.

Cf. A143496, A000302, A005060, A016103.

[7^n/6 - 6^n/2 + 5^n/2 - 4^n/6: n in [3..30]]; // Vincenzo Librandi, May 03 2013

A003468:=1/(6*z-1)/(4*z-1)/(7*z-1)/(5*z-1); # conjectured by Simon Plouffe in his 1992 dissertation

Table[7^n/6 - 6^n/2 + 5^n/2 - 4^n/6, {n, 3, 20}] (* Vaclav Kotesovec, Nov 19 2012 *)
LinearRecurrence[{22,-179,638,-840},{1,22,305,3410},20] (* Harvey P. Dale, Jan 09 2024 *)

G.f.: x^3/((1 - 4*x)*(1 - 5*x)*(1 - 6*x)*(1 - 7*x)). - N. J. A. Sloane, May 12 1994, corrected by Vaclav Kotesovec, Nov 19 2012
E.g.f.: (exp(4*x)*(exp(x) - 1)^3)/6. More generally, e.g.f. for number of minimal m-covers of a labeled n-set is (exp((2^m - m - 1)*x)*(exp(x) - 1)^m)/m!. - Vladeta Jovovic, May 09 2004
If we define f(m, j, x) = sum(binomial(m, k)*stirling2(k, j)*x^(m - k),k = j .. m) then a(n) = f(n, 3, 4), (n >= 3). - Milan Janjic, Apr 26 2009
a(n) = 7^n/6 - 6^n/2 + 5^n/2 - 4^n/6. - Vaclav Kotesovec, Nov 19 2012

A005783 Number of 3-covers of an unlabeled n-set.

Original entry on oeis.org

1, 3, 9, 23, 51, 103, 196, 348, 590, 960, 1506, 2290, 3393, 4905, 6945, 9651, 13185, 17739, 23542, 30846, 39954, 51206, 64986, 81730, 101935, 126141, 154967, 189093, 229269, 276325, 331182, 394830, 468372, 553002, 650016, 760824, 886963

Offset: 0

N. J. A. Sloane

Equals first differences of A002727. - Vladeta Jovovic, May 24 2000

Number of 3 X n binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

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

Stefano Spezia, Table of n, a(n) for n = 0..10000 (terms for n = 1..1000 from T. D. Noe)
R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
Masaaki Harada, Ken Saito, Binary linear complementary dual codes, arXiv:1802.06985 [math.CO], 2018.
Vladeta Jovovic, Binary matrices up to row and column permutations
Index entries for linear recurrences with constant coefficients, signature (3,-1,-3,-1,3,6,-6,-3,1,3,1,-3,1).

Column 3 of A055080.

Cf. A002727, A002620, A005784, A005785, A005786, A055066.

CoefficientList[Series[(x^6+x^4+2x^3+x^2+1)/((1-x^3)^2(1-x^2)^2 (1-x)^3),{x,0,50}],x] (* Harvey P. Dale, May 19 2011 *)

Vec(G(3, x)*(1 - x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

G.f.: (x^6+x^4+2*x^3+x^2+1)/((1-x^3)^2*(1-x^2)^2*(1-x)^3).
a(n) ~ n^6/4320. - Stefano Spezia, Aug 08 2022
a(n) = n^6/4320 + 7*n^5/1440 + 79*n^4/1728 + 35*n^3/144 + 2939*n^2/4320 + 8863*n/8640 + 1 + (n/16 + 7/32)*floor(n/2) + (n/9 + 11/27)*floor(n/3) + floor((n+1)/3)/27. - Vaclav Kotesovec, Aug 09 2022

More terms from Vladeta Jovovic, May 24 2000

a(0) = 1 prepended by Stefano Spezia, Aug 09 2022

A055066 Number of 7-covers of an unlabeled n-set.

Original entry on oeis.org

1, 7, 62, 664, 8609, 127415, 2004975, 31500927, 474504448, 6708348262, 88249739792, 1078567590128, 12269901302433, 130370516668917, 1298891291366245, 12182760243381355, 107979270564656625, 907568508195185203, 7256984238345563764, 55365443728411530716, 404091280028746802188

Offset: 0

Vladeta Jovovic, Jun 12 2000

nonn

Number of 7 X n binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

Column 7 of A055080.

Cf. A005748, A002620, A005783, A005784, A005785, A005786.

Vec(G(7, x)*(1-x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

a(0)=1 prepended by Alois P. Heinz, Aug 08 2022

Terms a(17) and beyond from Andrew Howroyd, Feb 28 2023

A005784 Number of 4-covers of an unlabeled n-set.

Original entry on oeis.org

1, 4, 17, 65, 230, 736, 2197, 6093, 15864, 38960, 90837, 202005, 430577, 883057, 1748909, 3355213, 6252575, 11345602, 20089514, 34778306, 58964020, 98053576, 160151566, 257229974, 406739271, 633795181, 974126408, 1477999320, 2215409037, 3282874359, 4812278064

Offset: 0

N. J. A. Sloane

Number of 4 X n binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

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

Stefano Spezia, Table of n, a(n) for n = 0..10000
R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
Vladeta Jovovic, Binary matrices up to row and column permutations
Index entries for linear recurrences with constant coefficients, signature (5, -7, -1, 5, -1, 21, -33, 0, -4, 8, 68, -57, -3, -57, 13, 100, -32, 32, -100, -13, 57, 3, 57, -68, -8, 4, 0, 33, -21, 1, -5, 1, 7, -5, 1).

Column 4 of A055080.
First differences of A006148.
Cf. A002620, A005783, A005785, A005786, A055066.

Vec(G(4, x)*(1 - x) + O(x^40)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

G.f.: (x^20 - x^19 + 4*x^18 + 9*x^17 + 23*x^16 + 39*x^15 + 90*x^14 + 131*x^13 + 204*x^12 + 238*x^11 + 252*x^10 + 238*x^9 + 204*x^8 + 131*x^7 + 90*x^6 + 39*x^5 + 23*x^4 + 9*x^3 + 4*x^2 - x + 1)/((1 - x^4)^3*(1 - x^3)^4*(1 - x^2)^3*(1 - x)^5).
a(n) ~ n^14/2092278988800. - Stefano Spezia, Aug 08 2022
a(n) = n^14/2092278988800 + n^13/19926466560 + n^12/418037760 + n^11/14598144 + 689*n^10/522547200 + 253*n^9/13934592 + 2184839*n^8/11705057280 + 10313*n^7/6967296 + 2319707*n^6/250822656 + 1817221*n^5/39813120 + 2405336243*n^4/13795246080 + 151784975*n^3/306561024 + 93746545019*n^2/95103590400 + 924100468541*n/717352796160 + 1 + (n^2/486 + 5*n/162 + 233/2187)*floor(n/3) + (n^2/256 + 15*n/256 + 101/512)*floor(n/4) - (n^3/1458 + 7*n^2/486 + 22*n/243 + 356/2187)*floor((n+1)/3) + (n^5/122880 + 5*n^4/16384 + 125*n^3/24576 + 359*n^2/8192 + 10967*n/61440 + 8461/32768)*floor(n/2) + (n/256 + 15/512)*floor((n+1)/4). - Vaclav Kotesovec, Aug 09 2022

More terms from Vladeta Jovovic, Jun 03 2000

a(0)=1 prepended by Alois P. Heinz, Aug 08 2022

A057668 Number of minimal 7-covers of a labeled n-set.

Original entry on oeis.org

1, 988, 549102, 226064280, 76785889587, 22762819040676, 6092115565691584, 1505097773271664000, 348617485585838373333, 76564317282173987801964, 16080209472530744351164146, 3250906483045575317042337960, 635954979082842132795003641239

Offset: 7

Vladeta Jovovic, Oct 16 2000

Eric Weisstein's World of Mathematics, Minimal cover

Cf. A000392, A003468, A016111, A046166-A046169, A005783-A005786, A055066 (unlabeled case).

a(n) = (1/7!) * (127^n - 7 * 126^n + 21 * 125^n - 35 * 124^n + 35 * 123^n - 21 * 122^n + 7 * 121^n - 120^n).

G.f.: x^7 / ((120*x-1)*(121*x-1)*(122*x-1)*(123*x-1)*(124*x-1)*(125*x-1)*(126*x-1)*(127*x-1)). - Colin Barker, Jul 11 2013

Additional term from Colin Barker, Jul 11 2013

cp's OEIS Frontend

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

A003468 Number of minimal 3-covers of a labeled n-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A005783 Number of 3-covers of an unlabeled n-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A055066 Number of 7-covers of an unlabeled n-set.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A005784 Number of 4-covers of an unlabeled n-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A057668 Number of minimal 7-covers of a labeled n-set.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions