Editing Inclusion–exclusion principle (section)

==Applications==

The inclusion–exclusion principle is widely used and only a few of its applications can be mentioned here.

===Counting derangements===

{{main|Derangement}}

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting all [[derangement]]s of a finite set. A ''derangement'' of a set ''A'' is a [[bijection]] from ''A'' into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality of ''A'' is ''n'', then the number of derangements is [''n''!&nbsp;/&nbsp;''e''] where [''x''] denotes the [[nearest integer function|nearest integer]] to ''x''; a detailed proof is available [[Random permutation statistics#Number of permutations that are derangements|here]] and also see [[#Examples|the examples section]] above.

The first occurrence of the problem of counting the number of derangements is in an early book on games of chance: ''Essai d'analyse sur les jeux de hazard'' by P. R. de Montmort (1678 – 1719) and was known as either "Montmort's problem" or by the name he gave it, "''problème des rencontres''."<ref>{{harvnb|van Lint|Wilson|1992|loc=pp. 77-8}}</ref> The problem is also known as the ''hatcheck problem.''

The number of derangements is also known as the [[subfactorial]] of ''n'', written !''n''. It follows that if all bijections are assigned the same probability then the probability that a random bijection is a derangement quickly approaches 1/''e'' as ''n'' grows.

===Counting intersections===
The principle of inclusion–exclusion, combined with [[De Morgan's law]], can be used to count the cardinality of the intersection of sets as well. Let <math>\overline{A_k}</math> represent the complement of ''A<sub>k</sub>'' with respect to some universal set ''A'' such that <math>A_k \subseteq A</math> for each ''k''. Then we have

:<math>\bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A_i}}</math>

thereby turning the problem of finding an intersection into the problem of finding a union.

===Graph coloring===
The inclusion exclusion principle forms the basis of algorithms for a number of NP-hard graph partitioning problems, such as [[graph coloring]].<ref name="bhk">{{harvnb|Björklund|Husfeldt|Koivisto|2009}}</ref>

A well known application of the principle is the construction of the [[chromatic polynomial]] of a graph.<ref>{{harvnb|Gross|2008|loc=pp. 211–13}}</ref>

===Bipartite graph perfect matchings===
The number of [[perfect matching]]s of a [[bipartite graph]] can be calculated using the principle.<ref>{{harvnb|Gross|2008|loc=pp. 208–10}}</ref>

===Number of onto functions===
Given finite sets ''A'' and ''B'', how many [[surjective function]]s (onto functions) are there from ''A'' to ''B''? [[Without any loss of generality]] we may take ''A'' = {1, ..., ''k''} and ''B'' = {1, ..., ''n''}, since only the cardinalities of the sets matter. By using ''S'' as the set of all [[Function (mathematics)|functions]] from ''A'' to ''B'', and defining, for each ''i'' in ''B'', the property ''P<sub>i</sub>'' as "the function misses the element ''i'' in ''B''" (''i'' is not in the [[Image (mathematics)|image]] of the function), the principle of inclusion&ndash;exclusion gives the number of onto functions between ''A'' and ''B'' as:<ref>{{harvnb|Mazur|2010|loc=pp.84-5, 90}}</ref>

:<math>\sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.</math>

===Permutations with forbidden positions===
A [[permutation]] of the set ''S'' = {1, ..., ''n''} where each element of ''S'' is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements of ''S'') is called a ''permutation with forbidden positions''. For example, with ''S'' = {1,2,3,4}, the permutations with the restriction that the element 1 can not be in positions 1 or 3, and the element 2 can not be in position 4 are: 2134, 2143, 3124, 4123, 2341, 2431, 3241, 3421, 4231 and 4321. By letting ''A<sub>i</sub>'' be the set of positions that the element ''i'' is not allowed to be in, and the property ''P''<sub>''i''</sub> to be the property that a permutation puts element ''i'' into a position in ''A<sub>i</sub>'', the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions.<ref>{{harvnb|Brualdi|2010|loc=pp. 177–81}}</ref>

In the given example, there are 12 = 2(3!) permutations with property ''P''<sub>1</sub>, 6 = 3! permutations with property ''P''<sub>2</sub> and no permutations have properties ''P''<sub>3</sub> or ''P''<sub>4</sub> as there are no restrictions for these two elements. The number of permutations satisfying the restrictions is thus:

:4! − (12 + 6 + 0 + 0) + (4) = 24 − 18 + 4 = 10.

The final 4 in this computation is the number of permutations having both properties ''P''<sub>1</sub> and ''P''<sub>2</sub>. There are no other non-zero contributions to the formula.

===Stirling numbers of the second kind===
{{main|Stirling numbers of the second kind}}

The [[Stirling numbers of the second kind]], ''S''(''n'',''k'') count the number of [[Partition of a set|partitions]] of a set of ''n'' elements into ''k'' non-empty subsets (indistinguishable ''boxes''). An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an ''n''-set into ''k'' non-empty but distinguishable boxes ([[Ordered set|ordered]] non-empty subsets). Using the universal set consisting of all partitions of the ''n''-set into ''k'' (possibly empty) distinguishable boxes, ''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A<sub>k</sub>'', and the properties ''P<sub>i</sub>'' meaning that the partition has box ''A<sub>i</sub>'' empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by ''k''! to remove the artificial ordering gives the Stirling number of the second kind:<ref>{{harvnb|Brualdi|2010|loc=pp. 282&ndash;7}}</ref>

:<math>S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.</math>

===Rook polynomials===
{{main|Rook polynomial}}

A rook polynomial is the [[generating polynomial|generating function]] of the number of ways to place non-attacking [[rook (chess)|rooks]] on a ''board B'' that looks like a subset of the squares of a [[checkerboard]]; that is, no two rooks may be in the same row or column. The board ''B'' is any subset of the squares of a rectangular board with ''n'' rows and ''m'' columns; we think of it as the squares in which one is allowed to put a rook. The [[coefficient]], ''r<sub>k</sub>''(''B'') of ''x<sup>k</sup>'' in the rook polynomial ''R<sub>B</sub>''(''x'') is the number of ways ''k'' rooks, none of which attacks another, can be arranged in the squares of ''B''. For any board ''B'', there is a complementary board <math>B'</math> consisting of the squares of the rectangular board that are not in ''B''. This complementary board also has a rook polynomial <math>R_{B'}(x)</math> with coefficients <math>r_k(B').</math>

It is sometimes convenient to be able to calculate the highest coefficient of a rook polynomial in terms of the coefficients of the rook polynomial of the complementary board. Without loss of generality we can assume that ''n'' ≤ ''m'', so this coefficient is ''r<sub>n</sub>''(''B''). The number of ways to place ''n'' non-attacking rooks on the complete ''n'' × ''m'' "checkerboard" (without regard as to whether the rooks are placed in the squares of the board ''B'') is given by the [[falling factorial]]:

:<math>(m)_n = m(m-1)(m-2) \cdots (m-n+1).</math>

Letting ''P''<sub>i</sub> be the property that an assignment of ''n'' non-attacking rooks on the complete board has a rook in column ''i'' which is not in a square of the board ''B'', then by the principle of inclusion–exclusion we have:<ref>{{harvnb|Roberts|Tesman|2009|loc=pp.419–20}}</ref>

:<math> r_n(B) = \sum_{t=0}^n (-1)^t (m-t)_{n-t} r_t(B'). </math>

===Euler's phi function===
{{main|Euler's totient function}}

Euler's totient or phi function, ''φ''(''n'') is an [[arithmetic function]] that counts the number of positive integers less than or equal to ''n'' that are [[relatively prime]] to ''n''. That is, if ''n'' is a [[positive integer]], then φ(''n'') is the number of integers ''k'' in the range 1 ≤ ''k'' ≤ ''n'' which have no common factor with ''n'' other than 1. The principle of inclusion–exclusion is used to obtain a formula for φ(''n''). Let ''S'' be the set {1, ..., ''n''} and define the property ''P<sub>i</sub>'' to be that a number in ''S'' is divisible by the prime number ''p<sub>i</sub>'', for 1 ≤ ''i'' ≤ ''r'', where the [[prime factorization]] of

:<math>n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.</math>

Then,<ref>{{harvnb|van Lint|Wilson|1992|loc=pg. 73}}</ref>

:<math>\varphi(n) = n - \sum_{i=1}^r \frac{n}{p_i} + \sum_{1 \leqslant i < j \leqslant r} \frac{n}{p_i p_j} - \cdots = n \prod_{i=1}^r \left (1 - \frac{1}{p_i} \right ).</math>

===Dirichlet hyperbola method===
{{main|Dirichlet hyperbola method}}

[[File:Dirichlet hyperbola example_4.svg|thumb|An example of the Dirichlet hyperbola method with <math>n = 10,</math> <math>a \approx 2.7,</math> and <math>b \approx 3.7.</math>]]

The Dirichlet hyperbola method re-expresses a sum of a [[multiplicative function]] <math>f(n)</math> by selecting a suitable [[Dirichlet convolution]] <math>f = g \ast h</math>, recognizing that the sum

: <math>F(n) = \sum_{k=1}^n f(k) = \sum_{k=1}^n \sum_{xy=k}^{} g(x) h(y)</math>

can be recast as a sum over the [[lattice points]] in a region bounded by <math>x \geq 1</math>, <math>y \geq 1</math>, and <math>xy \leq n</math>, splitting this region into two overlapping subregions, and finally using the inclusion–exclusion principle to conclude that

: <math>F(n) = \sum_{k=1}^n f(k)
= \sum_{k=1}^n \sum_{xy=k}^{} g(x)h(y)
= \sum_{x=1}^a \sum_{y=1}^{n/x} g(x)h(y) + \sum_{y=1}^b \sum_{x=1}^{n/y} g(x)h(y) - \sum_{x=1}^a \sum_{y=1}^b g(x)h(y).</math>