Editing Inclusion–exclusion principle (section)

==Examples==

<!--===Counting integers===
As a simple example of the use of the principle of inclusion–exclusion, consider the question:<ref>{{harvnb|Mazur|2010|loc=pp. 83–4, 88}}</ref>

:How many integers in {1, ..., 100} are not divisible by 2, 3 or 5?

Let ''S'' = {1,...,100} and ''P''<sub>1</sub> the property that an integer is divisible by 2, ''P''<sub>2</sub> the property that an integer is divisible by 3 and ''P''<sub>3</sub> the property that an integer is divisible by 5. Letting ''A''<sub>i</sub> be the subset of ''S'' whose elements have property ''P''<sub>i</sub> we have by elementary counting: |''A''<sub>1</sub>| = 50, |''A''<sub>2</sub>| = 33, and |''A''<sub>3</sub>| = 20. There are 16 of these integers divisible by 6, 10 divisible by 10, and 6 divisible by 15. Finally, there are just 3 integers divisible by 30, so the number of integers not divisible by any of 2, 3 or 5 is given by:

:100 − (50 + 33 + 20) + (16 + 10 + 6) − 3 = 26.-->

===Counting derangements===
A more complex example is the following.

Suppose there is a deck of ''n'' cards numbered from 1&nbsp;to&nbsp;''n''.  Suppose a card numbered ''m'' is in the correct position if it is the ''m<sup>th</sup>'' card in the deck. How many ways, ''W'', can the cards be shuffled with at least 1 card being in the correct position?

Begin by defining set ''A''<sub>''m''</sub>, which is all of the orderings of cards with the ''m<sup>th</sup>'' card correct.  Then the number of orders, ''W'', with ''at least'' one card being in the correct position, ''m'', is

: <math>W = \left|\bigcup_{m=1}^n A_m\right|.</math>

Apply the principle of inclusion–exclusion,

: <math>W = \sum_{m_1=1}^n |A_{m_1}| - \sum_{1 \leqslant m_1 < m_2 \leqslant n} |A_{m_1} \cap A_{m_2}| +\cdots + (-1)^{p-1} \sum_{1 \leqslant m_1 < \cdots < m_p \leqslant n} | A_{m_1} \cap \cdots \cap A_{m_p}| + \cdots</math>

Each value <math>A_{m_1} \cap \cdots \cap A_{m_p}</math> represents the set of shuffles having at least ''p'' values ''m''<sub>1</sub>,&nbsp;...,&nbsp;''m<sub>p</sub>'' in the correct position.  Note that the number of shuffles with at least ''p'' values correct only depends on ''p'', not on the particular values of <math>m</math>.  For example, the number of shuffles having the 1st, 3rd, and 17th cards in the correct position is the same as the number of shuffles having the 2nd, 5th, and 13th cards in the correct positions.  It only matters that of the ''n'' cards, 3 were chosen to be in the correct position.  Thus there are <math display="inline">{n \choose p}</math> equal terms in the ''p<sup>th</sup>'' summation (see [[combination]]).

:<math>W = {n \choose 1} |A_1| - {n \choose 2} |A_1 \cap A_2| + \cdots + (-1)^{p-1} {n \choose p} |A_1 \cap \cdots \cap A_p| + \cdots</math>

<math>|A_1 \cap \cdots \cap A_p|</math> is the number of orderings having ''p'' elements in the correct position, which is equal to the number of ways of ordering the remaining ''n''&nbsp;−&nbsp;''p'' elements, or (''n''&nbsp;−&nbsp;''p'')!. Thus we finally get:

: <math>\begin{align}
W &= {n \choose 1} (n-1)!  - {n \choose 2} (n-2)!  + \cdots + (-1)^{p-1} {n \choose p} (n-p)! + \cdots\\
&= \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)!  \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!(n-p)!} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}
\end{align}</math>

A permutation where ''no'' card is in the correct position is called a [[derangement]]. Taking ''n''! to be the total number of permutations, the probability ''Q'' that a random shuffle produces a derangement is given by

: <math>Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!}, </math>

a truncation to ''n''&nbsp;+&nbsp;1 terms of the [[Taylor series|Taylor expansion]] of ''e''<sup>−1</sup>. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately ''e''<sup>−1</sup> or 37%.