maths.free › Combinatorics & Graph Theory › 7. Inclusion-Exclusion › Inclusion-Exclusion: exercises

Inclusion-Exclusion: exercises

Inclusion-Exclusion: exercises — from Keller & Trotter, Applied Combinatorics.

Practice (33)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

A school has $147$ third graders. The third grade teachers have planned a special treat for the last day of school and brought ice cream for their students. There are three flavors: mint chip, chocolate, and strawberry. Suppose that $60$ students like (at least) mint chip, $103$ like chocolate, $50$ like strawberry, $30$ like mint chip and strawberry, $40$ like mint chip and chocolate, $25$ like chocolate and strawberry, and $18$ like all three flavors. How many students don't like any of the flavors available?

Vis svaret

This is a straightforward application of the Principle of Inclusion-Exclusion, and we have \[\begin{aligned}\end{aligned}\] students who like none of the flavors.
There are $1189$ students majoring in computer science at a particular university. They are surveyed about their knowledge of three programming languages: C++, Java, and Python. The survey results reflect that $856$ students know C++, $792$ know Java, and $692$ know Python. Additionally, $639$ students know both C++ and Java, $519$ know both C++ and Python, and $632$ know both Java and Python. There are $488$ students who report knowing all three languages. How many students reported that they did not know any of the three programming languages?
How many positive integers less than or equal to $100$ are divisible by $2$? How many positive integers less than or equal to $100$ are divisible by $5$? Use this information to determine how many positive integers less than or equal to $100$ are divisible by neither $2$ nor $5$.
How many positive integers less than or equal to $100$ are divisible by none of $2$, $3$, and $5$?
How many positive integers less than or equal to $1000$ are divisible by none of $3$, $8$, and $25$?

Vis svaret

There are 333 multiples of $3$ between 1 and 1000. There are 125 multiples of 8 between 1 and 1000. There are 40 multiples of 25 in this range. Since 3, 8, and 25 do not have any prime factors in common, being divisible by two of these means being divisible by 24, 75, or 200, respectively. There are 41, 13, and 5 multiples in this range, respectively. Finally, being divisible by all three is the same as being divisible by 600, so there is 1 number. Thus, applying the Principle of Inclusion-Exclusion, we have \[\begin{aligned}\end{aligned}\] numbers between 1 and 1000 that are divisible by none of 3, 8, and 25.
The State of Georgia is distributing $$173$ million in funding to Fulton, Gwinnett, DeKalb, Cobb, and Clayton counties (in millions of dollars). In how many ways can this distribution be made, assuming that each county receives at least $$1$ million, Clayton county receives at most $$10$ million, and Cobb county receives at most $$30$ million? What if we add the restriction that Fulton county is to receive at least $$5$ million (instead of at least $$1$ million)?
How many nonnegative integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 32$ with $0\leq x_i\leq 10$ for $i=1,2,3,4$?

Vis svaret

We can think of this as a folder distribution problem, but now we have four upper bound constraints. Fortunately, they are all the same, so we do not need to consider them each separately. We approach this by counting all solutions without regard to the upper bound constraints and then subtracting off those in which at least one upper bound constraint is violated. Since there are four upper bound constraints, we will use inclusion-exclusion to subtract them. Note that an upper bound constraint being violated means that $x_{i}\gt 10$ or $x_{i}\geq 11$. Thus, since the sum of the variables must be $32$, we can have at most 2 upper bound constraints violated concurrently:
Ignoring the upper bound constraints, we have 32 objects to distribute but need 4 artificial since each variable could get 0. We need 3 dividers, so we have $32 +4 = 36$ objects, determining 35 gaps and pick 3 of them in $C(35,3)$ ways.
When one upper bound constraint is violated, we set aside 10 for the variable that is greater than 10. This variable must now still get at least 1 more meaning that we need only 3 artificial objects. Hence, we distribute $32 - 10 + 3 = 25$ objects, which determine 24 gaps. We must choose 3. There are $C(24,3)$ ways to do this.
When two upper bound constraints are violated, we set aside 10 for each variable that is greater than 10. These two variables must now still get at least 1 more, meaning that we need only 2 artificial objects. Hence, we distribute $32-10-10 + 2 = 14$ objects, which determine 13 gaps. We must still choose 3. There are $C(13,3)$ ways to do this.
Notice that there are $C(4,1)$ ways to pick a single upper bound constraint to violate and $C(4,2)$ ways to pick two upper bound constraints to violate. Thus, the total number of solutions is \[\begin{aligned}\end{aligned}\].
How many integer solutions are there to the inequality \[\begin{aligned}\end{aligned}\] with $y_1>0$, $0\lt y_2\leq 10$, $0\leq y_3\leq 17$, and $0\leq y_4 \lt 19$?
A graduate student eats lunch in the campus food court every Tuesday over the course of a $15$-week semester. He is joined each week by some subset of a group of six friends from across campus. Over the course of a semester, he ate lunch with each friend $11$ times, each pair $9$ times, and each triple $6$ times. He ate lunch with each group of four friends $4$ times and each group of five friends $4$ times. All seven of them ate lunch together only once that semester. Did the graduate student ever eat lunch alone? If so, how many times?
A group of $268$ students are surveyed about their ability to speak Mandarin, Korean, and Japanese. There are $37$ students who do not speak any of the three languages surveyed. Mandarin is spoken by $174$ of the students, Japanese is spoken by $139$ of the students, and Korean is spoken by $112$ of the students. The survey results also reflect that $102$ students speak both Mandarin and Japanese, $81$ students speak both Mandarin and Korean, and $71$ students speak both Japanese and Korean. How many students speak all three languages?
As in , let $X$ be the set of functions from $[n]$ to $[m]$ and let a function $f\in X$ satisfy property $P_i$ if there is no $j$ such that $f(j)=i$.
1. Let the function $f\colon [8]\to [7]$ be defined by . Does $f$ satisfy property $P_2$? Why or why not? What about property $P_3$? List all the properties $P_i$ (with $i\leq 7$) satisfied by $f$.
2. Is it possible to define a function $g\colon [8]\to [7]$ that satisfies no property $P_i$, $i\leq 7$? If so, give an example. If not, explain why not.
3. Is it possible to define a function $h\colon [8]\to [9]$ that satisfies no property $P_i$, $i\leq 9$? If so, give an example. If not, explain why not.
As in , let $X$ be the set of permutations of $[n]$ and say that $\sigma\in X$ satisfies property $P_i$ if $\sigma(i) = i$.
1. Let the permutation $\sigma\colon [8]\to [8]$ be defined by . Does $\sigma$ satisfy property $P_2$? Why or why not? What about property $P_6$? List all the properties $P_i$ (with $i\leq 8$) satisfied by $\sigma$.
2. Give an example of a permutation $\tau\colon[8]\to[8]$ that satisfies properties $P_1$, $P_4$, and $P_8$ and no other properties $P_i$ with $1\leq i\leq 8$.
3. Give an example of a permutation $\pi\colon [8]\to[8]$ that does not satisfy any property $P_i$ with $1\leq i\leq 8$.
As in , let $m$ and $n$ be positive integers and $X=[n]$. Say that $j\in X$ satisfies property $P_i$ for an $i$ with $1\leq i\leq m$ if $i$ is a divisor of $j$.
1. Let $m=n=15$. Does $12$ satisfy property $P_3$? Why or why not? What about property $P_5$? List the properties $P_i$ with $1\leq i\leq 15$ that $12$ satisfies.
2. Give an example of an integer $j$ with $1\leq j\leq 15$ that satisfies exactly two properties $P_i$ with $1\leq i\leq 15$.
3. Give an example of an integer $j$ with $1\leq j\leq 15$ that satisfies exactly four properties $P_i$ with $1\leq i\leq 15$ or explain why such an integer does not exist.
4. Give an example of an integer $j$ with $1\leq j\leq 15$ that satisfies exactly three properties $P_i$ with $1\leq i\leq 15$ or explain why such an integer does not exist.
How many surjections are there from an eight-element set to a six-element set?
A teacher has $10$ books (all different) that she wants to distribute to John, Paul, Ringo, and George, ensuring that each of them gets at least one book. In how many ways can she do this?
A supervisor has nine tasks that must be completed and five employees to whom she may assign them. If she wishes to ensure that each employee is assigned at least one task to perform, how many ways are there to assign the tasks to the employees?
A professor is working with six undergraduate research students. He has $12$ topics that he would like these students to begin investigating. Since he has been working with Katie for several terms, he wants to ensure that she is given the most challenging topic (and possibly others). Each topic must be assigned to a single student. Subject to this, in how many ways can he assign the topics to his students if each student must be assigned at least one topic?

Vis svaret

We do the counting here by considering two cases. First, we count where Katie receives only the one, hardest topic. Second, we count where Katie receives that topic and at least one additional topic. When Katie receives only the one, hardest topic, we just distribute the remaining 11 topics to the five other students using a surjection so each student gets at least one topic. There are $S(11,5)$ ways to do this. When Katie gets more than just the hardest topic, we still have 11 other topics to distribute, but now we must have a surjection to the set of all six students. Thus, there are $S(11,6)$ for this case. The total number is the sum of these: $S(11,5)+S(11,6)$.
List all the derangements of $[4]$. (For brevity, you may write a permutation $\sigma$ as a string $\sigma(1)\sigma(2)\sigma(3)\sigma(4)$.)
How many derangements of a nine-element set are there?
A soccer team's equipment manager is in a hurry to distribute uniforms to the last six players to show up before a match. Instead of ensuring that each player receives his own uniform, he simply hands a uniform to each of the six players. In how many ways could he hand out the uniforms so that no player receives his own uniform? (Assume that the six remaining uniforms belong to the last six players to arrive.)
A careless payroll clerk is placing employees' paychecks into envelopes that have been pre-labeled. The envelopes are sealed before the clerk realizes he didn't match the names on the paychecks with the names on the envelopes. If there are seven employees, in how many ways could he have placed the paychecks into the envelopes so that exactly three employees receive the correct paycheck?

Vis svaret

First we choose the three who do get the correct paycheck. There are $C(7,3)$ ways to do this. Then the other four checks must be distributed using a derangement, so we have \[\begin{aligned}\end{aligned}\] ways.
The principle of inclusion-exclusion is not the only approach available for counting derangements. We know that $d_1=0$ and $d_2=1$. Using this initial information, it is possible to give a recursive form for $d_n$. In this exercise, we consider two recursions for $d_n$.
1. Give a combinatorial argument to prove that the number of derangements satisfies the recursive formula $d_n = (n-1)(d_{n-1}+d_{n-2})$ for $n\geq 2$.
2. Prove that the number of derangements also satisfies the recursive formula $d_n = nd_{n-1} + (-1)^n$ for $n\geq 2$.
Vis svaret
Hint:
1. For a derangement $\sigma$, consider the integer $k$ with $\sigma(k)=1$. Argue based on the number of choices for $k$ and then whether $\sigma(1)=k$ or not.
2. You may find it easiest to prove this using the other recursive formula and mathematical induction.
Determine $\phi(18)$ by listing the integers it counts as well as by using the formula of .
Compute $\phi(756)$.
Given that $1625190883965792 = (2)^5(3)^4(11)^2(13)(23)^3(181)^2$, compute \[\begin{aligned}\end{aligned}\]
At a very small school, there is a class with nine students in it. The students, whom we will denote as $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$, and $I$, walk from their classroom to the lunchroom in the order $ABCDEFGHI$. (Let's say that $A$ is at the front of the line.) On the way back to their classroom after lunch, they would like to walk in an order so that no student walks immediately behind the same classmate he or she was behind on the way to lunch. (For instance, $ACBDIHGFE$ and $IHGFEDCBA$ would meet their criteria. However, they would not be happy with $CEFGBADHI$ since it contains $FG$ and $HI$, so $G$ is following $F$ again and $I$ is following $H$ again.)
1. One student ponders how many possible ways there would be for them to line up meeting this criterion. Help him out by determining the exact value of this number.
2. Is this number bigger than, smaller than, or equal to the number of ways they could return so that no student walks in the same position as before (, $A$ is not first, $B$ is not second, , and $I$ is not last)?
3. What fraction (give it as a decimal) of the total number of ways they could line up meet their criterion of no student following immediately behind the same student on the return trip?
Suppose that $m=4$. How many terms are there in the sum \[\begin{aligned}\end{aligned}\]?
Which of the following functions from $[6]$ to $[4]$ are surjections? \[\begin{aligned}\end{aligned}\]
Let $X$ be the set of all functions from $[n]$ to $[m]$. What is the size of $X$?
Define $f\colon [8] \to [5]$ as shown below. Which properties does $f$ satisfy? \[\begin{aligned}\end{aligned}\]
Consider the set $X$ of all permutations of $[n]$. What is the size of $X$?
A permutation $\sigma$ of $[n]$ satisfies property $P_{i}$ if $\sigma(i)=i$.
Define $\sigma\colon [6]\to [6]$ as shown in the table below. Which properties does $\sigma$ satisfy?
\[\begin{aligned}\end{aligned}\]
Of the following integers, which are relatively prime to $10$?

Symbols used here

\pi

pi
Ratio of a circle's circumference to its diameter, 3.14159…

x \in A,\ A \subseteq B

element of, subset
x belongs to A; every element of A is in B.

\sigma,\ s,\ \sigma^2

standard deviation, sample s.d., variance
Typical distance from the mean; its square.

imaginary unit
i² = −1.

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Prøv din egen

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

Mer i Combinatorics & Graph Theory

The counting principles Pigeonhole principle and inclusion–exclusion Binomial coefficients and Pascal's triangle Recurrences and generating functions Graphs: vertices, edges, degrees Paths, cycles, trees, Euler and Hamilton Colouring and planar graphs