Inclusion–Exclusion Principle

Introduction

Is it $10+15+21=46$ students? No, because some students may like both mathematics and Chinese, or Chinese and programming, and some may even like all three.

For convenience, let the sets of students who like Chinese, mathematics, and programming be $A,B,C$, respectively. Then the total number of students is $|A\cup B\cup C|$. As noted above, directly adding the cardinalities $|A|,|B|,|C|$ of these three sets counts some elements more than once, so we must subtract $|A\cap B|,|B\cap C|,|C\cap A|$. This subtracts a small part too many times, however, so we add it back as $|A\cap B\cap C|$. Thus

This generalization of the problem is the familiar inclusion–exclusion principle.

Definition

Suppose the elements of U have n different properties, and call the i-th property $P_i$. The elements having property $P_i$ form the set $S_i$. Then

That is,

Proof

For each element, use the binomial theorem to calculate how many times it appears. For an element x, suppose it belongs to the sets $T_1,T_2,\cdots,T_m$. Its number of appearances is

Thus each element appears exactly once, and combining all elements gives the union. QED.

Complements

For the union of sets in a universal set U, we can use inclusion–exclusion. The intersection of sets can instead be obtained by subtracting the union of the complements from the universal set:

The right-hand side can be expanded by inclusion–exclusion.

Readers who have encountered inclusion–exclusion are familiar with the material above; what matters more are its applications.

We next give three examples at different levels to demonstrate applications of the inclusion–exclusion principle.

Counting Nonnegative Integer Solutions of an Indeterminate Equation

Without Constraints

If there is no constraint $x_i\leq b_i$, the number of nonnegative integer solutions to the equation $\sum_{i=1}^nx_i=m$ is $\dbinom{m+n-1}{n-1}$.

A brief proof uses the stars-and-bars method.

Equivalently, distribute $m$ balls among $n$ boxes, allowing a box to be empty. This cannot be solved directly with a binomial coefficient.

Add $n-1$ more balls. The problem becomes choosing balls from a sequence of length $m+n-1$; specifically, choose $n-1$ balls. These $n-1$ balls divide the sequence into $n$ parts, which correspond one-to-one to distributions into $n$ boxes. Thus, the number of ways to choose from $m+n-1$ balls, selecting $n-1$, is $\dbinom{m+n-1}{n-1}$.

Inclusion–Exclusion Model

Let us abstract the model of inclusion–exclusion:

1. Universal set U: the nonnegative integer solutions of $\sum_{i=1}^nx_i=m$
2. Elements: the variables $x_i$.
3. Property: the property of $x_i$ is the condition satisfied by $x_i$, namely the condition $x_i\leq b_i$.

The goal is the size of the set in which all variables satisfy their corresponding properties, namely $|\bigcap_{i=1}^nS_i|$.

This can be computed using $\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$. The quantity $|U|$ can be computed with a binomial coefficient, while the latter part is naturally expanded by inclusion–exclusion.

The problem therefore becomes finding the size of an intersection of some $\overline{S_{a_i}}$. Consider the meaning of $\overline{S_{a_i} }$: it counts solutions satisfying $x_{a_i}\geq b_{a_i}+1$. Their intersection means satisfying all these conditions simultaneously. Thus, in the corresponding indeterminate equation, some variables have lower-bound constraints, while others have none.

Can these lower-bound constraints be removed? We seek nonnegative integer solutions, and some variables have a lower bound greater than $0$. We can simply subtract this lower bound, making the lower bound $0$, i.e. removing it. Therefore, for

the indeterminate equation has the form

This can also be evaluated with a binomial coefficient. The length-$k$ $a$ array is effectively enumerating subsets.

HAOI2008 Coin Shopping

A knapsack solution would have complexity $O(4nS)$, which is too large. The most notable feature is that there are only four coin types. Abstractly, we need the number of nonnegative integer solutions to $\sum_{i=1}^4C_ix_i=S,x_i\leq D_i$.

Using the same inclusion–exclusion method, the property of $x_i$ is $x_i\leq D_i$. Applying the inclusion–exclusion formula, we ultimately need to solve

which is an unbounded knapsack problem. It can be precomputed; including the queries, the total complexity is $O(4S+2^4n)$.

#include <iostream>
using namespace std;
constexpr long long S = 1e5 + 5;
long long c[5], d[5], n, s;
long long f[S];

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
  f[0] = 1;
  for (long long j = 1; j <= 4; j++)
    for (long long i = 1; i < S; i++)
      if (i >= c[j]) f[i] += f[i - c[j]];  // f[i]: number of ways to form price i with the coins
  for (long long k = 1; k <= n; k++) {
    cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
    long long ans = 0;
    for (long long i = 1; i < 16;
         i++) {  // Inclusion-exclusion: there are four item types, so iterate from 1 to 2^4-1=15
      long long m = s, bit = 0;
      for (long long j = 1; j <= 4; j++) {
        if ((i >> (j - 1)) % 2 == 1) {
          m -= (d[j] + 1) * c[j];
          bit++;
        }
      }
      if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
    }
    cout << f[s] - ans << '\n';
  }
  return 0;
}

Coloring a Complete-Graph Subgraph

The first three examples use inclusion–exclusion directly; this problem requires analyzing it in reverse.

Mathematical Form

The algorithmic direction is not obvious at first glance, so for a difficult problem we first abstract its mathematical form. The score difference is an alternating sum, so powers of -1 can serve as coefficients. We seek

Inclusion–Exclusion Model

We treat the requirement that adjacent vertices have the same color as a property. For now, ignore the coloring rule and color the graph directly with m colors. For the graph $G'=(V,S)$, regard a coloring as an element. The property $x_i=x_j$ means that vertices i and j have the same color (there need not be an edge between i and j).

Define the set corresponding to property $x_i=x_j$ as $Q_{i,j}$. It consists of all colorings of graphs $G'$ satisfying that property; its size is the number of colorings satisfying the property, and its elements can be viewed as the colored graphs $G'$ satisfying it.

Returning to the problem, “adjacent vertices must have the same color” can be understood as an intersection of several $Q$ sets. Hence

The right-hand side says that every edge $(i,j)$ in S satisfies $x_i=x_j$; its number of colorings is therefore $F(S)$.

Does this look like inclusion–exclusion? Since inclusion–exclusion has no native pair form, map all edges $(i,j)$ to $T=\frac{n(n+1)}{2}$ integers. Suppose $(i,j)$ maps to $k,1\leq k\leq T$, and $Q_{i,j}$ maps to $Q_k$. Then define the property $x_i=x_j$ as $P_k$.

Similarly, S can be represented as a set of several k values, namely $S\iff K=\{k_1,k_2,\cdots,k_m\}$. (In other words, we establish an equivalence between edge sets and sets of integers.)

The edge set E corresponds to the set $M=\left\{1,2,\cdots,\frac{n(n+1)}{2}\right\}$. Therefore,

Reverse Analysis

Expanding the desired expression gives

This is exactly the expansion of inclusion–exclusion, so we derive the expression in reverse:

Now consider the meaning of the right-hand side. It requires satisfying any one of the $1\sim T$ conditions, meaning the number of colorings in which some two vertices have the same color (not necessarily adjacent). The universal set of colorings is $U$, clearly $|U|=m^n$. Passing to the complement means counting colorings in which every pair has different colors, namely $A_m^n=\frac{m!}{(m-n)!}$. Therefore,

To solve this problem, first abstract its mathematical form. Then start from the most informative condition, the definition of the function $F(S)$, and convert it into intersections, unions, and complements of sets. Finally, transform the expression into the form of inclusion–exclusion and derive it in reverse. This problem demonstrates the reverse use of inclusion–exclusion.

Inclusion–Exclusion in Number Theory

Inclusion–exclusion can be used cleverly to solve number-theoretic problems.

Counting Pairs with GCD k

Consider the following problem:

This can be solved with the Euler totient function or Möbius inversion, but inclusion–exclusion is simpler.

By inclusion–exclusion, first find all pairs for which $k$ is a common divisor, then remove all pairs for which a multiple of $k$ is a common divisor. The remaining pairs are those for which $k$ is the greatest common divisor. In other words, $f(k)=$ is the number of pairs for which $k$ is a common divisor $-$ the number of pairs for which a multiple of $k$ is a common divisor.

