info prev up next book cdrom email home

Inclusion-Exclusion Principle

If $A_1$, ..., $A_k$ are finite sets, then

\begin{displaymath}
\left\vert{\,\bigcup_{i=1}^k A_i}\right\vert = \sum_{i=1}^k (-1)^{i+1} \xi_i,
\end{displaymath}

where $\xi_i$ is the sum of the Cardinalities of the intersections of the sets taken $i$ at a time.




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