Inclusion-Exclusion Principle

Author: Mihnea Brebenel

The inclusion-exclusion principle is a counting technique that generalizes the formula for computing the size of union of n finite sets.

Edit This Page


CP Algorithm Well-covered article

The inclusion-exclusion principle relates to finding the size of the union of some sets.

Verbally it can be stated as following:

Sum the sizes of the sets separately, substract the sizes of all pairwise intersections of the sets, add back the sizes of intersections of triples of the sets, substract the size of quadruples of the sets, ...

The mathematical identity of the above is:

i=1nAi=i=1nAi1i<jnAiAj+1i<j<knAiAjAk+(1)n1A1An\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n|A_i| - \sum_{1\leq i<j\leq n} |A_i \cap A_j| + \sum _{1\leq i<j<k\leq n}|A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} | A_1 \cap \cdots \cap A_n |

Written in a compact form:

i=1nAi=0J{1,2,...,n}(1)J1jJAj\bigg|\bigcup_{i=1}^nA_i \bigg|= \sum_{0 \neq J \in \{1, 2,...,n\} } (-1)^{|J|-1} \bigg| \bigcap_{j \in J} A_j \bigg|

Mobius Function

The Mobius function is a multiplicative function that comes in handy when dealing with inclusion-exclusion technique and divisors-related problems. It has values in {1,0,1}\{-1, 0, 1\} depending on number's factorization.

μ(n)={1if n is 1,0if n has a squared prime factor,(1)kif n is a product of k distinct prime factors.\mu(n)=\begin{cases} 1 & \text{if $n$ is $1$},\\ 0 & \text{if $n$ has a squared prime factor},\\ (-1)^k & \text{if $n$ is a product of $k$ distinct prime factors}. \end{cases}

Belowe you can see the first 2020 values of μ(n)\mu(n):


Let's take a look at how the mobius function can be precomputed with a slightly modified sieve.


mobius[1] = -1;
for (int i = 1; i < VALMAX; i++) {
if (mobius[i]) {
mobius[i] = -mobius[i];
for (int j = 2 * i; j < VALMAX; j += i) { mobius[j] += mobius[i]; }



Focus Problem – try your best to solve this problem before continuing!

A perfect application for inclusion-exclusion principle and mobius function. In this particular case the set AiA_i - previously mentioned in the tutorial section - denotes how many numbers are numbers are divisible with i2i^2 and we're asked to find out i=1nAi\bigg| \bigcup_{i=1}^{\sqrt{n}} A_i \bigg|. the precomputed mobius array tells whether to add or substract AiA_i.


#include <iostream>
#include <vector>
using namespace std;
const int VALMAX = 2e7;
int mobius[VALMAX];
int main() {


Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

In this particular case the set AiA_i - previously mentioned in the tutorial section - denotes how many pairs of cows have at least ii ice cream flavors in common. From the total number of pairs substract the union of AiA_i. The global answer is:

n(n1)2i=15Ai\frac{n \cdot(n-1)}{2}- \bigg| \bigcup_{i=1}^{5} A_i \bigg|


#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream in("");
int n;
in >> n;
map<vector<int>, int> subsets;

The number of strings that match a certain pattern

Focus Problem – try your best to solve this problem before continuing!

A dynamic programming approach with bitmasking would look like this: dp[i][mask]=the number of strings of length i that match all the patterns in set, but none other patterns. dp[i][mask] = \text{the number of strings of length i that match all the patterns in set, but none other patterns. } The recurrence is:

dp[i][mask&j]=dp[i1][j] where j is a set of patterns that match charachter c at position idp[i][mask \& j]=dp[i-1][j]\text{ where j is a set of patterns that match charachter c at position i}

The following code illustrates this:


int howMany(vector<string> patterns, int k) {
vector<vector<int>> dp(50, vector<int>((1 << (int)patterns.size())));
for (int i = 0; i < (int)patterns[0].size(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
int mask = 0;
for (int j = 0; j < (int)patterns.size(); j++) {
if (patterns[j][i] == c || patterns[j][i] == '?') {
mask |= (1 << j);

The problem can also be solved using the inclusion exclusion principle.

An important observation is that we can easily count the strings that satisfy some specific patterns. Simply iterate through the positions of all patterns. If all the patterns contain ?? then we can use any letter from aa to zz giving us 2626 solution, otherwise we can only put the fixed letter contained by a pattern. The answer is the product.

Iterate over subsets - denoted by AA - of patterns consisting of exactly kk strings. For this specific subset count the number of string that can only match all the patterns in subset AA. Apply the inclusion-exclusion principle over all supersets BB such that ABA \subset B.

solve(A)=BA(1)Bkf(B)solve(A) = \sum_{B \supseteq A} (-1)^{|B|-k} \cdot f(B)

f(B)f(B) denotes the number of strings matching at leat set BB

The global answer is:

ans=A:A=ksolve(A)ans = \sum_{A:|A|=k} solve(A)


int howMany(vector<string> patterns, int k) {
int ans = 0;
for (int mask = 0; mask < (1 << (int)patterns.size()); mask++) {
if (__builtin_popcount(mask) == k) {
for (int supermask = mask; supermask < (1 << (int)patterns.size());
supermask++) {
if ((mask & supermask) == mask) {
int sign =
((__builtin_popcount(supermask) - k) & 1 ? -1 : 1);
int cnt = 1;
StatusSourceProblem NameDifficultyTags
Show TagsDivisors, PIE
Show TagsDivisors, PIE

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!