Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Inclusion–exclusion principle

From Wikipedia, the free encyclopedia
Counting technique in combinatorics
Venn diagram showing the union of setsA andB as everything not in white

Incombinatorics, theinclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in theunion of twofinite sets; symbolically expressed as

|A∪B|=|A|+|B|−|A∩B|{\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}

whereA andB are two finite sets and |S| indicates thecardinality of a setS (which may be considered as the number of elements of the set, if the set isfinite). 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 theintersection 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 setsA,B andC is given by

|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|{\displaystyle |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 theVenn diagram 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.

Inclusion–exclusion illustrated by a Venn diagram for three sets

Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union ofn sets:

  1. Include the cardinalities of the sets.
  2. Exclude the cardinalities of the pairwise intersections.
  3. Include the cardinalities of the triple-wise intersections.
  4. Exclude the cardinalities of the quadruple-wise intersections.
  5. Include the cardinalities of the quintuple-wise intersections.
  6. Continue, until the cardinality of then-tuple-wise intersection is included (ifn is odd) or excluded (n even).

The name comes from the idea that the principle is based on over-generousinclusion, followed by compensatingexclusion.This concept is attributed toAbraham de Moivre (1718),[1] although it first appears in a paper ofDaniel da Silva (1854)[2] and later in a paper byJ. J. Sylvester (1883).[3] 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 thesieve method extensively used innumber theory and is sometimes referred to as thesieve formula.[4]

As finite probabilities are computed as counts relative to the cardinality of theprobability space, 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 ofmeasure theory.

In a very abstract setting, the principle of inclusion–exclusion can be expressed as the calculation of the inverse of a certain matrix.[5] This inverse has a special structure, making the principle an extremely valuable technique in combinatorics and related areas of mathematics. AsGian-Carlo Rota put it:[6]

"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

[edit]

In its general formula, the principle of inclusion–exclusion states that for finite setsA1, ...,An, one has the identity

|⋃i=1nAi|=∑i=1n|Ai|−∑1⩽i<j⩽n|Ai∩Aj|+∑1⩽i<j<k⩽n|Ai∩Aj∩Ak|−⋯+(−1)n+1|A1∩⋯∩An|.{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|.}1
Each term of the inclusion–exclusion formula gradually corrects the count until finally each portion of theVenn diagram is counted exactly once.

This can be compactly written as

|⋃i=1nAi|=∑k=1n(−1)k+1(∑1⩽i1<⋯<ik⩽n|Ai1∩⋯∩Aik|){\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{1\leqslant i_{1}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)}

or

|⋃i=1nAi|=∑∅≠J⊆{1,…,n}(−1)|J|+1|⋂j∈JAj|.{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{\emptyset \neq J\subseteq \{1,\ldots ,n\}}(-1)^{|J|+1}\left|\bigcap _{j\in J}A_{j}\right|.}

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, ifn=4,{\displaystyle n=4,} there can be no elements that appear in more than4{\displaystyle 4} sets; equivalently, there can be no elements that appear in at least5{\displaystyle 5} sets.)

In applications it is common to see the principle expressed in its complementary form. That is, lettingS be a finiteuniversal set containing all of theAi and lettingAi¯{\displaystyle {\bar {A_{i}}}} denote the complement ofAi inS, byDe Morgan's laws we have

|⋂i=1nAi¯|=|S−⋃i=1nAi|=|S|−∑i=1n|Ai|+∑1⩽i<j⩽n|Ai∩Aj|−⋯+(−1)n|A1∩⋯∩An|.{\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.}

As another variant of the statement, letP1, ...,Pn be a list of properties that elements of a setS may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements ofS that have none of the properties. Just letAi be the subset of elements ofS which have the propertyPi and use the principle in its complementary form. This variant is due toJ. J. Sylvester.[1]

Notice that if you take into account only the firstm<n sums on the right (in the general form of the principle), then you will get an overestimate ifm is odd and an underestimate ifm is even.

Examples

[edit]

Counting derangements

[edit]

A more complex example is the following.

Suppose there is a deck ofn cards numbered from 1 to n. Suppose a card numberedm is in the correct position if it is themth 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 setAm, which is all of the orderings of cards with themth card correct. Then the number of orders,W, withat least one card being in the correct position,m, is

