Inclusion-exclusion principle


Inclusion-exclusion principle

In combinatorial mathematics, the inclusion-exclusion principle (also known as the sieve principle) states that if "A"1, ..., "A""n" are finite sets, then

:egin{align}iggl|igcup_{i=1}^n A_iiggr| & {} =sum_{i=1}^nleft|A_i ight
-sum_{i,j,:,1 le i < j le n}left|A_icap A_j ight| \& {}qquad +sum_{i,j,k,:,1 le i < j < k le n}left|A_icap A_jcap A_k ight|- cdots + left(-1 ight)^{n-1} left|A_1capcdotscap A_n ight
end{align}

where |"A"| denotes the cardinality of the set "A". For example, taking "n" = 2, we get a special case of double counting; in words: we can count the size of the union of sets "A" and "B" by adding |"A"| and |"B"| and then subtracting the size of their intersection. The name comes from the idea that the principle is based on over-generous "inclusion", followed by compensating "exclusion". When "n" > 2 the exclusion of the pairwise intersections is (possibly) too severe, and the correct formula is as shown with alternating signs.

This formula is attributed to Abraham de Moivre; it is sometimes also named for Joseph Sylvester or Henri Poincaré.fact|date=October 2007

For the case of three sets "A", "B", "C" the inclusion-exclusion principle is illustrated in the graphic on the right.

Inclusion-exclusion principle in probability

In probability, for events "A"1, ..., "A""n" in a probability space scriptstyle(Omega,mathcal{F},mathbb{P}), the inclusion-exclusion principle becomes for "n" = 2

:mathbb{P}(A_1cup A_2)=mathbb{P}(A_1)+mathbb{P}(A_2)-mathbb{P}(A_1cap A_2),

for "n" = 3

:egin{align}mathbb{P}(A_1cup A_2cup A_3)&=mathbb{P}(A_1)+mathbb{P}(A_2)+mathbb{P}(A_3)\&qquad-mathbb{P}(A_1cap A_2)-mathbb{P}(A_1cap A_3)-mathbb{P}(A_2cap A_3)+mathbb{P}(A_1cap A_2cap A_3)end{align}

and in general

:egin{align}mathbb{P}iggl(igcup_{i=1}^n A_iiggr) & {} =sum_{i=1}^n mathbb{P}(A_i)-sum_{i,j,:,i

which can be written in closed form as

:mathbb{P}iggl(igcup_{i=1}^n A_iiggr) =sum_{k=1}^n (-1)^{k-1}sum_{scriptstyle Isubset{1,ldots,n}atopscriptstyle|I|=k} mathbb{P}iggl(igcap_{iin I} A_iiggr),

where the last sum runs over all subsets "I" of the indices 1, ..., "n" which contain exactly "k" elements.

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 ("S","Σ","μ") and measurable subsets "A"1, ..., "An" of finite measure, the above identities also hold when the probability measure mathbb{P} is replaced by the measure "μ".

Proof

To prove the inclusion-exclusion principle in general, we first have to verify the identity

:1_{cup_{i=1}^n A_i} =sum_{k=1}^n (-1)^{k-1}sum_{scriptstyle Isubset{1,ldots,n}atopscriptstyle|I|=k} 1_{cap_{iin I} A_i}qquad(*)

for indicator functions. There are at least two ways to do this:

First possibility: If suffices to do this for every "x" in the union of "A"1, ..., "An". Suppose "x" belongs to exactly "m" sets with 1 ≤ "m" ≤ "n", for simplicity of notation say "A"1, ..., "Am". Then the identity at "x" reduces to

:1 =sum_{k=1}^m (-1)^{k-1}sum_{scriptstyle Isubset{1,ldots,m}atopscriptstyle|I|=k} 1.

The number of subsets of cardinality "k" of an "m"-element set is the combinatorical interpretation of the binomial coefficient extstyleinom mk . Since extstyle1=inom m0 , we have

:inom m0 =sum_{k=1}^m (-1)^{k-1}inom mk.

Putting all terms to the left-hand side of the equation, we obtain the expansion for (1 – 1)"m" given by the binomial theorem, hence we see that (*) is true for "x".

Second possibility: Let "A" denote the union of the sets "A"1, ..., "An". Then

:0=(1_A-1_{A_1})(1_A-1_{A_2})cdots(1_A-1_{A_n}),,

because both sides are zero for an "x" not in "A", and if "x" belongs to one of the sets, say "Am", then the corresponding "m"th factor is zero. By expanding the product on the right-hand side, equation (*) follows.

Use of (*): To prove the inclusion-exclusion principle for the cardinality of sets, sum the equation (*) over all "x" in the union of "A"1, ..., "A""n". To derive the version used in probability, take the expectation in (*). In general, integrate the equation (*) with respect to "μ". Always use linearity.

Other forms

The principle is sometimes stated in the form that says that if

:g(A)=sum_{S,:,Ssubseteq A}f(S)

then

:f(A)=sum_{S,:,Ssubseteq A}(-1)^{left|A ight|-left|S ightg(S)

In that form it is seen to be the Möbius inversion formula for the incidence algebra of the partially ordered set of all subsets of "A".

Applications

In many cases where the principle could give an exact formula (in particular, counting prime numbers using the sieve of Eratosthenes), the formula arising doesn't 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 isn't directly applicable. In number theory, 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.

Derangements

A well-known application of the inclusion-exclusion principle is to the combinatorial problem of counting all derangements 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"! / "e"] where ["x"] denotes the nearest integer to "x"; a detailed proof is available here.

This 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 theorem, can be used to count the intersection of sets as well. Let scriptstyleoverline{A}_k represent the complement of "A""k" with respect to some universal set "A" such that scriptstyle A_k, subseteq, A for each "k". Then we have

: igcap_{i=1}^n A_i = overline{igcup_{i=1}^n overline{A}_i}

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

ee also

* Combinatorial principles
* Boole's inequality
* Necklace problem
* Schuette–Nesbitt formula
* Maximum-minimums identity

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Inclusion — For inclusion and exclusion of Wikipedia templates, see Wikipedia:Template inclusion. Inclusion may refer to: Contents 1 Metallurgy 2 Social inclusion of persons 3 Mathematics …   Wikipedia

  • Combinatorial principles — In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used. The rule of sum, rule of product, and inclusion exclusion principle are often used for enumerative purposes.… …   Wikipedia

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Bernoulli number — In mathematics, the Bernoulli numbers Bn are a sequence of rational numbers with deep connections to number theory. They are closely related to the values of the Riemann zeta function at negative integers. There are several conventions for… …   Wikipedia

  • Derangement — For the psychological condition, see psychosis. Number of possible permutations and derangements of n elements. P(n) is the number of n permutations; D(n) is the number of derangements (n permutations where all of the n elements change their… …   Wikipedia

  • Boole's inequality — In probability theory, Boole s inequality, named after George Boole, (also known as the union bound) says that for any finite or countable set of events, the probability that at least one of the events happens is no greater than the sum of the… …   Wikipedia

  • Schuette–Nesbitt formula — In probability theory, the Schuette–Nesbitt formula is a generalization of the probabilistic version of the inclusion exclusion principle. It is named after Donald R. Schuette and Cecil J. Nesbitt. The Schuette–Nesbitt formula has practical… …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • Logical connective — This article is about connectives in classical logic. For connectors in natural languages, see discourse connective. For connectives and operators in other logics, see logical constant. For other logical symbols, see table of logic symbols. In… …   Wikipedia

  • List of mathematics articles (I) — NOTOC Ia IA automorphism ICER Icosagon Icosahedral 120 cell Icosahedral prism Icosahedral symmetry Icosahedron Icosian Calculus Icosian game Icosidodecadodecahedron Icosidodecahedron Icositetrachoric honeycomb Icositruncated dodecadodecahedron… …   Wikipedia