A369950 -id:A369950 - cp's OEIS frontend

A003465 Number of ways to cover an n-set.

1, 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281

Offset: 0

N. J. A. Sloane

Let S be an n-element set, and let P be the set of all nonempty subsets of S. Then a(n) = number of subsets of P whose union is S.
Including the empty set doubles the entries, and we get A000371.
For disjoint covers see A000110. - Manfred Boergens, May 13 2024
For disjoint covers which may include one empty set see A186021. - Manfred Boergens, Mar 09 2025

			Let n=2, S={a,b}, P={a,b,ab}. There are five subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}. - _Marc LeBrun_, Nov 10 2010

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.

Alois P. Heinz, Table of n, a(n) for n = 0..11
D. Applegate, M. LeBrun and N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
Martin Klazar, Extremal problems for ordered hypergraphs, arXiv:math/0305048 [math.CO], 2003.
Liwen Ma, Classification of coverings in the finite approximation spaces, Inf. Sci. 276 (2014) 31-41
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
S. Spasovski and A. M. Bogdanova, Optimization of the Polynomial Greedy Solution for the Set Covering Problem, 2013, 10th Conference for Informatics and Information Technology (CIIT 2013).
Eric Weisstein's World of Mathematics, Cover.
Yoad Winter and Remko Scha, Plurals, draft chapter for the Wiley-Blackwell Handbook of Contemporary Semantics - second edition, edited by Shalom Lappin and Chris Fox, 2014.
Ping Zhou, Covering rough sets based on neighborhoods: an approach without using neighborhoods, Int. J. Approx. Reas. 52 (2011) 461-472, Section 3

Cf. A007537, A000371, A055154 (row sums), A369950 (diagonal for n>=1), A055621 (unlabeled case).
Column sums of A326914 and of A326962.
Cf. A000110, A186021.

a:= n-> add((-1)^k * binomial(n, k)*2^(2^(n-k))/2, k=0..n):
seq(a(n), n=0..11);  # Alois P. Heinz, Aug 24 2014

Table[Sum[(-1)^j Binomial[n,j] 2^(2^(n-j)-1),{j,0,n}],{n,0,10}] (* Geoffrey Critzer, Jun 26 2013 *)

{a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* Michael Somos, Jun 14 1999 */

a(n) = Sum_{k>=0} (-1)^k * binomial(n, k) * 2^(2^(n-k)) / 2. - Michael Somos, Jun 14 1999
E.g.f.: (1/2)*Sum_{n>=0} exp((2^n-1)*x)*log(2)^n/n!. - Vladeta Jovovic, May 30 2004
a(n) ~ 2^(2^n - 1). - Vaclav Kotesovec, Jul 02 2016

More terms and comments from Michael Somos

Entry revised by N. J. A. Sloane, Nov 23 2010

A055154 Triangle read by rows: T(n,k) = number of k-covers of a labeled n-set, k=1..2^n-1.

Original entry on oeis.org

1, 1, 3, 1, 1, 12, 32, 35, 21, 7, 1, 1, 39, 321, 1225, 2919, 4977, 6431, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 1, 120, 2560, 24990, 155106, 711326, 2597410, 7856550, 20135050, 44337150, 84665490, 141118250, 206252550, 265182450, 300540190

Offset: 1

Vladeta Jovovic, Jun 14 2000

Row sums give A003465.
From Manfred Boergens, Apr 11 2024: (Start)
If more than half of the nonempty subsets of [n] are drawn their union covers [n] (see Formula). - The proof is based on 2^(n-1)-1 being the number of nonempty subsets of [n] with one fixed element of [n] missing.
For covers which may include one empty set see A163353.
For disjoint covers see A008277.
For disjoint covers which may include one empty set see A256894 (amendment by Manfred Boergens, Mar 09 2025). (End)

			Triangle begins:
  [1],
  [1,3,1],
  [1,12,32,35,21,7,1],
  ...
There are 35 4-covers of a labeled 3-set.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.

Alois P. Heinz, Rows n = 1..10, flattened

Cf. A054780, A055621.
Cf. A369950 (partial row sums).
Cf. 256894.
Columns: A029858, A095152, A095153, A095155.

nn=5;Map[Select[#,#>0&]&,Transpose[Table[Table[Sum[(-1)^j Binomial[n,j] Binomial[2^(n-j)-1,m],{j,0,n}],{n,1,nn}],{m,1,2^nn-1}]]]//Grid (* Geoffrey Critzer, Jun 27 2013 *)

T(n,k) = Sum_{j=0..n} (-1)^j*C(n, j)*C(2^(n-j)-1, k), k=1..2^n-1.
From Vladeta Jovovic, May 30 2004: (Start)
T(n,k) = (1/k!)*Sum_{j=0..k} Stirling1(k+1, j+1)*(2^j-1)^n.
E.g.f.: Sum(exp(y*(2^n-1))*log(1+x)^n/n!, n=0..infinity)/(1+x). (End)
Also exp(-y)*Sum((1+x)^(2^n-1)*y^n/n!, n=0..infinity).
From Manfred Boergens, Apr 11 2024: (Start)
T(n,k) = C(2^n-1,k) for k>=2^(n-1).
T(n,k) < C(2^n-1,k) for k<2^(n-1).
(Note: C(2^n-1,k) is the number of all k-subsets of P([n])\{{}}.) (End)

A102661 Triangle of partial sums of Stirling numbers of 2nd kind (A008277): T(n,k) = Sum_{i=1..k} Stirling2(n,i), 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 4, 5, 1, 8, 14, 15, 1, 16, 41, 51, 52, 1, 32, 122, 187, 202, 203, 1, 64, 365, 715, 855, 876, 877, 1, 128, 1094, 2795, 3845, 4111, 4139, 4140, 1, 256, 3281, 11051, 18002, 20648, 21110, 21146, 21147, 1, 512, 9842, 43947, 86472, 109299, 115179, 115929, 115974, 115975

Offset: 1

Vladeta Jovovic, Feb 03 2005

T(n,k) is the number of ways to place n distinguishable balls into k indistinguishable bins. - Geoffrey Critzer, Mar 22 2011
From Mark Wildon, Aug 10 2015: (Start)
T(n,k) is the number of partitions of a set of size n into at most k parts.
T(n,k) is the number of sequences of n top-to-random shuffles of a deck of k cards that leave the deck invariant.
T(n,k) =  where pi is the natural permutation character of the symmetric group Sym_k. This gives another combinatorial interpretation of T(n,k) as counting sequences of box moves on Young diagrams. Reference linked to below. (End)
Diagonal entries T(n,n) are the Bell numbers A000110. - Robert Israel, Aug 10 2015
From Manfred Boergens, Mar 18 2025: (Start)
The partitions in the second comment can be described as disjoint collections of subsets of [n] without the empty set with union = [n]. For instance, T(4,2)=8 is the number of partitions of [4] into 1 or 2 parts: 1234, 1 234, 2 134, 3 124, 4 123, 12 34, 13 24, 14 23.
For disjoint collections which may include one empty set see A381682.
For arbitrary collections without the empty set see A369950.
For arbitrary collections which may include one empty set see A381683. (End)

			Triangle begins:
  1;
  1,  2;
  1,  4,  5;
  1,  8, 14, 15;
  1, 16, 41, 51, 52;
  ...

Richard Stanley, Enumerative Combinatorics, Cambridge Univ. Press, 1997 page 38. (#7 of the twelvefold ways)

Reinhard Zumkeller, Rows n = 1..125 of triangle, flattened
John R. Britnell and Mark Wildon, Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and D, arXiv:1507.04803 [math.CO], 2015.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers

Cf. A000110, A008277, A008949, A048993, A049444.

Cf. A369950, A381682, A381683.

a102661 n k = a102661_tabl !! (n-1) !! (k-1)
a102661_row n = a102661_tabl !! (n-1)
a102661_tabl = map (scanl1 (+) . tail) $ tail a048993_tabl
-- Reinhard Zumkeller, Jun 19 2015

with(combinat): A102661_row := proc(n) local k,j; seq(add(stirling2(n,j),j=1..k),k=1..n) end:
seq(print(A102661_row(r)),r=1..6); # Peter Luschny, Sep 30 2011

Table[Table[Sum[StirlingS2[n, i], {i, 1, k}], {k, 1, n}], {n, 1,10}] // Grid (* Geoffrey Critzer, Mar 22 2011*)
Table[Accumulate[StirlingS2[n,Range[n]]],{n,10}]//Flatten (* Harvey P. Dale, Oct 28 2019 *)

tabl(nn) = {for (n=1, nn, for (k=1, n, print1(sum(i=1, k, stirling(n,i, 2)), ", ");); print(););} \\ Michel Marcus, Aug 10 2015

def T(n,k):
    return sum([stirling_number2(n,j) for j in range(1,k+1)])
# Danny Rorabaugh, Oct 13 2015

E.g.f. for row polynomials s(n,y) = Sum_{k=0..n} a(n,k)*y^k is (y*e^(e^(x*y)-1)- e^(y*(e^x-1)))/(y-1) - 1. - Robert Israel, Aug 10 2015

A381682 Triangle read by rows: T(n,k) = number of collections of up to k+1 disjoint subsets of [n] covering [n], with [0]={}, 0<=k<=n.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 5, 9, 10, 1, 9, 22, 29, 30, 1, 17, 57, 92, 103, 104, 1, 33, 154, 309, 389, 405, 406, 1, 65, 429, 1080, 1570, 1731, 1753, 1754, 1, 129, 1222, 3889, 6640, 7956, 8250, 8279, 8280, 1, 257, 3537, 14332, 29053, 38650, 41758, 42256, 42293, 42294

Offset: 0

Manfred Boergens, Mar 04 2025

Partial row sums of A256894.
For disjoint covers (collections without an empty set) see A102661.
For non-disjoint collections see A381683.
For non-disjoint covers see A369950.

			Triangle begins:
 1
 1   2
 1   3    4
 1   5    9    10
 1   9   22    29    30
 1  17   57    92   103   104
 1  33  154   309   389   405   406
 1  65  429  1080  1570  1731  1753  1754
 1 129 1222  3889  6640  7956  8250  8279  8280
 1 257 3537 14332 29053 38650 41758 42256 42293 42294
 ...
T(3,2)=9 is the number of disjoint [3]-covering collections of up to 3 subsets:
 {{1,2,3}}
 {{1,2,3},{}}
 {{1},{2,3}}
 {{2},{1,3}}
 {{3},{1,2}}
 {{1},{2},{3}}
 {{1},{2,3},{}}
 {{2},{1,3},{}}
 {{3},{1,2},{}}.

Cf. A186021 (diagonal).

Cf. A102661, A256894, A369950, A381683.

Table[If[n==0, 1, 2*Sum[StirlingS2[n, j], {j, k}] + StirlingS2[n, k+1]], {n, 0, 9}, {k, 0, n}] // Flatten

T(n,k) = 2*Sum_{j=1..k} S2(n,j) + S2(n,k+1) for n>=1.

T(0,k) = 1.

A381683 Triangle read by rows: T(n,k) = number of collections of up to k subsets of [n] covering [n], with [0]={}; n>=0, k=0..2^n.

Original entry on oeis.org

1, 2, 0, 1, 2, 0, 1, 5, 9, 10, 0, 1, 14, 58, 125, 181, 209, 217, 218, 0, 1, 41, 401, 1947, 6091, 13987, 25395, 38261, 49701, 57709, 62077, 63897, 64457, 64577, 64593, 64594, 0, 1, 122, 2802, 30352, 210448, 1076880, 4385616, 14839576, 42831176, 107303376, 236306016, 462089756, 809460556, 1280895556, 1846618196, 2447698581

Offset: 0

Manfred Boergens, Mar 04 2025

Partial row sums of A163353.
For covers (collections without an empty set) see A369950.
For disjoint collections see A381682.
For disjoint covers see A102661.

			Triangle begins:
  1 2
  0 1  2
  0 1  5   9   10
  0 1 14  58  125  181   209   217   218
  0 1 41 401 1947 6091 13987 25395 38261 49701 57709 62077 63897 64457 64577 64593 64594
  ...
T(3,2)=14 is the number of covering collections of 1 or 2 subsets of [3]:
  {{1,2,3}}
  {{},{1,2,3}}
  {{1},{2,3}}
  {{1},{1,2,3}}
  {{2},{1,3}}
  {{2},{1,2,3}}
  {{3},{1,2}}
  {{3},{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1,2},{1,2,3}}
  {{1,3},{1,2,3}}
  {{2,3},{1,2,3}}.

Cf. A000371 (diagonal).

Cf. A102661, A163353, A369950, A381682.

Table[Sum[Sum[(-1)^(n-i)*Binomial[n, i]*Binomial[2^i, j], {i, 0, n}], {j, 0, k}], {n, 0, 4}, {k, 0, 2^n}]//Flatten

T(n,k) = sum(j=0,k, sum(i=0,n, (-1)^(n-i)*binomial(n,i)*binomial(2^i,j)));
for(n=0,5,for(k=0,2^n,print1(T(n,k),", "))); \\ Joerg Arndt, Mar 04 2025

T(n,k) = Sum_{j=0..k} Sum_{i=0..n} (-1)^(n-i)*binomial(n,i)*binomial(2^i,j).

cp's OEIS Frontend

A003465 Number of ways to cover an n-set.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A055154 Triangle read by rows: T(n,k) = number of k-covers of a labeled n-set, k=1..2^n-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A102661 Triangle of partial sums of Stirling numbers of 2nd kind (A008277): T(n,k) = Sum_{i=1..k} Stirling2(n,i), 1<=k<=n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Sage

Formula

A381682 Triangle read by rows: T(n,k) = number of collections of up to k+1 disjoint subsets of [n] covering [n], with [0]={}, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A381683 Triangle read by rows: T(n,k) = number of collections of up to k subsets of [n] covering [n], with [0]={}; n>=0, k=0..2^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula