info prev up next book cdrom email home

Minimal Cover

A minimal cover is a Cover for which removal of one member destroys the covering property. Let $\mu(n,k)$ be the number of minimal covers of $\{1, \ldots, n\}$ with $k$ members. Then

\begin{displaymath}
\mu(n,k)={1\over k!} \sum_{m=k}^{\alpha_k} {2^k-k-1\choose m-k}m! s(n,m),
\end{displaymath}

where ${n\choose k}$ is a Binomial Coefficient, $s(n,m)$ is a Stirling Number of the Second Kind, and

\begin{displaymath}
\alpha_k={\rm min}(n,2^k-1).
\end{displaymath}

Special cases include $\mu(n,1)=1$ and $\mu(n,2)=s(n+1,3)$.

$n$ $k=1$ $k=2$ $k=3$ $k=4$ $k=5$ $k=6$ $k=7$
Sloane   Sloane's A000392 Sloane's A003468 Sloane's A016111      
1 1            
2 1 1          
3 1 6 1        
4 1 25 22 1      
5 1 90 305 65 1    
6 1 301 3410 2540 171 1  
7 1 966 33621 77350 17066 420 1

See also Cover, Lew k-gram, Stirling Number of the Second Kind


References

Hearne, T. and Wagner, C. ``Minimal Covers of Finite Sets.'' Disc. Math. 5, 247-251, 1973.

Macula, A. J. ``Lewis Carroll and the Enumeration of Minimal Covers.'' Math. Mag. 68, 269-274, 1995.




© 1996-9 Eric W. Weisstein
1999-05-26