A005783 -id:A005783 - 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

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

Original entry on oeis.org

1, 2, 1, 4, 3, 2, 7, 7, 6, 3, 11, 13, 14, 9, 4, 16, 22, 26, 21, 13, 5, 23, 34, 44, 40, 31, 17, 7, 31, 50, 68, 68, 59, 41, 23, 8, 41, 70, 100, 106, 101, 79, 55, 28, 10, 53, 95, 140, 157, 158, 136, 106, 68, 35, 12, 67, 125, 190, 221, 234, 214, 182, 132, 85, 42, 14, 83, 161

Offset: 0

Vladeta Jovovic, Oct 16 2000

Row sums give A005783.

			[1], [2, 1], [4, 3, 2], [7, 7, 6, 3], ...
There are 7 minimal 3-covers of an unlabeled 6-set that cover 3 points of that set uniquely: {{1}, {2, 4, 5, 6}, {3, 4, 5, 6}}, {{1, 6}, {2, 4, 5}, {3, 4, 5, 6}}, {{1, 6}, {2, 4, 5, 6}, {3, 4, 5, 6}}, {{1, 5, 6}, {2, 4, 6}, {3, 4, 5}}, {{1, 5, 6}, {2, 4, 6}, {3, 4, 5, 6}}, {{1, 5, 6}, {2, 4, 5, 6}, {3, 4, 5, 6}}, {{1, 4, 5, 6}, {2, 4, 5, 6}, {3, 4, 5, 6}}.

V. Jovovic, More information

Cf. A001752, A056885, A057222, A057223, A057524.

T(n, k) = b(n, k)-b(n-1, k); b(n, k) = coefficient of x^k in x^3/6*(Z(S_n; 5+3*x, 5+3*x^2, ...)+3*Z(S_n; 3+x, 5+3*x^2, 3+x^3, 5+3*x^4, ...)+2*Z(S_n; 2, 2, 5+3*x^3, 2, 2, 5+3*x^6, ...)), where Z(S_n; x_1, x_2, ..., x_n) is cycle index of symmetric group S_n of degree n.

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

A005785 Number of 5-covers of an unlabeled n-set.

Original entry on oeis.org

1, 5, 28, 156, 863, 4571, 22952, 108182, 477136, 1969270, 7625579, 27804973, 95858868, 313747418, 978734539, 2920530663, 8363945469, 23057872913, 61357278239, 157985305473, 394486861086, 957156158394, 2260761331227

Offset: 0

N. J. A. Sloane

Number of 5 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 (7, -17, 13, 7, -11, 16, -44, 43, -65, 82, 46, -36, -28, -175, 85, -168, 504, 91, 77, -394, -664, -52, -382, 1642, 600, 813, -1209, -1632, -1650, -1050, 2982, 2124, 3592, -1360, -2074, -5329, -3607, 1970, 3608, 7640, 1778, 426, -8168, -6638, -3524, 2095, 8401, 6077, 5907, -5907, -6077, -8401, -2095, 3524, 6638, 8168, -426, -1778, -7640, -3608, -1970, 3607, 5329, 2074, 1360, -3592, -2124, -2982, 1050, 1650, 1632, 1209, -813, -600, -1642, 382, 52, 664, 394, -77, -91, -504, 168, -85, 175, 28, 36, -46, -82, 65, -43, 44, -16, 11, -7, -13, 17, -7, 1).

Column 5 of A055080.
First differences of A052264.
Cf. A002620, A005783, A005784, A055066.

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

G.f.: - (x^68 - 2*x^67 + 10*x^66 + 32*x^65 + 175*x^64 + 794*x^63 + 3441*x^62 + 13186*x^61 + 46027*x^60 + 146118*x^59 + 427347*x^58 + 1155432*x^57 + 2912873*x^56 + 6875608*x^55 + 15281029*x^54 + 32094658*x^53 + 63945531*x^52 + 121210914*x^51 + 219194198*x^50 + 378998758*x^49 + 627863648*x^48 + 998282344*x^47 + 1525746624*x^46 + 2244502676*x^45 + 3181886869*x^44 + 4351201210*x^43 + 5744918381*x^42 + 7328807372*x^41 + 9039504349*x^40 + 10785767638*x^39 + 12455264802*x^38 + 13925287384*x^37 + 15077477135*x^36 + 15812782150*x^35 + 16065602576*x^34 + 15812782150*x^33 + 15077477135*x^32 + 13925287384*x^31 + 12455264802*x^30 + 10785767638*x^29 + 9039504349*x^28 + 7328807372*x^27 + 5744918381*x^26 + 4351201210*x^25 + 3181886869*x^24 + 2244502676*x^23 + 1525746624*x^22 + 998282344*x^21 + 627863648*x^20 + 378998758*x^19 + 219194198*x^18 + 121210914*x^17 + 63945531*x^16 + 32094658*x^15 + 15281029*x^14 + 6875608*x^13 + 2912873*x^12 + 1155432*x^11 + 427347*x^10 + 146118*x^9 + 46027*x^8 + 13186*x^7 + 3441*x^6 + 794*x^5 + 175*x^4 + 32*x^3 + 10*x^2 - 2*x + 1)/((x^6 - 1)^2*(x^4 + x^3 + x^2 + x + 1)^6*(x^3 - x^2 + x - 1)^6*(x^2 + x + 1)^6*(x + 1)^10*(x - 1)^23).

a(n) = n^30/(30!*5!) + O(n^29). - Vaclav Kotesovec, Aug 09 2022

More terms from Vladeta Jovovic, Jun 03 2000

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

A005786 Number of 6-covers of an unlabeled n-set.

Original entry on oeis.org

1, 6, 43, 336, 2864, 25326, 223034, 1890123, 15115098, 112980937, 787320629, 5121184083, 31188412225, 178517111561, 964196387369, 4933278065881, 23997707450765, 111358094980387, 494444748602595, 2106504840061571

Offset: 0

N. J. A. Sloane

nonn

Number of 6 X n binary matrices with at least one 1 in every column up to row and column permutations.

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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

Column 6 of A055080.

Cf. A002620, A005783, A005784, A005785, A055066.

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

More terms from Vladeta Jovovic, Jun 12 2000

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

A055484 Number of unlabeled 3-element intersecting families (with not necessarily distinct sets) of an n-element set.

Original entry on oeis.org

1, 4, 14, 39, 96, 213, 437, 837, 1520, 2632, 4380, 7040, 10979, 16668, 24716, 35879, 51104, 71549, 98625, 134025, 179782, 238292, 312386, 405368, 521083, 663968, 839140, 1052439, 1310534, 1620985, 1992343, 2434229, 2957458, 3574108

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Jul 03 2000

nonn

G. C. Greubel, Table of n, a(n) for n = 1..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (4, -4, -2, 2, 4, 3, -12, 3, 4, 2, -2, -4, 4, -1).

Cf. A053155 (labeled case), A005783, A002727, A051180.

Rest[CoefficientList[Series[-x*(x^3 - x^2 - 1)*(x^6 + x^4 + 2*x^3 + x^2 + 1)/((x^3 - 1)^2*(x^2 - 1)^2*(x - 1)^4), {x, 0, 50}], x]] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{4,-4,-2,2,4,3,-12,3,4,2,-2,-4,4,-1},{1,4,14,39,96,213,437,837,1520,2632,4380,7040,10979,16668},40] (* Harvey P. Dale, Jun 10 2024 *)

x='x+O('x^50); Vec(-x*(x^3-x^2-1)*(x^6+x^4+2*x^3+x^2+1)/( (x^3-1)^2*(x^2-1)^2*(x-1)^4)) \\ G. C. Greubel, Oct 06 2017

G.f.: -x*(x^3-x^2-1)*(x^6+x^4+2*x^3+x^2+1)/((x^3-1)^2*(x^2-1)^2*(x-1)^4).

More terms from James Sellers, Jul 04 2000

A055485 Number of unlabeled 3-element intersecting families (with distinct sets) of an n-element set.

