5. Inclusion–exclusion and applications

Suppose we want to count the students taking algebra or geometry. Adding the two course enrollments counts every student in both courses twice. With three or more courses, a student may appear in several intersections, and each kind of overlap requires its own correction. The principle of inclusion–exclusion organizes these corrections.

We first develop inclusion–exclusion for unions and then rewrite it for objects that must avoid several violations. The applications follow the order in which they arose in lecture: bounded integer solutions, forbidden substrings, Euler’s totient function, a grouped formula for symmetric conditions, and derangements. Graphs without isolated vertices, full-alphabet strings, and surjective functions provide further applications of the same formula.

After studying these notes, you will be able to do the following.

• Explain and apply the two-set and three-set inclusion–exclusion formulas.

• State the general principle of inclusion–exclusion for finite sets and compute sizes of unions.

• Use indicator functions to prove the inclusion–exclusion formula.

• Express problems with multiple constraints using the complement (violation-set) form.

• Count integer solutions to linear equations with upper bounds by combining inclusion–exclusion with stars and bars.

• Count strings without repeated letters that avoid prescribed substrings, including cases in which substring conditions are incompatible.

• Derive the product formula for Euler’s totient function.

• Recognize when the count for imposed conditions depends only on the number of conditions and apply the grouped inclusion–exclusion formula.

• Count labeled graphs with no isolated vertices.

• Derive the formula for derangements and count permutations with a specified number of fixed points.

• Count surjective functions and strings that use every symbol of an alphabet.

5.1 The geometry of overlapping sets

Let and be finite subsets of a universal set . The union consists of all elements belonging to , to , or to both. When , the sum rule gives . When , every element contributes to and to , so the sum counts each element of . Subtracting removes this extra copy.

Theorem 1 (Inclusion–exclusion for two sets)

For any finite sets and ,

Example 2 (Students enrolled in two courses)

In a department of mathematics, students take abstract algebra, take geometry, and take both courses. How many students take at least one of these two courses?

Solution: Let be the set of students taking algebra and the set of students taking geometry. The set of students taking at least one course is . By Theorem 1, The students enrolled in both courses were counted in and in ; subtracting leaves each student counted exactly once.

Now consider three finite sets , , and . If we begin with the sum of their individual sizes, , an element belonging to exactly one set is counted once. An element belonging to the intersection of two sets (say , but not ) is counted twice: once in and once in . An element belonging to all three sets, , is counted three times.

To correct for the pairwise overlaps, we subtract the sizes of all three two-way intersections: An element in exactly two sets was counted twice and is now subtracted once, leaving a net count of . However, an element in all three sets was counted three times in the initial sum and subtracted three times (once in each pairwise intersection). Its net count is now . To count such elements in the union, we must add back the size of the triple intersection .

Figure 1: Multiplicities in each Venn region across the three stages of inclusion–exclusion for three sets. Stage 1 adds individual sizes; Stage 2 subtracts pairwise intersections; Stage 3 adds the triple intersection.

Figure 1 tracks how each step adjusts the multiplicity of every region in the Venn diagram. The net result is that every element belonging to at least one of the three sets has a final coefficient of .

Theorem 3 (Inclusion–exclusion for three sets)

For any finite sets , , and ,

Example 4 (Course enrollments in three subjects)

A survey of mathematics majors records course enrollments as follows: students take algebra, take geometry, and take calculus. Furthermore, take algebra and geometry, take algebra and calculus, take geometry and calculus, and take all three courses.

1. How many students take at least one of these three courses?

2. How many students take none of these three courses?

Solution: Let , , and denote the sets of students taking algebra, geometry, and calculus, respectively.

1. The set of students taking at least one course is . Applying Theorem 3:

2. The universal set has students. The students taking none of the three courses form the complement . By the difference rule,

5.2 The general principle of inclusion–exclusion

To state the principle for any finite number of sets , we index the intersections by subsets of the index set . The size determines whether the term is added or subtracted: terms with odd carry a positive sign, while terms with even carry a negative sign.

Figure 2: Four intersections corresponding to index subsets of : gives ; gives ; gives ; and gives .

Theorem 5 (Principle of inclusion–exclusion)

Let be finite sets. Then

Grouping the index subsets by their size gives an equivalent expanded form: The inner sum for adds the sizes of all individual sets; for , it subtracts all pairwise intersections; for , it adds all triple intersections, continuing up to .

5.2.1 Proof via indicator functions

A clean and general proof of Theorem 5 uses indicator functions, also called characteristic functions. Let be a finite universal set containing . For any subset , the indicator function is defined by Indicator functions satisfy three basic algebraic properties:

1. The cardinality of is the sum of its indicator values over the universe:

2. The indicator of an intersection is the product of the indicators, since an element belongs to an intersection precisely when it belongs to every set in the intersection:

3. The indicator of the complement is

Proof of Theorem 5

An element does not belong to the union if and only if for every . Therefore, Using the complement property , we have We expand the product with . Every term in the expansion corresponds to choosing for a subset of indices and for the remaining indices: Subtracting this product from yields Finally, summing this identity over all and using the identity for each term gives which proves the theorem.

5.2.2 The complement and violation-set form

In combinatorial applications, we frequently want to count objects in a universe that satisfy several conditions simultaneously. Rather than working directly with the satisfying objects, it is often simpler to identify the violation sets , where consists of the objects that fail condition .

An object satisfies all conditions if and only if it belongs to none of the violation sets. The set of valid objects is therefore the complement of the union of the violation sets: Subtracting the union formula from gives the complement form of inclusion–exclusion:

(1)

where the term for is defined to be .

5.3 Integer solutions with upper bounds

The method of stars and bars counts nonnegative integer solutions to equations of the form . Lower bounds are easily handled by a change of variables . Upper bounds , however, cannot be incorporated by a simple variable shift because solutions may violate the bound in one coordinate, two coordinates, or more. Inclusion–exclusion provides the mechanism to enforce upper bounds.

Example 6 (Upper bounds on three of four variables)

How many integer solutions satisfy with , , and ? There is no upper bound on .

Outline: Let contain all nonnegative solutions of the equation, before imposing the three upper bounds. Let where each set is understood to contain solutions in satisfying the displayed violation. The requested solutions lie in .

We will compute the cardinality of , then the cardinality of each of the three single intersections, each of the three pairwise intersections, and the triple intersection. The complement form of inclusion–exclusion will combine those eight numbers.

Computing the cardinalities: Stars and bars gives In , set . The transformed equation is so . For , subtract from ; for , subtract from . The three single-intersection counts are

• ;

• ;

• .

For , set and . We obtain and therefore . Applying the corresponding two shifts in each of the other intersections gives

• ;

• ;

• .

Finally, in we subtract , , and from , , and , respectively. The remaining total is , so Inclusion–exclusion now gives No binomial coefficient was used to abbreviate the choices of violation sets; every intersection appears in the calculation.

The answer has a direct check. We may choose each of independently within its own range. There are , , and choices, respectively. Then is uniquely determined and is at least , so it is nonnegative. This gives solutions.

5.4 Strings with forbidden substrings

When counting arrangements of distinct items that must avoid specific consecutive patterns, we combine the block-reduction technique with inclusion–exclusion.

To enforce that a specific substring appears, we treat that entire sequence of symbols as a single compound object. When two requested substrings share a letter, that one letter must occupy the same position in both occurrences if repetition is forbidden. The conditions may merge into a longer block, or they may be incompatible.

Example 7 (Four substrings with compatible and incompatible pairs)

How many length- strings can be formed from the uppercase English letters if no letter may be repeated and none of the following strings occurs as a substring?

Solution: Let be the set of all length- strings with no repeated letter. Thus . Define four violation sets:

• : strings containing CAST;

• : strings containing TUG;

• : strings containing GAS;

• : strings containing SAG.

We first count the individual violation sets. A copy of CAST can start in any of the first positions. After placing it, we fill the other positions with distinct letters chosen in order from the remaining letters. A three-letter substring has possible starting positions, after which the other positions are filled from the remaining letters. Because letters cannot repeat, none of the specified substrings can occur twice in the same string. The start-position cases are therefore disjoint, and

The pairwise intersections are not all alike. We examine all six.

