Rare
0/5

# 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.

## Tutorial

Resources
CP Algorithm Well-covered article
WikipediaWiki

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:

$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n|A_i| - \sum_{1\leq i

Written in a compact form:

$\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\}$ depending on number's factorization.

$\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 $20$ values of $\mu(n)$:

n12345678910111213141516171819
$\mu(n)$1-1-10-11-1001-10-1110-10-1

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

C++

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]; }	}}

## Applications

### SQFREE

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 $A_i$ - previously mentioned in the tutorial section - denotes how many numbers are numbers are divisible with $i^2$ and we're asked to find out $\bigg| \bigcup_{i=1}^{\sqrt{n}} A_i \bigg|$. the precomputed mobius array tells whether to add or substract $A_i$.

C++

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

### Cowpatibility

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

View Internal Solution

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

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

C++

#include <bits/stdc++.h>
using namespace std;
int main() {	ifstream in("cowpatibility.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] = \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[i-1][j]\text{ where j is a set of patterns that match charachter c at position i}$

The following code illustrates this:

C++

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 $a$ to $z$ giving us $26$ solution, otherwise we can only put the fixed letter contained by a pattern. The answer is the product.

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

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

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

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

C++

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
SPOJMedium
Show TagsDivisors, PIE
SPOJMedium
Show TagsDivisors, PIE

### 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!