Original entry on oeis.org

4, 19, 61, 157, 353, 717, 1355, 2412, 4094, 6676, 10524, 16108, 24036, 35063, 50135, 70409, 97295, 132485, 178011, 236268, 310086, 402768, 518158, 660692, 835486, 1048379, 1306039, 1616025, 1986887, 2428245, 2950913, 3566968, 4289896

Offset: 3

Vladeta Jovovic, Goran Kilibarda, Jul 03 2000

nonn

G. C. Greubel, Table of n, a(n) for n = 3..1000
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (in Russian), Diskretnaya Matematika, 11 (1999), no. 4, 127-138.
V. Jovovic, G. Kilibarda, On the number of Boolean functions in the Post classes F^{mu}_8, (English translation), Discrete Mathematics and Applications, 9, (1999), no. 6.
Index entries for linear recurrences with constant coefficients, signature (3,1,-9,0,12,7,-15,-16,16,15,-7,-12,0,9,-1,-3,1).

Cf. A051180 (labeled case), A005783.

Rest[Rest[Rest[CoefficientList[Series[-x^3*(x^8 + x^7 - 3*x^6 - x^5 + x^4 + 3*x^3 - x^2 - 3*x - 4)/((x^3 - 1)^2*(x^2 - 1)^2*(x - 1)^4), {x,0,50}], x]]]] (* G. C. Greubel, Oct 06 2017 *)
LinearRecurrence[{3, 1, -9, 0, 12, 7, -15, -16, 16, 15, -7, -12, 0, 9, -1, -3, 1}, {4, 19, 61, 157, 353, 717, 1355, 2412, 4094, 6676, 10524, 16108, 24036, 35063, 50135, 70409, 97295}, 33] (* Vincenzo Librandi, Oct 07 2017 *)

x='x+O('x^50); Vec(-x^3*(x^8+x^7-3*x^6-x^5+x^4+3*x^3-x^2-3*x-4)/((x^3-1)^2*(x^2-1)^2*(x-1)^4)) \\ G. C. Greubel, Oct 06 2017

G.f.: -x^3*(x^8+x^7-3*x^6-x^5+x^4+3*x^3-x^2-3*x-4)/((x^3-1)^2*(x^2-1)^2*(x-1)^4).

More terms from James Sellers, Jul 04 2000

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

Original entry on oeis.org

1, 9, 29, 72, 154, 294, 522, 877, 1406, 2172, 3255, 4746, 6763, 9445, 12953, 17480, 23254, 30528, 39604, 50823, 64568, 81276, 101443, 125610, 154395, 188479, 228611, 275622, 330432, 394032, 467524, 552103, 649064, 759818, 885901

Offset: 2

Vladeta Jovovic, Jun 30 2000

Covers are defined in proper sense, i.e. without empty sets or multiple sets.

Andrew Howroyd, Table of n, a(n) for n = 2..1000
Eric Weisstein's World of Mathematics, Covers
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 A055130.

Cf. A005783.

Drop[CoefficientList[Series[x^2(x^11-x^10-3x^9+4x^7+6x^6-3x^5-5x^4-3x^3+ 3x^2+6x+1)/ ((1-x^3)^2(1-x^2)^2(1-x)^3),{x,0,40}],x],2] (* or *) LinearRecurrence[ {3,-1,-3,-1,3,6,-6,-3,1,3,1,-3,1},{1,9,29,72,154,294,522,877,1406,2172,3255,4746,6763},40] (* Harvey P. Dale, Jul 18 2021 *)

G.f.: x^2*(x^11-x^10-3*x^9+4*x^7+6*x^6-3*x^5-5*x^4-3*x^3+3*x^2+6*x+1)/((1-x^3)^2*(1-x^2)^2*(1-x)^3).

More terms from James Sellers, Jul 04 2000

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

A005785 Number of 5-covers of an unlabeled n-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

A005786 Number of 6-covers of an unlabeled n-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A055484 Number of unlabeled 3-element intersecting families (with not necessarily distinct sets) of an n-element set.