It is also easy to see that the number of pairs for which a multiple of $k$ is a common divisor equals the sum of the numbers of pairs for which multiples of $k$ are the greatest common divisor. Hence,

When $k>N/2$, we can directly calculate $f(k)= \lfloor (N/k) \rfloor ^2$. Therefore, we can work backward from $f(N)$ down to $f(1)$. This completes the problem using inclusion–exclusion.

for (long long k = N; k >= 1; k--) {
  f[k] = (N / k) * (N / k);
  for (long long i = k + k; i <= N; i += k) f[k] -= f[i];
}

The time complexity of the method above is $O( \sum_{i=1}^{N} N/i)=O(N \sum_{i=1}^{N} 1/i)=O(N \log N)$.

Here are three extra practice problems:

• Luogu P2398 GCD SUM
• Luogu P2158[SDOI2008] Guard Team
• Luogu P1447[NOI2010] Energy Collection

Deriving the Euler Totient Function by Inclusion–Exclusion

Consider the following problem:

Direct computation takes $O(n\log n)$ time, a linear sieve takes $O(n)$ time, and the Du sieve takes $O(n^{\frac{2}{3}})$ time (although it is odd to bring up the Du sieve in an introductory number-theory problem solved by inclusion–exclusion). We now derive the Euler totient formula using inclusion–exclusion.

To determine whether two numbers are coprime, first factorize

For every $p_i$, we require that $x$ is not a multiple of $p_i$, namely $p_i\nmid x$. Treat this as a property, with corresponding set $S_i$. Thus,

The universal set has size $|U|=n$. The set $\overline{S_i}$ consists of values satisfying $p_i\mid x$, so clearly $|\overline{S_i}|=\frac{n}{p_i}$. Therefore,

It follows that

This is the mathematical expression for the Euler totient function.

Generalization of Inclusion–Exclusion

The inclusion–exclusion principle is often used for set-counting problems. For functions $f(S),g(S)$ on subsets, if

then

Proof

We give a brief proof, starting from the right-hand side:

The latter summation is independent of $Q$, so remove the latter $Q$:

For a set $P$, define the function $F(P)=\sum_{T\subseteq P}(-1)^{|P|-|T|}$ and simplify it:

Thus the value of the original expression is

Only when $|S\setminus Q|=0$ do we have $0^0=1$; then $Q=S$, whose contribution to the answer is $g(S)$. In all other cases $0^{|S\setminus Q|}=0$, so there is no contribution. Hence

This proves the result.

Corollary

There is also the following corollary. Under the universal set $U$, for functions $f(S),g(S)$, if

then

This corollary is the complement form; the proof is similar.

Counting DAGs

Direct DP

Consider a DP. Define $f[i,j]$ as the number of DAGs on $i$ vertices with exactly $j$ vertices of indegree $0$. Suppose that after removing these $j$ vertices, there are $k$ vertices of indegree $0$. Before removal, each of these $k$ vertices must have an edge from at least one of the $j$ removed vertices, giving $2^j-1$ possibilities. The $j$ removed vertices may also connect arbitrarily to the remaining vertices other than the $k$ vertices, giving $2^{i-j-k}$ possibilities. Thus,

The complexity of computing this expression is $O(n^3)$.

Relaxing the Constraint

The DP above defines exactly $j$ vertices of indegree $0$, which is too restrictive. We may instead require at least $j$ vertices of indegree $0$. Define $f[i]$ directly as the number of DAGs on $i$ vertices. Inclusion–exclusion applies directly. For the selected $j$ vertices, each of these $j$ vertices may have arbitrary edges to the remaining $i-j$ vertices, giving $\left(2^{i-j}\right)^j=2^{(i-j)j}$ possibilities:

The complexity of this expression is $O(n^2)$.

Min–Max Inclusion–Exclusion

For a sequence $\{x_i\}$ whose elements lie in a total order total order and support addition and subtraction, let its length be $n$ and let $S=\{1,2,3,\cdots,n\}$. Then

Proof: Map this to the ordinary inclusion–exclusion principle. For $x\in S$, suppose $x$ is the $k$-th smallest element. Define the map $f:x\mapsto \{1,2,\cdots,k\}$. Clearly, this is a bijection.

For $x,y\in S$, it is easy to see that $f(\min(x,y))=f(x)\cap f(y)$ and $f(\max(x,y))=f(x)\cup f(y)$. Therefore,

Now map $\left|f\left(\max_{i\in S}{x_i}\right)\right|$ back to $\max_{i\in S}{x_i}$; the case for $\min$ is analogous.

QED.

You may find this formula pointless because a maximum can be computed directly. Min–max inclusion–exclusion is important because it also holds for expectations:

Proof: Consider one way to calculate an expectation:

Here $y$ is a sequence of length $n$.

Apply the previous formula to the $\max$ that follows:

Swap the order of summation:

The case for $\min$ is analogous.

QED.

There is an even stronger form:

By convention, if $n< m$, then $\dbinom nm=0$.

Proof: Without loss of generality, assume $\forall 1\le i<n,x_i\le x_{i+1}$. Then

Using the combinatorial identity $\dbinom ab\dbinom bc=\dbinom ac\dbinom {a-c}{b-c}$, we obtain

When $i=n-k+1$,

Otherwise,

Therefore,

The other three identities are analogous.

QED.

Min–max inclusion–exclusion also gives

Because $\operatorname{lcm},\gcd,a^{1},a^{-1}$ correspond respectively to $\max,\min,+,-$, this is exactly min–max inclusion–exclusion applied to the exponents, so the identity follows.

PKUWC2018 Random Walk

The number of steps in the random walk is its elapsed time. Let the random variable $x_i$ be the first time the walk reaches vertex $i$. We seek

Min–max inclusion–exclusion gives

For a set $T\in[n]$, consider computing $F(T)=E(\min_{i\in T}x_i)$.

The meaning of $E(\min_{i\in T}x_i)$ is the expected time to first reach some vertex in $T$. Let $f(i)$ denote the expected time to first reach a vertex when starting from vertex $i$ in $T$.

• For $i\in T$, $f(i)=0$.
• For $i\notin T$, $f(i)=1+\frac{1}{\text{deg}(i)}\sum_{(i,j)\in E}f(j)$.

Gaussian elimination would take $O(n^3)$ time. Then, for each set $T$, computing $F(T)$ would give total complexity $O(2^nn^3)$, which is unacceptable. We use elimination on a tree.

Let the root be $1$, and let the parent of vertex $u$ be $p_u$. For a leaf $i$, $f(i)$ depends only on the parent $i$ (and it may even be $f(i)=0$, which is easier). Thus we can write $f(i)$ in the form $f(i)=A_i+B_if(p_i)$, where $A_i,B_i$ can be computed quickly.

For a non-leaf vertex $i$, consider its sequence of children $j_1,\cdots,j_k$. Since $f(j_e)=A_{j_e}+B_{j_e}f(i)$, we obtain

Rearranging gives

Thus $f(i)$ can also be written in the form $A_i+B_if(p_i)$. We can continue this backward to the root. The root has no parent, so

Solving this equation gives $f(1)$; one downward pass then gives every vertex's $f(i)$. Thus $F(T)=f(x)$, with time complexity $O(n)$.

We can therefore, for every $T$, compute $F(T)$ in time $O(2^nn)$.

Returning to inclusion–exclusion, we know that $E(\max_{i\in S}x_i)=\sum_{T\subseteq S}(-1)^{|T|-1}F(T)$.

Let $F'(T)=(-1)^{|T|-1}F(T)$. Then $E(\max_{i\in S}x_i)=\sum_{T\subseteq S}F'(T)$. Therefore, in time $O(2^nn)$, for every $S$ we compute $E(\max_{i\in S}x_i)$, and answer each query in $O(1)$.

Exercises

• ABC331-G — Collect Them All
• Luogu P4707 Return to the Present

References

A Brief Exploration of the Inclusion–Exclusion Principle — Wang Di, 2013 Collection of Papers by Candidates for the Chinese National Team in the Informatics Olympiad

Counting Series of Labeled DAGs — Cyhlnj

Total Order — Wikipedia