W=|⋃m=1nAm|.{\displaystyle W=\left|\bigcup _{m=1}^{n}A_{m}\right|.}

Apply the principle of inclusion–exclusion,

W=∑m1=1n|Am1|−∑1⩽m1<m2⩽n|Am1∩Am2|+⋯+(−1)p−1∑1⩽m1<⋯<mp⩽n|Am1∩⋯∩Amp|+⋯{\displaystyle 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 }

Each valueAm1∩⋯∩Amp{\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}} represents the set of shuffles having at leastp valuesm1, ..., mp in the correct position. Note that the number of shuffles with at leastp values correct only depends onp, not on the particular values ofm{\displaystyle 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 then cards, 3 were chosen to be in the correct position. Thus there are(np){\textstyle {n \choose p}} equal terms in thepth summation (seecombination).

W=(n1)|A1|−(n2)|A1∩A2|+⋯+(−1)p−1(np)|A1∩⋯∩Ap|+⋯{\displaystyle 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 }

|A1∩⋯∩Ap|{\displaystyle |A_{1}\cap \cdots \cap A_{p}|} is the number of orderings havingp elements in the correct position, which is equal to the number of ways of ordering the remainingn − p elements, or (n − p)!. Thus we finally get:

W=(n1)(n−1)!−(n2)(n−2)!+⋯+(−1)p−1(np)(n−p)!+⋯=∑p=1n(−1)p−1(np)(n−p)!=∑p=1n(−1)p−1n!p!(n−p)!(n−p)!=∑p=1n(−1)p−1n!p!{\displaystyle {\begin{aligned}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{aligned}}}

A permutation whereno card is in the correct position is called aderangement. Takingn! to be the total number of permutations, the probabilityQ that a random shuffle produces a derangement is given by

Q=1−Wn!=∑p=0n(−1)pp!,{\displaystyle Q=1-{\frac {W}{n!}}=\sum _{p=0}^{n}{\frac {(-1)^{p}}{p!}},}

a truncation ton + 1 terms of theTaylor expansion ofe−1. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximatelye−1 or 37%.

A special case

[edit]

The situation that appears in the derangement example above occurs often enough to merit special attention.[7] 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

AJ:=⋂j∈JAj{\displaystyle A_{J}:=\bigcap _{j\in J}A_{j}}

has the same cardinality, sayαk = |AJ|, for everyk-element subsetJ of {1, ..., n}, then

|⋃i=1nAi|=∑k=1n(−1)k−1(nk)αk.{\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}

Or, in the complementary form, where the universal setS has cardinalityα0,

|S∖⋃i=1nAi|=α0−∑k=0n(−1)k−1(nk)αk.{\displaystyle \left|S\smallsetminus \bigcup _{i=1}^{n}A_{i}\right|=\alpha _{0}-\sum _{k=0}^{n}(-1)^{k-1}{\binom {n}{k}}\alpha _{k}.}

Formula generalization

[edit]

Given afamily (repeats allowed) of subsetsA1,A2, ...,An of a universal setS, the principle of inclusion–exclusion calculates the number of elements ofS in none of these subsets. A generalization of this concept would calculate the number of elements ofS which appear in exactly some fixedm of these sets.

LetN = [n] = {1,2,...,n}. If we defineA∅=S{\displaystyle A_{\emptyset }=S}, then the principle of inclusion–exclusion can be written as, using the notation of the previous section; the number of elements ofS contained in none of theAi is:

∑J⊆[n](−1)|J||AJ|.{\displaystyle \sum _{J\subseteq [n]}(-1)^{|J|}|A_{J}|.}

IfI is a fixed subset of the index setN, then the number of elements which belong toAi for alli inI and for no other values is:[8]

∑J⊇I(−1)|J|−|I||AJ|.{\displaystyle \sum _{J\supseteq I}(-1)^{|J|-|I|}|A_{J}|.}

Define the sets

Bk=AI∪{k} for k∈N∖I.{\displaystyle B_{k}=A_{I\cup \{k\}}{\text{ for }}k\in N\smallsetminus I.}

We seek the number of elements in none of theBk which, by the principle of inclusion–exclusion (withB∅=AI{\displaystyle B_{\emptyset }=A_{I}}), is

∑K⊆N∖I(−1)|K||BK|.{\displaystyle \sum _{K\subseteq N\smallsetminus I}(-1)^{|K|}|B_{K}|.}

The correspondenceK ↔J =I ∪K between subsets ofN \ I and subsets ofN containingI is a bijection and ifJ andK correspond under this map thenBK =AJ, showing that the result is valid.

In probability

[edit]

Inprobability, for eventsA1, ...,An in aprobability space(Ω,F,P){\displaystyle (\Omega ,{\mathcal {F}},\mathbb {P} )}, the inclusion–exclusion principle becomes forn = 2

P(A1∪A2)=P(A1)+P(A2)−P(A1∩A2),{\displaystyle \mathbb {P} (A_{1}\cup A_{2})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})-\mathbb {P} (A_{1}\cap A_{2}),}

