HOME

TheInfoList



OR:

In
combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. ...
s; symbolically expressed as : , A \cup B, = , A, + , B, - , A \cap B, where ''A'' and ''B'' are two finite sets and , ''S'', indicates the
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of a set ''S'' (which may be considered as the number of elements of the set, if the set is finite). The formula expresses the fact that the sum of the sizes of the two sets may be too large since some elements may be counted twice. The double-counted elements are those in the
intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
of the two sets and the count is corrected by subtracting the size of the intersection. The inclusion-exclusion principle, being a generalization of the two-set case, is perhaps more clearly seen in the case of three sets, which for the sets ''A'', ''B'' and ''C'' is given by :, A \cup B \cup C, = , A, + , B, + , C, - , A \cap B, - , A \cap C, - , B \cap C, + , A \cap B \cap C, This formula can be verified by counting how many times each region in the
Venn diagram A Venn diagram is a widely used diagram style that shows the logical relation between sets, popularized by John Venn (1834–1923) in the 1880s. The diagrams are used to teach elementary set theory, and to illustrate simple set relationships ...
figure is included in the right-hand side of the formula. In this case, when removing the contributions of over-counted elements, the number of elements in the mutual intersection of the three sets has been subtracted too often, so must be added back in to get the correct total. Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of sets: # Include the cardinalities of the sets. # Exclude the cardinalities of the pairwise intersections. # Include the cardinalities of the triple-wise intersections. # Exclude the cardinalities of the quadruple-wise intersections. # Include the cardinalities of the quintuple-wise intersections. # Continue, until the cardinality of the -tuple-wise intersection is included (if is odd) or excluded ( even). The name comes from the idea that the principle is based on over-generous ''inclusion'', followed by compensating ''exclusion''. This concept is attributed to
Abraham de Moivre Abraham de Moivre FRS (; 26 May 166727 November 1754) was a French mathematician known for de Moivre's formula, a formula that links complex numbers and trigonometry, and for his work on the normal distribution and probability theory. He move ...
(1718), although it first appears in a paper of Daniel da Silva (1854) and later in a paper by J. J. Sylvester (1883). Sometimes the principle is referred to as the formula of Da Silva or Sylvester, due to these publications. The principle can be viewed as an example of the sieve method extensively used in
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathe ...
and is sometimes referred to as the ''sieve formula''. As finite probabilities are computed as counts relative to the cardinality of the
probability space In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models t ...
, the formulas for the principle of inclusion–exclusion remain valid when the cardinalities of the sets are replaced by finite probabilities. More generally, both versions of the principle can be put under the common umbrella of
measure theory In mathematics, the concept of a measure is a generalization and formalization of geometrical measures (length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simil ...
. In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix. This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. As
Gian-Carlo Rota Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, p ...
put it:
"One of the most useful principles of enumeration in discrete probability and combinatorial theory is the celebrated principle of inclusion–exclusion. When skillfully applied, this principle has yielded the solution to many a combinatorial problem."


Formula

In its general formula, the principle of inclusion–exclusion states that for finite sets , one has the identity This can be compactly written as :\left, \bigcup_^n A_i\ = \sum_^n (-1)^ \left( \sum_ , A_ \cap \cdots \cap A_ , \right) or :\left, \bigcup_^n A_i\ = \sum_(-1)^ \left , \bigcap_ A_j\. In words, to count the number of elements in a finite union of finite sets, first sum the cardinalities of the individual sets, then subtract the number of elements that appear in at least two sets, then add back the number of elements that appear in at least three sets, then subtract the number of elements that appear in at least four sets, and so on. This process always ends since there can be no elements that appear in more than the number of sets in the union. (For example, if n = 4, there can be no elements that appear in more than 4 sets; equivalently, there can be no elements that appear in at least 5 sets.) In applications it is common to see the principle expressed in its complementary form. That is, letting be a finite
universal set In set theory, a universal set is a set which contains all objects, including itself. In set theory as usually formulated, it can be proven in multiple ways that a universal set does not exist. However, some non-standard variants of set theory inc ...
containing all of the and letting \bar denote the complement of in , by De Morgan's laws we have :\left, \bigcap_^n \bar\ = \left, S - \bigcup_^n A_i \ =, S, - \sum_^n , A_i, + \sum_ , A_i\cap A_j, - \cdots + (-1)^n , A_1\cap\cdots\cap A_n, . As another variant of the statement, let be a list of properties that elements of a set may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements of which have none of the properties. Just let be the subset of elements of which have the property and use the principle in its complementary form. This variant is due to J. J. Sylvester. Notice that if you take into account only the first sums on the right (in the general form of the principle), then you will get an overestimate if is odd and an underestimate if is even.


Examples


Counting integers

As a simple example of the use of the principle of inclusion–exclusion, consider the question: :How many integers in are not divisible by 2, 3 or 5? Let ''S'' = and ''P''1 the property that an integer is divisible by 2, ''P''2 the property that an integer is divisible by 3 and ''P''3 the property that an integer is divisible by 5. Letting ''A''i be the subset of ''S'' whose elements have property ''P''i we have by elementary counting: , ''A''1, = 50, , ''A''2, = 33, and , ''A''3, = 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 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? Begin by defining set ''A''''m'', which is 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, \bigcup_^n A_m\. Apply the principle of inclusion–exclusion, : W = \sum_^n , A_, - \sum_ , A_ \cap A_, +\cdots + (-1)^ \sum_ , A_ \cap \cdots \cap A_, + \cdots Each value A_ \cap \cdots \cap A_ represents the set of shuffles having at least ''p'' values ''m''1, …, ''mp'' 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 m. 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 equal terms in the ''p''th summation (see
combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
). :W = , A_1, - , A_1 \cap A_2, + \cdots + (-1)^ , A_1 \cap \cdots \cap A_p, + \cdots , A_1 \cap \cdots \cap A_p, 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'' − ''p'' elements, or (''n'' − ''p'')!. Thus we finally get: : \begin W &= (n-1)! - (n-2)! + \cdots + (-1)^ (n-p)! + \cdots\\ &= \sum_^n (-1)^ (n-p)! \\ &= \sum_^n (-1)^ \frac (n-p)! \\ &= \sum_^n (-1)^ \frac \end A permutation where ''no'' card is in the correct position is called a
derangement In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements o ...
. Taking ''n''! to be the total number of permutations, the probability ''Q'' that a random shuffle produces a derangement is given by : Q = 1 - \frac = \sum_^n \frac, a truncation to ''n'' + 1 terms of the
Taylor expansion In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor seri ...
of ''e''−1. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately ''e''−1 or 37%.


A special case

The situation that appears in the derangement example above occurs often enough to merit special attention. Namely, when the size of the intersection sets appearing in the formulas for the principle of inclusion–exclusion depend only on the number of sets in the intersections and not on which sets appear. More formally, if the intersection :A_J:=\bigcap_ A_j has the same cardinality, say ''αk'' = , ''AJ'', , for every ''k''-element subset ''J'' of , then :\left , \bigcup_^n A_i\ =\sum_^n (-1)^\binom nk \alpha_k. Or, in the complementary form, where the universal set ''S'' has cardinality ''α''0, :\left , S \setminus \bigcup_^n A_i\ =\sum_^n (-1)^\binom nk \alpha_k.


Formula generalization

Given a family (repeats allowed) of subsets ''A''1, ''A''2, ..., ''A''n of a universal set ''S'', the principle of inclusion–exclusion calculates the number of elements of ''S'' in none of these subsets. A generalization of this concept would calculate the number of elements of ''S'' which appear in exactly some fixed ''m'' of these sets. Let ''N'' = /nowiki>''n''/nowiki> = . If we define A_ = S, then the principle of inclusion–exclusion can be written as, using the notation of the previous section; the number of elements of ''S'' contained in none of the ''A''i is: : \sum_ (-1)^ , A_J, . If ''I'' is a fixed subset of the index set ''N'', then the number of elements which belong to ''A''i for all ''i'' in ''I'' and for no other values is: : \sum_ (-1)^ , A_J, . Define the sets :B_k = A_ \text k \in N \setminus I. We seek the number of elements in none of the ''B''k which, by the principle of inclusion–exclusion (with B_\emptyset = A_I), is :\sum_ (-1)^, B_K, . The correspondence ''K'' ↔ ''J'' = ''I'' ∪ ''K'' between subsets of ''N'' \ ''I'' and subsets of ''N'' containing ''I'' is a bijection and if ''J'' and ''K'' correspond under this map then ''B''K = ''A''J, showing that the result is valid.


In probability

In
probability Probability is the branch of mathematics concerning numerical descriptions of how likely an event is to occur, or how likely it is that a proposition is true. The probability of an event is a number between 0 and 1, where, roughly speaking, ...
, for events ''A''1, ..., ''A''''n'' in a
probability space In probability theory, a probability space or a probability triple (\Omega, \mathcal, P) is a mathematical construct that provides a formal model of a random process or "experiment". For example, one can define a probability space which models t ...
(\Omega,\mathcal,\mathbb), the inclusion–exclusion principle becomes for ''n'' = 2 :\mathbb(A_1\cup A_2)=\mathbb(A_1)+\mathbb(A_2)-\mathbb(A_1\cap A_2), for ''n'' = 3 :\mathbb(A_1\cup A_2\cup A_3)=\mathbb(A_1)+\mathbb(A_2)+\mathbb(A_3)-\mathbb(A_1\cap A_2)-\mathbb(A_1\cap A_3)-\mathbb(A_2\cap A_3)+\mathbb(A_1\cap A_2\cap A_3) and in general :\mathbb\left(\bigcup_^n A_i\right)=\sum_^n \mathbb(A_i) -\sum_\mathbb(A_i\cap A_j)+\sum_\mathbb(A_i\cap A_j\cap A_k) + \cdots +(-1)^ \sum_\mathbb\left(\bigcap_^n A_i\right), which can be written in closed form as :\mathbb\left(\bigcup_^n A_i\right)=\sum_^n \left((-1)^\sum_ \mathbb(A_I)\right), where the last sum runs over all subsets ''I'' of the indices 1, …, ''n'' which contain exactly ''k'' elements, and :A_I:=\bigcap_ A_i denotes the intersection of all those ''Ai'' with index in ''I''. According to the Bonferroni inequalities, the sum of the first terms in the formula is alternately an upper bound and a lower bound for the LHS. This can be used in cases where the full formula is too cumbersome. For a general
measure space A measure space is a basic object of measure theory, a branch of mathematics that studies generalized notions of volumes. It contains an underlying set, the subsets of this set that are feasible for measuring (the -algebra) and the method that ...
(''S'',Σ,''μ'') and
measurable In mathematics, the concept of a measure is a generalization and formalization of geometrical measures ( length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many si ...
subsets ''A''1, …, ''A''''n'' of finite measure, the above identities also hold when the probability measure \mathbb is replaced by the measure ''μ''.


Special case

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersection ''A''''I'' only depends on the cardinality of ''I'', meaning that for every ''k'' in there is an ''ak'' such that :a_k=\mathbb(A_I) \text I\subset\ \text , I, =k, then the above formula simplifies to :\mathbb\left(\bigcup_^n A_i\right) =\sum_^n (-1)^\binom n k a_k due to the combinatorial interpretation of the binomial coefficient \binom nk. For example, if the events A_i are independent and identically distributed, then \mathbb(A_i) = p for all ''i'', and we have a_k = p^k, in which case the expression above simplifies to :\mathbb\left(\bigcup_^n A_i\right) = 1 - (1-p)^n. (This result can also be derived more simply by considering the intersection of the complements of the events A_i.) An analogous simplification is possible in the case of a general measure space and measurable subsets ''A''1, …, ''A''''n'' of finite measure.


Other formulas

The principle is sometimes stated in the form that says that if :g(A)=\sum_f(S) then The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (). If one sees a number n as a set of its prime factors, then () is a generalization of
Möbius inversion formula In mathematics, the classic Möbius inversion formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. It was introduced into number theory in 1832 by August Ferdinand Möbius. A large gener ...
for
square-free {{no footnotes, date=December 2015 In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''. ...
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
s. Therefore, () is seen as the Möbius inversion formula for the
incidence algebra In order theory, a field of mathematics, an incidence algebra is an associative algebra, defined for every locally finite partially ordered set and commutative ring with unity. Subalgebras called reduced incidence algebras give a natural construct ...
of the
partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary ...
of all subsets of ''A''. For a generalization of the full version of Möbius inversion formula, () must be generalized to multisets. For multisets instead of sets, () becomes where A - S is the multiset for which (A - S) \uplus S = A, and * ''μ''(''S'') = 1 if ''S'' is a set (i.e. a multiset without double elements) of even
cardinality In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
. * ''μ''(''S'') = −1 if ''S'' is a set (i.e. a multiset without double elements) of odd cardinality. * ''μ''(''S'') = 0 if ''S'' is a proper multiset (i.e. ''S'' has double elements). Notice that \mu(A - S) is just the (-1)^ of () in case A - S is a set.


Applications

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


Counting derangements

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting all
derangement In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, a derangement is a permutation that has no fixed points. The number of derangements o ...
s of a finite set. A ''derangement'' of a set ''A'' is a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
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''! / ''e''where 'x''denotes the nearest integer to ''x''; a detailed proof is available
here Here is an adverb that means "in, on, or at this place". It may also refer to: Software * Here Technologies, a mapping company * Here WeGo (formerly Here Maps), a mobile app and map website by Here Television * Here TV (formerly "here!"), a ...
and also see 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''." 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 \overline represent the complement of ''Ak'' with respect to some universal set ''A'' such that A_k \subseteq A for each ''k''. Then we have :\bigcap_^n A_i = \overline 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. A well known application of the principle is the construction of the chromatic polynomial of a graph.


Bipartite graph perfect matchings

The number of
perfect matching In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph , a perfect matching in is a subset of edge set , such that every vertex in the vertex set is adjacent to exactly ...
s of a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V a ...
can be calculated using the principle.


Number of onto functions

Given finite sets ''A'' and ''B'', how many
surjective function In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
s (onto functions) are there from ''A'' to ''B''? Without any loss of generality we may take ''A'' = and ''B'' = , since only the cardinalities of the sets matter. By using ''S'' as the set of all functions from ''A'' to ''B'', and defining, for each ''i'' in ''B'', the property ''Pi'' as "the function misses the element ''i'' in ''B''" (''i'' is not in the image of the function), the principle of inclusion–exclusion gives the number of onto functions between ''A'' and ''B'' as: :\sum_^ \binom (-1)^j (n-j)^k.


Permutations with forbidden positions

A permutation of the set ''S'' = 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'' = , 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 ''Ai'' be the set of positions that the element ''i'' is not allowed to be in, and the property ''P''''i'' to be the property that a permutation puts element ''i'' into a position in ''Ai'', the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions. In the given example, there are 12 = 2(3!) permutations with property ''P''1, 6 = 3! permutations with property ''P''2 and no permutations have properties ''P''3 or ''P''4 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''1 and ''P''2. There are no other non-zero contributions to the formula.


Stirling numbers of the second kind

The
Stirling numbers of the second kind In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \lef ...
, ''S''(''n'',''k'') count the number of 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 non-empty subsets). Using the universal set consisting of all partitions of the ''n''-set into ''k'' (possibly empty) distinguishable boxes, ''A''1, ''A''2, …, ''Ak'', and the properties ''Pi'' meaning that the partition has box ''Ai'' 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: :S(n,k) = \frac\sum_^k (-1)^t \binom k t (k-t)^n.


Rook polynomials

A rook polynomial is the
generating function In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
of the number of ways to place non-attacking 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 In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves va ...
, ''rk''(''B'') of ''xk'' in the rook polynomial ''RB''(''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 B' consisting of the squares of the rectangular board that are not in ''B''. This complementary board also has a rook polynomial R_(x) with coefficients r_k(B'). 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 ''rn''(''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 In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial :\begin (x)_n = x^\underline &= \overbrace^ \\ &= \prod_^n(x-k+1) = \prod_^(x-k) \,. \e ...
: :(m)_n = m(m-1)(m-2) \cdots (m-n+1). Letting ''P''i 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: : r_n(B) = \sum_^n (-1)^t (m-t)_ r_t(B').


Euler's phi function

Euler's totient or phi function, ''φ''(''n'') is an
arithmetic function In number theory, an arithmetic, arithmetical, or number-theoretic function is for most authors any function ''f''(''n'') whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their de ...
that counts the number of positive integers less than or equal to ''n'' that are
relatively prime In mathematics, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equivale ...
to ''n''. That is, if ''n'' is a
positive integer In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal ...
, 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 and define the property ''Pi'' to be that a number in ''S'' is divisible by the prime number ''pi'', for 1 ≤ ''i'' ≤ ''r'', where the
prime factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are s ...
of :n = p_1^ p_2^ \cdots p_r^. Then, :\varphi(n) = n - \sum_^r \frac + \sum_ \frac - \cdots = n \prod_^r \left (1 - \frac \right ).


Diluted inclusion–exclusion principle

In many cases where the principle could give an exact formula (in particular, counting
prime number A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
s using the
sieve of Eratosthenes In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime ...
), the formula arising does not offer useful content because the number of terms in it is excessive. If each term individually can be estimated accurately, the accumulation of errors may imply that the inclusion–exclusion formula is not directly applicable. In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mathe ...
, this difficulty was addressed by Viggo Brun. After a slow start, his ideas were taken up by others, and a large variety of sieve methods developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula. Let ''A''1, ..., ''A''''n'' be arbitrary sets and ''p''1, …, ''p''''n'' real numbers in the closed unit interval . Then, for every even number ''k'' in , the
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
s satisfy the inequality: : 1_ \ge \sum_^k (-1)^\sum_ p_ \dots p_ \, 1_.


Proof of main statement

Choose an element contained in the union of all sets and let A_1, A_2, \dots, A_t be the individual sets containing it. (Note that ''t'' > 0.) Since the element is counted precisely once by the left-hand side of equation (), we need to show that it is counted precisely once by the right-hand side. On the right-hand side, the only non-zero contributions occur when all the subsets in a particular term contain the chosen element, that is, all the subsets are selected from A_1, A_2, \dots, A_t. The contribution is one for each of these sets (plus or minus depending on the term) and therefore is just the (signed) number of these subsets used in the term. We then have: :\begin , \, &- , \, + \cdots + (-1)^, \, = \binom - \binom + \cdots + (-1)^\binom. \end By the
binomial theorem In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial into a sum involving terms of the form , where the ...
, : 0 = (1-1)^t= \binom - \binom + \binom - \cdots + (-1)^t\binom. Using the fact that \binom = 1 and rearranging terms, we have :1 = \binom - \binom + \cdots + (-1)^\binom, and so, the chosen element is counted only once by the right-hand side of equation ().


Algebraic proof

An algebraic proof can be obtained using
indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x\i ...
s (also known as characteristic functions). The indicator function of a subset ''S'' of a set ''X'' is the function :\begin &\mathbf_S: X \to \ \\ &\mathbf_S(x) = \begin 1 & x \in S\\ 0 & x \notin S \end \end If A and B are two subsets of X, then :\mathbf_A \cdot\mathbf_B = \mathbf_. Let ''A'' denote the union \bigcup_^n A_i of the sets ''A''1, …, ''An''. To prove the inclusion–exclusion principle in general, we first verify the identity for indicator functions, where: :A_I = \bigcap_ A_i. The following function :\left (\mathbf_A-\mathbf_ \right )\left (\mathbf_A-\mathbf_ \right )\cdots \left (\mathbf_A-\mathbf_ \right ), is identically zero because: if ''x'' is not in ''A'', then all factors are 0 − 0 = 0; and otherwise, if ''x'' does belong to some ''Am'', then the corresponding ''m''th factor is 1 − 1 = 0. By expanding the product on the left-hand side, equation () follows. To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation () over all ''x'' in the union of ''A''1, …, ''An''. To derive the version used in probability, take the expectation in (). In general, integrate the equation () with respect to ''μ''. Always use linearity in these derivations.


See also

* * * * * *


Notes


References

* * * * * * * * * * * * {{DEFAULTSORT:Inclusion-exclusion principle Enumerative combinatorics Probability theory Articles containing proofs Mathematical principles