• The conditions CAST and TUG share their letter T. The only compatible placement joins them into the block CASTUG. This length- block has possible starting positions; the remaining positions use distinct letters from the other . Hence

• The conditions CAST and GAS cannot both hold. Both would use the same adjacent pair AS, but CAST requires C immediately before that pair while GAS requires G there. Thus .

• The conditions CAST and SAG cannot both hold: CAST places A before S, while SAG places the same S before the same A. Thus .

• The conditions TUG and GAS join at their common letter G to form TUGAS. This length- block has possible starting positions, and the remaining positions use distinct letters from the other . Hence

• The conditions TUG and SAG both end in their only copy of G. They would require both U and A immediately before that G, so .

• The conditions GAS and SAG use the same three letters in incompatible orders. Hence .

Every intersection of three or four violation sets contains one of the incompatible pairs above, so all higher intersections are empty. Inclusion–exclusion gives The coefficient in the first subtraction groups three equal single counts. It does not assert that all intersections involving the same number of conditions have equal size: among the six pairwise intersections, two are nonzero and they have different sizes.

5.5 Euler’s totient function

Two positive integers are relatively prime, or coprime, if their greatest common divisor is . For a positive integer , Euler’s totient function counts the integers in that are relatively prime to : If we know the distinct prime divisors of , inclusion–exclusion counts the integers that avoid divisibility by every one of them.

Theorem 8 (Product formula for Euler’s totient function)

Let be a positive integer with distinct prime divisors . Then For , the list of prime divisors is empty, the empty product is , and the formula gives .

Proof

Let . For each distinct prime divisor of , let be the set of integers in divisible by . An integer in is not relatively prime to precisely when it belongs to at least one . Thus counts the elements that belong to none of these sets.

For an index set , an integer lies in precisely when it is divisible by . The primes are distinct, and their product divides , so exactly elements of satisfy these conditions. The complement form of inclusion–exclusion gives The last equality is the expansion of the product: choosing from the th factor records the index in .

Example 9 (Computing )

The distinct prime divisors of are , , and . The exponents in the prime factorization do not create additional violation sets: an integer fails to be coprime to when it is divisible by , by , or by . Therefore There are integers in relatively prime to .

5.6 When only the number of imposed conditions matters

In the substring example, the number of strings in an intersection depends on which conditions we impose. Of the six pairwise intersections, four are empty and the other two have different cardinalities. We therefore had to examine the pairs one at a time.

Other problems have enough symmetry that the identities of the imposed conditions do not affect the count. In that situation, the sum over all subsets of conditions becomes a sum indexed only by the number of imposed conditions.

Theorem 10 (Inclusion–exclusion grouped by number of conditions)

Let be a finite set, and let consist of the objects in that satisfy condition , for . Set . Suppose that for each there is a number such that Then the number of objects satisfying at least one condition is and the number satisfying none of the conditions is

Proof

For a fixed , there are index sets of size . By hypothesis, each corresponding intersection has size . Therefore Substituting this equality into the general union formula gives the first formula. Substituting it into the complement formula gives the second.

The word imposed has a specific meaning here. An object counted by must satisfy every condition indexed by , but it may also satisfy conditions whose indices are not in . Thus does not count objects satisfying exactly conditions.

Example 11 (The same upper bound on five variables)

How many integer solutions satisfy

Solution: Let be the set of nonnegative solutions before the upper bounds are imposed. Stars and bars gives For each , let be the violation set defined by .

Suppose that has size . For every , subtract from . The transformed nonnegative variables have sum . The number of solutions depends on , but not on which variables are named by . Thus and the grouped complement formula gives

The calculation uses the same shifting method as Example 6. In that example, the bounds on were , , and . The three single-intersection counts were different, as were the three pairwise-intersection counts, so we kept every term separate. Here all five variables have the same upper bound. Any chosen violation conditions leave the same total , so the intersections of size all have cardinality . The binomial coefficient is justified by this equality of cardinalities; it is not part of the general inclusion–exclusion formula.

The same argument yields a formula for any number of variables with a common upper bound.

Theorem 12 (Nonnegative solutions with a common upper bound)

Let be nonnegative integers with . The number of integer solutions to is

Proof

Let be the set of all nonnegative solutions to . For each , let contain the solutions with .

If has size , subtracting from every with gives a bijection from to the nonnegative solutions of When the right side is nonnegative, stars and bars shows that the intersection has size When , the intersection is empty. This cardinality depends only on , so the formula for satisfying none of the conditions in Theorem 10 gives the stated sum.

Warning (Check symmetry before using )

The grouped formula requires every choice of conditions to give the same intersection size. In Example 7, some pairs merge into a longer block while other pairs are incompatible, so there is no single number . The general inclusion–exclusion formula still applies, but the pairwise intersections must be counted separately.

5.7 Graphs with no isolated vertices

A simple graph consists of a set of vertices together with a set of edges, where each edge is an unordered pair of distinct vertices. Thus a simple graph has no loops from a vertex to itself and no multiple edges joining the same pair. In this section the vertex set is so the vertices are labeled. Two graphs with different edge sets are counted as different graphs. A vertex is isolated if it belongs to no edge.

Problem 13 (Graphs without isolated vertices)

How many simple graphs on the labeled vertex set have no isolated vertices? Derive a formula, and then evaluate it when .

We begin by counting all simple graphs on , before excluding isolated vertices. There is one possible edge for each unordered pair of distinct vertices, so there are possible edges. For each pair we independently decide whether its edge is present or absent. The product rule therefore gives simple graphs on .

For five vertices, the ten dashed segments in Figure 3 are the ten possible edges. A particular graph is obtained by retaining any subset of them. The drawing is not one graph being counted; it displays the ten independent edge choices used to count all graphs.

Figure 3: The possible edges on five labeled vertices. Each edge may be present or absent independently, giving graphs.

Let be the set of all simple graphs on . For each vertex , let A graph has no isolated vertices precisely when it belongs to none of the sets .

Suppose and . In a graph belonging to , every edge having an endpoint in must be absent. The only edges still available join two of the vertices outside . There are such pairs, and each corresponding edge may be present or absent independently. Consequently, Here when is or , because fewer than two vertices determine no possible edge. This number depends on , but not on the identities of the vertices in . The grouped complement form of inclusion–exclusion gives the formula

(2)

For , Figure 4 shows a representative intersection for each value . The red vertices are required to be isolated. Dashed edges are the choices that remain; an unshown edge is forced to be absent. The vertices not colored red are not required to be nonisolated. They may become isolated when some or all of their optional edges are omitted.

Figure 4: Representative intersections of isolated-vertex conditions for graphs on . After those conditions are imposed, only edges among the other vertices remain optional.

The complete inclusion–exclusion calculation is There are therefore simple graphs on the labeled vertex set with no isolated vertices. Notice that the and intersections each contain one graph: the graph with no edges. If four vertices are required to be isolated, the fifth vertex cannot have an edge by itself and is isolated as well.

5.8 Derangements and fixed points

Let be a permutation of the first positive integers. An index is a fixed point of if .

Definition 14 (Derangement)

A derangement of is a permutation with no fixed points; that is, for all . The number of derangements of an -element set is denoted by or .

A classic illustration is the hat-check problem: if people check their hats and the hats are returned completely at random, a derangement is an assignment in which no person receives their own hat.

Theorem 15 (Formula for derangements)

For any integer , the number of derangements of is By convention, .

Proof

Let be the set of all permutations of . For each , let be the set of permutations that fix element : A permutation is a derangement if and only if it belongs to none of the sets , so .

Let with . A permutation in the intersection fixes all elements in . The remaining elements may be permuted arbitrarily in ways. Thus, regardless of which elements are chosen.

The number depends only on the number of fixed-point conditions, not on which elements are fixed. Therefore Theorem 10 gives Using the identity , we factor out : which proves the formula.

The table below lists the first several values of alongside :

Example 16 (Returning items at random)

Six students place their phones into a basket, and the phones are redistributed uniformly at random so that each student receives one phone.

1. In how many ways can the phones be returned so that no student receives their own phone?

2. In how many ways can the phones be returned so that exactly two students receive their own phones?

Solution:

1. This is the number of derangements of items:

2. To have exactly two students receive their own phones, we first choose which two students receive their own phones in ways. The remaining phones must then be deranged among the other students so that no further student receives their own phone:

The reasoning in part (2) of Example 16 immediately generalizes to count permutations with any specified number of fixed points.

Corollary 17 (Permutations with exactly fixed points)

The number of permutations of having exactly fixed points (where ) is

Proof

There are ways to choose the elements that remain fixed. For each such choice, the remaining elements must be deranged among themselves to ensure that no other element is fixed. There are such derangements. By the product rule, the total number of permutations is .

Remark 18 (Asymptotic probability of a derangement)

The probability that a uniformly chosen permutation of elements is a derangement is As , this sum converges rapidly to the Taylor series for : Because the series alternates with terms decreasing monotonically to zero, . Multiplying by shows that for all . Consequently, is the nearest integer to for every .

5.9 Counting surjective functions and full-alphabet strings

Let and be finite sets with and . A function is surjective, or onto, if every element of is in the image of : for each , there is at least one such that .

We may record a function as a string of length after choosing an order for the elements of . The character in the position belonging to is . Under this correspondence, surjectivity means that the string contains every symbol of the alphabet at least once.

The condition that a function omit a specified output is easier to count than surjectivity itself. If specified elements of are omitted, each input has possible images. This count depends only on the number of omitted outputs, so Theorem 10 applies.

Theorem 19 (Number of surjective functions)

Let and be finite sets with and , where . The number of surjective functions is Equivalently, this is the number of length- strings over an -symbol alphabet that use every symbol.

Proof

Let be the set of all functions from to . For each , let be the set of functions whose image omits : A function is surjective if and only if it belongs to none of the sets .

For any subset of size , the intersection consists of functions whose image is contained in . There are such functions, regardless of which elements form . The formula for satisfying none of the omission conditions in Theorem 10 gives the result.

Example 20 (Surjective functions from a -set to a -set)

How many surjective functions are there from a set of elements to a set of elements?

Solution: Setting and in Theorem 19 gives Thus there are functions whose image contains all three target elements. The same number counts length- strings over a three-symbol alphabet in which every symbol occurs.

5.9.1 Connection with Stirling numbers

The Stirling number of the second kind is the number of ways to partition an -element set into nonempty, unlabeled subsets. Every surjective function produces such a partition: its parts are the nonempty preimages for . Conversely, after choosing a partition into parts, we may bijectively assign those parts to the elements of in ways. Therefore and hence

When , the pigeonhole principle says that no function can be surjective. Consequently , and the alternating sum also equals .

5.10 Summary of the inclusion–exclusion framework

To apply the principle of inclusion–exclusion systematically to an enumeration problem:

1. Define the universe : Identify the ambient set of all possible configurations without the restrictive conditions, and verify that can be computed.

2. Define the violation sets : Formulate each restrictive condition so that failing condition corresponds to membership in .

3. Characterize the intersections: For an arbitrary index subset , determine what mathematical structure an object in possesses.

4. Count the intersections: Compute . If the answer is for every index set of size , group the equal terms. Check this hypothesis for each ; do not infer it from the one-condition counts alone.

5. Evaluate the alternating sum: Substitute the intersection counts into the union formula or the complement formula, paying attention to the alternating signs.

The applications differ mainly in how an imposed set of conditions changes an object. Upper-bound violations reserve units before stars and bars; compatible substring conditions glue letters into blocks while incompatible ones give empty intersections; divisibility conditions force multiples of selected primes; isolated-vertex conditions remove every edge incident to the named vertices; fixed-point conditions remove elements from the part of a permutation still free to move; and omitted-output conditions reduce the available alphabet. Inclusion–exclusion supplies the alternating signs after these intersections have been counted.

5.11 Further reading

The course resources page links to the reference texts for this course.

• Applied Combinatorics by Tucker, Sections 7.1–7.4, provides additional examples of inclusion–exclusion, rook polynomials, and general derangement problems.

• Discrete Mathematics: An Open Introduction by Levin, Sections 3.3 and 3.8, covers Venn diagram bookkeeping, onto functions, and counting multisets with bounded multiplicities.

• Counting Rocks! by Schepers, Section 2.7, develops the algebraic indicator function approach.