forn = 3

P(A1∪A2∪A3)=P(A1)+P(A2)+P(A3)−P(A1∩A2)−P(A1∩A3)−P(A2∩A3)+P(A1∩A2∩A3){\displaystyle \mathbb {P} (A_{1}\cup A_{2}\cup A_{3})=\mathbb {P} (A_{1})+\mathbb {P} (A_{2})+\mathbb {P} (A_{3})-\mathbb {P} (A_{1}\cap A_{2})-\mathbb {P} (A_{1}\cap A_{3})-\mathbb {P} (A_{2}\cap A_{3})+\mathbb {P} (A_{1}\cap A_{2}\cap A_{3})}

and in general

P(⋃i=1nAi)=∑i=1nP(Ai)−∑i<jP(Ai∩Aj)+∑i<j<kP(Ai∩Aj∩Ak)+⋯+(−1)n−1P(⋂i=1nAi),{\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{i=1}^{n}\mathbb {P} (A_{i})-\sum _{i<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\cdots +(-1)^{n-1}\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right),}

which can be written in closed form as

P(⋃i=1nAi)=∑k=1n((−1)k−1∑I⊆{1,…,n}|I|=kP(AI)),{\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}\left((-1)^{k-1}\sum _{I\subseteq \{1,\ldots ,n\} \atop |I|=k}\mathbb {P} (A_{I})\right),}

where the last sum runs over all subsetsI of the indices 1, ...,n which contain exactlyk elements, and

AI:=⋂i∈IAi{\displaystyle A_{I}:=\bigcap _{i\in I}A_{i}}

denotes the intersection of all thoseAi with index inI.

According to theBonferroni inequalities, the sum of the first terms in the formula is alternately an upper bound and a lower bound for theLHS. This can be used in cases where the full formula is too cumbersome.

For a generalmeasure space (S,Σ,μ) andmeasurable subsetsA1, ...,An offinite measure, the above identities also hold when the probability measureP{\displaystyle \mathbb {P} } is replaced by the measureμ.

Special case

[edit]

If, in the probabilistic version of the inclusion–exclusion principle, the probability of the intersectionAI only depends on the cardinality ofI, meaning that for everyk in {1, ..., n} there is anak such that

ak=P(AI) for every I⊂{1,…,n} with |I|=k,{\displaystyle a_{k}=\mathbb {P} (A_{I}){\text{ for every }}I\subset \{1,\ldots ,n\}{\text{ with }}|I|=k,}

then the above formula simplifies to

P(⋃i=1nAi)=∑k=1n(−1)k−1(nk)ak{\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{n}A_{i}\right)=\sum _{k=1}^{n}(-1)^{k-1}{\binom {n}{k}}a_{k}}

due to the combinatorial interpretation of thebinomial coefficient(nk){\textstyle {\binom {n}{k}}}. For example, if the eventsAi{\displaystyle A_{i}} areindependent and identically distributed, thenP(Ai)=p{\displaystyle \mathbb {P} (A_{i})=p} for alli, and we haveak=pk{\displaystyle a_{k}=p^{k}}, in which case the expression above simplifies to

P(⋃i=1nAi)=1−(1−p)n.{\displaystyle \mathbb {P} \left(\bigcup _{i=1}^{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 eventsAi{\displaystyle A_{i}}.)

An analogous simplification is possible in the case of a general measure space(S,Σ,μ){\displaystyle (S,\Sigma ,\mu )} and measurable subsetsA1,…,An{\displaystyle A_{1},\dots ,A_{n}} of finite measure.

There is another formula used inpoint processes. LetS{\displaystyle S} be a finite set andP{\displaystyle P} be a random subset ofS{\displaystyle S}. LetA{\displaystyle A} be any subset ofS{\displaystyle S}, then

P(P=A)=P(P⊃A)−∑j1∈S∖AP(P⊃A∪j1)+∑j1,j2∈S∖A j1≠j2P(P⊃A∪j1,j2)+…+(−1)|S|−|A|P(P⊃S)=∑A⊂J⊂S(−1)|J|−|A|P(P⊃J).{\displaystyle {\begin{aligned}\mathbb {P} (P=A)&=\mathbb {P} (P\supset A)-\sum _{j_{1}\in S\setminus A}\mathbb {P} (P\supset A\cup {j_{1}})\\&+\sum _{j_{1},j_{2}\in S\setminus A\ j_{1}\neq j_{2}}\mathbb {P} (P\supset A\cup {j_{1},j_{2}})+\dots \\&+(-1)^{|S|-|A|}\mathbb {P} (P\supset S)\\&=\sum _{A\subset J\subset S}(-1)^{|J|-|A|}\mathbb {P} (P\supset J).\end{aligned}}}

Other formulas

[edit]

The principle is sometimes stated in the form[9] that says that if

g(A)=∑S⊆Af(S){\displaystyle g(A)=\sum _{S\subseteq A}f(S)}

then

f(A)=∑S⊆A(−1)|A|−|S|g(S){\displaystyle f(A)=\sum _{S\subseteq A}(-1)^{|A|-|S|}g(S)}2

The combinatorial and the probabilistic version of the inclusion–exclusion principle are instances of (2).

Proof

Takem_={1,2,…,m}{\displaystyle {\underline {m}}=\{1,2,\ldots ,m\}},f(m_)=0{\displaystyle f({\underline {m}})=0}, and

f(S)=|⋂i∈m_∖SAi∖⋃i∈SAi| and f(S)=P(⋂i∈m_∖SAi∖⋃i∈SAi){\displaystyle f(S)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right|{\text{ and }}f(S)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus S}A_{i}\smallsetminus \bigcup _{i\in S}A_{i}\right)}

respectively for allsetsS{\displaystyle S} withS⊊m_{\displaystyle S\subsetneq {\underline {m}}}. Then we obtain

g(A)=|⋂i∈m_∖AAi|,g(m_)=|⋃i∈m_Ai| and g(A)=P(⋂i∈m_∖AAi),  g(m_)=P(⋃i∈m_Ai){\displaystyle g(A)=\left|\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right|,\quad g({\underline {m}})=\left|\bigcup _{i\in {\underline {m}}}A_{i}\right|{\text{ and }}g(A)=\mathbb {P} \left(\bigcap _{i\in {\underline {m}}\smallsetminus A}A_{i}\right),~~g({\underline {m}})=\mathbb {P} \left(\bigcup _{i\in {\underline {m}}}A_{i}\right)}

respectively for all setsA{\displaystyle A} withA⊊m_{\displaystyle A\subsetneq {\underline {m}}}. This is becauseelementsa{\displaystyle a} of∩i∈m_∖AAi{\displaystyle \cap _{i\in {\underline {m}}\smallsetminus A}A_{i}} can becontained in otherAi{\displaystyle A_{i}} (Ai{\displaystyle A_{i}} withi∈A{\displaystyle i\in A}) as well, and the∩∖∪{\displaystyle \cap \smallsetminus \cup }-formula runs exactly through all possible extensions of the sets{Ai∣i∈m_∖A}{\displaystyle \{A_{i}\mid i\in {\underline {m}}\smallsetminus A\}} with otherAi{\displaystyle A_{i}}, countinga{\displaystyle a} only for the set that matches the membership behavior ofa{\displaystyle a}, ifS{\displaystyle S} runs through allsubsets ofA{\displaystyle A} (as in the definition ofg(A){\displaystyle g(A)}).

Sincef(m_)=0{\displaystyle f({\underline {m}})=0}, we obtain from (2) withA=m_{\displaystyle A={\underline {m}}} that

∑m_⊇T⊋∅(−1)|T|−1g(m_∖T)=∑∅⊆S⊊m_(−1)m−|S|−1g(S)=g(m_){\displaystyle \sum _{{\underline {m}}\supseteq T\supsetneq \varnothing }(-1)^{|T|-1}g({\underline {m}}\smallsetminus T)=\sum _{\varnothing \subseteq S\subsetneq {\underline {m}}}(-1)^{m-|S|-1}g(S)=g({\underline {m}})}

and by interchanging sides, the combinatorial and the probabilistic version of the inclusion–exclusion principle follow.

If one sees a numbern{\displaystyle n} as a set of its prime factors, then (2) is a generalization ofMöbius inversion formula forsquare-freenatural numbers. Therefore, (2) is seen as the Möbius inversion formula for theincidence algebra of thepartially ordered set of all subsets ofA.

For a generalization of the full version of Möbius inversion formula, (2) must be generalized tomultisets. For multisets instead of sets, (2) becomes

f(A)=∑S⊆Aμ(A−S)g(S){\displaystyle f(A)=\sum _{S\subseteq A}\mu (A-S)g(S)}3

whereA−S{\displaystyle A-S} is the multiset for which(A−S)⊎S=A{\displaystyle (A-S)\uplus S=A}, and

  • μ(S) = 1 ifS is a set (i.e. a multiset without double elements) ofevencardinality.
  • μ(S) = −1 ifS is a set (i.e. a multiset without double elements) of odd cardinality.
  • μ(S) = 0 ifS is a proper multiset (i.e.S has double elements).

Notice thatμ(A−S){\displaystyle \mu (A-S)} is just the(−1)|A|−|S|{\displaystyle (-1)^{|A|-|S|}} of (2) in caseA−S{\displaystyle A-S} is a set.

Proof of (3)

Substituteg(S)=∑T⊆Sf(T){\displaystyle g(S)=\sum _{T\subseteq S}f(T)}on the right hand side of (3). Notice thatf(A){\displaystyle f(A)} appears once on both sides of (3). So we must show that for allT{\displaystyle T} withT⊊A{\displaystyle T\subsetneq A}, the termsf(T){\displaystyle f(T)} cancel out on the right hand side of (3). For that purpose, take a fixedT{\displaystyle T} such thatT⊊A{\displaystyle T\subsetneq A} and take an arbitrary fixeda∈A{\displaystyle a\in A} such thata∉T{\displaystyle a\notin T}.

Notice thatA−S{\displaystyle A-S} must be a set for eachpositive ornegative appearance off(T){\displaystyle f(T)} on the right hand side of (3) that is obtained by way of the multisetS{\displaystyle S} such thatT⊆S⊆A{\displaystyle T\subseteq S\subseteq A}. Now each appearance off(T){\displaystyle f(T)} on the right hand side of (3) that is obtained by way ofS{\displaystyle S} such thatA−S{\displaystyle A-S} is a set that containsa{\displaystyle a} cancels out with the one that is obtained by way of the correspondingS{\displaystyle S} such thatA−S{\displaystyle A-S} is a set that does not containa{\displaystyle a}. This gives the desired result.

Applications

[edit]

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

Counting derangements

[edit]
Main article:Derangement

A well-known application of the inclusion–exclusion principle is to the combinatorial problem of counting allderangements of a finite set. Aderangement of a setA is abijection fromA into itself that has no fixed points. Via the inclusion–exclusion principle one can show that if the cardinality ofA isn, then the number of derangements is [n! / e] where [x] denotes thenearest integer tox; a detailed proof is availablehere and also seethe 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."[10] The problem is also known as thehatcheck problem.

The number of derangements is also known as thesubfactorial ofn, 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 asn grows.

Counting intersections

[edit]

The principle of inclusion–exclusion, combined withDe Morgan's law, can be used to count the cardinality of the intersection of sets as well. LetAk¯{\displaystyle {\overline {A_{k}}}} represent the complement ofAk with respect to some universal setA such thatAk⊆A{\displaystyle A_{k}\subseteq A} for eachk. Then we have

⋂i=1nAi=⋃i=1nAi¯¯{\displaystyle \bigcap _{i=1}^{n}A_{i}={\overline {\bigcup _{i=1}^{n}{\overline {A_{i}}}}}}

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

Graph coloring

[edit]

The inclusion exclusion principle forms the basis of algorithms for a number of NP-hard graph partitioning problems, such asgraph coloring.[11]

A well known application of the principle is the construction of thechromatic polynomial of a graph.[12]

Bipartite graph perfect matchings

[edit]

The number ofperfect matchings of abipartite graph can be calculated using the principle.[13]

Number of onto functions

[edit]

Given finite setsA andB, how manysurjective functions (onto functions) are there fromA toB?Without any loss of generality we may takeA = {1, ...,k} andB = {1, ...,n}, since only the cardinalities of the sets matter. By usingS as the set of allfunctions fromA toB, and defining, for eachi inB, the propertyPi as "the function misses the elementi inB" (i is not in theimage of the function), the principle of inclusion–exclusion gives the number of onto functions betweenA andB as:[14]

∑j=0n(nj)(−1)j(n−j)k.{\displaystyle \sum _{j=0}^{n}{\binom {n}{j}}(-1)^{j}(n-j)^{k}.}

Permutations with forbidden positions

[edit]

Apermutation of the setS = {1, ...,n} where each element ofS is restricted to not being in certain positions (here the permutation is considered as an ordering of the elements ofS) is called apermutation with forbidden positions. For example, withS = {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 lettingAi be the set of positions that the elementi is not allowed to be in, and the propertyPi to be the property that a permutation puts elementi into a position inAi, the principle of inclusion–exclusion can be used to count the number of permutations which satisfy all the restrictions.[15]

In the given example, there are 12 = 2(3!) permutations with propertyP1, 6 = 3! permutations with propertyP2 and no permutations have propertiesP3 orP4 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 propertiesP1 andP2. There are no other non-zero contributions to the formula.

Stirling numbers of the second kind

[edit]
Main article:Stirling numbers of the second kind

TheStirling numbers of the second kind,S(n,k) count the number ofpartitions of a set ofn elements intok non-empty subsets (indistinguishableboxes). 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 ann-set intok non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of then-set intok (possibly empty) distinguishable boxes,A1,A2, ...,Ak, and the propertiesPi meaning that the partition has boxAi empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing byk! to remove the artificial ordering gives the Stirling number of the second kind:[16]

S(n,k)=1k!∑t=0k(−1)t(kt)(k−t)n.{\displaystyle S(n,k)={\frac {1}{k!}}\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}(k-t)^{n}.}

Rook polynomials

[edit]
Main article:Rook polynomial

Arook polynomial is thegenerating function of the number of ways to place non-attackingrooks on aboard B that looks like a subset of the squares of acheckerboard; that is, no two rooks may be in the same row or column. The boardB is any subset of the squares of a rectangular board withn rows andm columns; we think of it as the squares in which one is allowed to put a rook. Thecoefficient,rk(B) ofxk in the rook polynomialRB(x) is the number of waysk rooks, none of which attacks another, can be arranged in the squares ofB. For any boardB, there is a complementary boardB′{\displaystyle B'} consisting of the squares of the rectangular board that are not inB. This complementary board also has a rook polynomialRB′(x){\displaystyle R_{B'}(x)} with coefficientsrk(B′).{\displaystyle 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 thatn ≤m, so this coefficient isrn(B). The number of ways to placen non-attacking rooks on the completen ×m "checkerboard" (without regard as to whether the rooks are placed in the squares of the boardB) is given by thefalling factorial:

(m)n=m(m−1)(m−2)⋯(m−n+1).{\displaystyle (m)_{n}=m(m-1)(m-2)\cdots (m-n+1).}

LettingPi be the property that an assignment ofn non-attacking rooks on the complete board has a rook in columni which is not in a square of the boardB, then by the principle of inclusion–exclusion we have:[17]

rn(B)=∑t=0n(−1)t(m−t)n−trt(B′).{\displaystyle r_{n}(B)=\sum _{t=0}^{n}(-1)^{t}(m-t)_{n-t}r_{t}(B').}

Euler's phi function

[edit]
Main article:Euler's totient function

Euler's totient or phi function,φ(n) is anarithmetic function that counts the number of positive integers less than or equal ton that arerelatively prime ton. That is, ifn is apositive integer, then φ(n) is the number of integersk in the range 1 ≤k ≤n which have no common factor withn other than 1. The principle of inclusion–exclusion is used to obtain a formula for φ(n). LetS be the set {1, ...,n} and define the propertyPi to be that a number inS is divisible by the prime numberpi, for 1 ≤i ≤r, where theprime factorization of

n=p1a1p2a2⋯prar.{\displaystyle n=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots p_{r}^{a_{r}}.}

Then,[18]

φ(n)=n−∑i=1rnpi+∑1⩽i<j⩽rnpipj−⋯=n∏i=1r(1−1pi).{\displaystyle \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).}

Dirichlet hyperbola method

[edit]
Main article:Dirichlet hyperbola method
An example of the Dirichlet hyperbola method withn=10,{\displaystyle n=10,}a≈2.7,{\displaystyle a\approx 2.7,} andb≈3.7.{\displaystyle b\approx 3.7.}

TheDirichlet hyperbola method re-expresses a sum of amultiplicative functionf(n){\displaystyle f(n)} by selecting a suitableDirichlet convolutionf=g∗h{\displaystyle f=g\ast h}, recognizing that the sum

F(n)=∑k=1nf(k)=∑k=1n∑xy=kg(x)h(y){\displaystyle F(n)=\sum _{k=1}^{n}f(k)=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y)}

can be recast as a sum over thelattice points in a region bounded byx≥1{\displaystyle x\geq 1},y≥1{\displaystyle y\geq 1}, andxy≤n{\displaystyle xy\leq n}, splitting this region into two overlapping subregions, and finally using the inclusion–exclusion principle to conclude that

F(n)=∑k=1nf(k)=∑k=1n∑xy=kg(x)h(y)=∑x=1a∑y=1n/xg(x)h(y)+∑y=1b∑x=1n/yg(x)h(y)−∑x=1a∑y=1bg(x)h(y).{\displaystyle 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).}

Diluted inclusion–exclusion principle

[edit]
See also:Bonferroni inequalities

In many cases where the principle could give an exact formula (in particular, countingprime numbers using thesieve of Eratosthenes), 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. Innumber theory, this difficulty was addressed byViggo Brun. After a slow start, his ideas were taken up by others, and a large variety ofsieve methods developed. These for example may try to find upper bounds for the "sieved" sets, rather than an exact formula.

LetA1, ...,An be arbitrary sets andp1, ...,pn real numbers in the closed unit interval[0, 1]. Then, for every even numberk in {0, ...,n}, theindicator functions satisfy the inequality:[19]

1A1∪⋯∪An≥∑j=1k(−1)j−1∑1≤i1<⋯<ij≤npi1…pij1Ai1∩⋯∩Aij.{\displaystyle 1_{A_{1}\cup \cdots \cup A_{n}}\geq \sum _{j=1}^{k}(-1)^{j-1}\sum _{1\leq i_{1}<\cdots <i_{j}\leq n}p_{i_{1}}\dots p_{i_{j}}\,1_{A_{i_{1}}\cap \cdots \cap A_{i_{j}}}.}

Proof of main statement

[edit]

Choose an element contained in the union of all sets and letA1,A2,…,At{\displaystyle A_{1},A_{2},\dots ,A_{t}} be the individual sets containing it. (Note thatt > 0.) Since the element is counted precisely once by the left-hand side of equation (1), 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 fromA1,A2,…,At{\displaystyle 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:

|{Ai∣1⩽i⩽t}|−|{Ai∩Aj∣1⩽i<j⩽t}|+⋯+(−1)t+1|{A1∩A2∩⋯∩At}|=(t1)−(t2)+⋯+(−1)t+1(tt).{\displaystyle {\begin{aligned}|\{A_{i}\mid 1\leqslant i\leqslant t\}|&-|\{A_{i}\cap A_{j}\mid 1\leqslant i<j\leqslant t\}|+\cdots +(-1)^{t+1}|\{A_{1}\cap A_{2}\cap \cdots \cap A_{t}\}|={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}}.\end{aligned}}}

By thebinomial theorem,

0=(1−1)t=(t0)−(t1)+(t2)−⋯+(−1)t(tt).{\displaystyle 0=(1-1)^{t}={\binom {t}{0}}-{\binom {t}{1}}+{\binom {t}{2}}-\cdots +(-1)^{t}{\binom {t}{t}}.}

Using the fact that(t0)=1{\displaystyle {\binom {t}{0}}=1} and rearranging terms, we have

1=(t1)−(t2)+⋯+(−1)t+1(tt),{\displaystyle 1={\binom {t}{1}}-{\binom {t}{2}}+\cdots +(-1)^{t+1}{\binom {t}{t}},}

and so, the chosen element is counted only once by the right-hand side of equation (1).

Algebraic proof

[edit]

An algebraic proof can be obtained usingindicator functions (also known as characteristic functions). The indicator function of a subsetS of a setX is the function

1S:X→{0,1}1S(x)={1x∈S0x∉S{\displaystyle {\begin{aligned}&\mathbf {1} _{S}:X\to \{0,1\}\\&\mathbf {1} _{S}(x)={\begin{cases}1&x\in S\\0&x\notin S\end{cases}}\end{aligned}}}

IfA{\displaystyle A} andB{\displaystyle B} are two subsets ofX{\displaystyle X}, then

1A⋅1B=1A∩B.{\displaystyle \mathbf {1} _{A}\cdot \mathbf {1} _{B}=\mathbf {1} _{A\cap B}.}

LetA denote the union⋃i=1nAi{\textstyle \bigcup _{i=1}^{n}A_{i}} of the setsA1, ...,An. To prove the inclusion–exclusion principle in general, we first verify the identity

1A=∑k=1n(−1)k−1∑I⊂{1,…,n}|I|=k1AI{\displaystyle \mathbf {1} _{A}=\sum _{k=1}^{n}(-1)^{k-1}\sum _{I\subset \{1,\ldots ,n\} \atop |I|=k}\mathbf {1} _{A_{I}}}4

for indicator functions, where:

AI=⋂i∈IAi.{\displaystyle A_{I}=\bigcap _{i\in I}A_{i}.}

The following function

(1A−1A1)(1A−1A2)⋯(1A−1An)=0,{\displaystyle \left(\mathbf {1} _{A}-\mathbf {1} _{A_{1}}\right)\left(\mathbf {1} _{A}-\mathbf {1} _{A_{2}}\right)\cdots \left(\mathbf {1} _{A}-\mathbf {1} _{A_{n}}\right)=0,}

is identically zero because: ifx is not inA, then all factors are 0−0 = 0; and otherwise, ifx does belong to someAm, then the correspondingmth factor is 1−1=0. By expanding the product on the left-hand side, equation (4) follows.

To prove the inclusion–exclusion principle for the cardinality of sets, sum the equation (4) over allx in the union ofA1, ...,An. To derive the version used in probability, take theexpectation in (4). In general,integrate the equation (4) with respect to μ. Always use linearity in these derivations.

See also

[edit]

Notes

[edit]
  1. ^abRoberts & Tesman 2009, pg. 405
  2. ^Mazur 2010, pg. 94
  3. ^van Lint & Wilson 1992, pg. 77
  4. ^van Lint & Wilson 1992, pg. 77
  5. ^Stanley 1986, pg. 64
  6. ^Rota, pp. 340–368 harvnb error: no target: CITEREFRota (help)
  7. ^Brualdi 2010, pp. 167–8
  8. ^Cameron 1994, pg. 78
  9. ^Graham, Grötschel & Lovász 1995, pg. 1049
  10. ^van Lint & Wilson 1992, pp. 77-8
  11. ^Björklund, Husfeldt & Koivisto 2009
  12. ^Gross 2008, pp. 211–13
  13. ^Gross 2008, pp. 208–10
  14. ^Mazur 2010, pp.84-5, 90
  15. ^Brualdi 2010, pp. 177–81
  16. ^Brualdi 2010, pp. 282–7
  17. ^Roberts & Tesman 2009, pp.419–20
  18. ^van Lint & Wilson 1992, pg. 73
  19. ^(Fernández, Fröhlich & Alan D. 1992, Proposition 12.6)

References

[edit]

This article incorporates material from principle of inclusion–exclusion onPlanetMath, which is licensed under theCreative Commons Attribution/Share-Alike License.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Inclusion–exclusion_principle&oldid=1315363138"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp