info prev up next book cdrom email home


A group $C$ of Subsets of $X$ whose Union contains the given set $X$ ( $\cup \{S:S\in C\}=X$) is called a cover (or a Covering). A Minimal Cover is a cover for which removal of one member destroys the covering property. There are various types of specialized covers, including proper covers, antichain covers, minimal covers, $k$-covers, and $k^*$-covers. The number of possible covers for a set of $N$ elements is

\vert C(N)\vert = {1\over 2} \sum_{k=0}^N (-1)^k{N\choose k}2^{2^{N-k}},

the first few of which are 1, 5, 109, 32297, 2147321017, 9223372023970362989, ... (Sloane's A003465). The number of proper covers for a set of $N$ elements is
$\displaystyle \vert C'(N)\vert$ $\textstyle =$ $\displaystyle \vert C(N)\vert-{\textstyle{1\over 4}}2^{2^N}$  
  $\textstyle =$ $\displaystyle \left[{{1\over 2} \sum_{k=0}^N (-1)^k{N\choose k}2^{2^{N-k}}}\right]-{2^{2^N}\over 4},$  

the first few of which are 0, 1, 45, 15913, 1073579193, ... (Sloane's A007537).

See also Minimal Cover


Eppstein, D. ``Covering and Packing.''

Macula, A. J. ``Covers of a Finite Set.'' Math. Mag. 67, 141-144, 1994.

Sloane, N. J. A. Sequences A003465/M4024 and A007537/M5287 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

© 1996-9 Eric W. Weisstein