A family gamma of nonempty subsets of X whose union contains the given set X (and which contains no duplicated subsets) is called a cover (or covering) of X. For example, there is only a single cover of {1}, namely {{1}}. However, there are five covers of {1,2}, namely {{1},{2}}, {{1,2}}, {{1},{1,2}}, {{2},{1,2}}, and {{1},{2},{1,2}}.

A minimal cover is a cover for which removal of one member destroys the covering property. For example, of the five covers of {1,2}, only {{1},{2}} and {{1,2}} are minimal covers. There are various other types of specialized covers, including proper covers, antichain covers, k-covers, and k^*-covers (Macula 1994).

The number of possible covers for a set of N elements are

 |C(N)|=1/2sum_(k=0)^N(-1)^k(N; k)2^(2^(N-k)),

the first few of which are 1, 5, 109, 32297, 2147321017, 9223372023970362989, ... (OEIS A003465).

See also

Baseball Cover, Covering Map, Edge Cover, Lebesgue Covering Dimension, Minimal Cover, Minkowski Cover, Open Cover, Proper Cover, Universal Cover, Vertex Cover

Explore with Wolfram|Alpha


Eppstein, D. "Covering and Packing.", A. J. "Covers of a Finite Set." Math. Mag. 67, 141-144, 1994.Sloane, N. J. A. Sequences A003465/M4024 and A055621 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha


Cite this as:

Weisstein, Eric W. "Cover." From MathWorld--A Wolfram Web Resource.

Subject classifications