| Prinple of Inclusion and Exclusion |
|---|
The principle og inclusion and exclusion (PIE for short) is one of the most common and intuitive enumeration procedures. It is a straightforward generalization of the familiar method of obtaining the number of elements in the union of two finite sets:
\[
\left\vert A \cup B \right\vert = \left\vert A \right\vert +
\left\vert B \right\vert - \left\vert A \cap B \right\vert ,
\]
where A and B are two finite sets and |S| indicates the cardinality of a set S
(which may be considered as the number of elements of the set, if the set is
finite).
The principle is more clearly seen in the case of three sets, which for the sets A, B, and C is given by
\[
\left\vert A \cup B \cup C \right\vert = \left\vert A \right\vert +
\left\vert B \right\vert + \left\vert C \right\vert -
\left\vert A \cap B \right\vert - \left\vert A \cap C \right\vert -
\left\vert B \cap C \right\vert +
\left\vert A \cap B \cap C \right\vert .
\]
A derangement
is a permutation of the elements of a set, such that no element appears in
its original position. In other words, derangement is a permutation that has
no fixed points.
▣
Example:
Suppose there is a deck of n cards (or any distinguishing objects)
numbered from 1 to n. Suppose a card numbered m is in the
correct position if it is the m-th card in the deck. How many ways,
W, can the cards be shuffled with at least 1 card being in the correct
position?
Let Wm denote the set of all of the orderings of cards with the m-th card correct. Then the number of orders, W, with at least one card being in the correct position, m, is
\[
W = \left\vert \cup_{m=1}^n A_m \right\vert .
\]
Apply the principle of inclusion–exclusion, we get
\[
W = \sum_{m_1 =1}^n \left\vert A_{m_1} \right\vert -
\sum_{1 \le m_1 < m_2 \le n} \left\vert A_{m_1} \cap A_{m_2} \right\vert +
\cdots + (-1)^{p+1} \sum_{1 \le m_1 < \cdots < m_p \le n}
\left\vert A_{m_1} \cap A_{m_2} \cap \cdots \cap A_{m_p} \right\vert +
\cdots .
\]
■
- Dobrushkin, V.A., Methods in Algorithmic Analysis, CRC Press, FL, 2010.