[Tutorial] Inclusion-Exclusion Principle, Part 1.

Revision en10, by Roundgod, 2019-01-18 20:01:13

Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate calabash_boy is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book Graduate Text in Mathematics 238, A Course in Enumeration, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yourself. I'll start with the basic formula, one can choose to skip some of the text depending on your grasp with the topic.

Consider a finite set X and three subsets A, B, C, To obtain , we take the sum + + . Unless A, B, C are pairwise distinct, we have an overcount, since the elements of has been counted twice. So we subtract . Now the count is correct except for the elements in which have been added three times, but also subtracted three times. The answer is therefore

, or equivalently,

The following formula addresses the case applied to more sets.

The Restricted Inclusion-Exclusion Principle. Let A1, A2, ..., An be subsets of X. Then

This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets. It's not hard to prove the correctness of this formula, we can just check how often an element is counted in both sides. If , then it's counted once on either side. Suppose , and more precisely, that x is in exactly m of the sets Ai. The count on the left-hand side is 0, and on the right hand side, we have

for m ≥ 1, thus the equality holds.

Example 1. Let's see an example problem Co-prime where this principle could be applied: Given N, L, R, you need to compute the number of integers x in the interval [L, R] such that x is coprime with N, that is, gcd(x, N) = 1. There are 1 ≤ T ≤ 100 testcases. Constraints: 1 ≤ N ≤ 109, 1 ≤ L ≤ R ≤ 1015.

Solution

The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set X, called the universe, and a set E = {e1, e2, ..., en} of properties that the elements of X may or may not process. Here we can define the properties as we like, such as e = " ≤ 5", , or even . Let Ai be the subset of elements that enjoy property ei(and possibly others). Then is the number of elements that process none of the properties. Clearly, Ai1, Ai2, ..., Ait is the set of elements that possess the properties ei1, ei2, ..., eit(and maybe others). Using the notation

we arrive at the principle of inclusion-exclusion.

Principle of Inclusion-Exclusion. Let X be a set, and E = {e1, e2, ..., en} a set of properties. Then

The formula becomes even simpler when Nsupseteq T depends only on the size . We can then write Nsupseteq T = N ≥ k for , and call E a homogeneous set of properties, and in this case N = T = N = k also depends only on the cardinality of T. Hence for homogeneous properties, we have

This is the very essence of Principle of Inclusion-Exclusion. Please make sure you understand every notation before you proceed. One can figure out, by letting , we arrive at the restricted inclusion-exclusion principle.

Example 2. This problem Character Encoding requires you to compute the number of solutions to the equation x1 + x2 + ... + xn = k, satisfying that 0 ≤ xi < m? Constraints: . Hint: the number of non-negative integer solutions of x1 + x2 + dots + xn = k is given by .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en27 English Roundgod 2022-01-07 09:58:51 9
en26 English Roundgod 2020-11-01 10:27:44 2
en25 English Roundgod 2020-10-13 21:06:15 4 Tiny change: 'irwise distinct, we have' -> 'irwise disjoint, we have'
en24 English Roundgod 2019-03-23 21:22:54 8 Tiny change: '-j,j)+g(i-1,j-1)-g(i-j-N,j-1)$. An' -> '-j,j)+g(i-j,j-1)-g(i-(N+1),j-1)$. An'
en23 English Roundgod 2019-03-22 11:04:49 13 Tiny change: 'g(i-1,j-1)$. An' -> 'g(i-1,j-1)-g(i-j-N,j-1)$. An'
en22 English Roundgod 2019-03-22 10:30:16 2 Tiny change: 'ts_{i\geq 1}(-1)^{i}g' -> 'ts_{i\geq 0}(-1)^{i}g'
en21 English Roundgod 2019-03-22 10:27:48 2 Tiny change: '-j,j)+g(i-j,j-1)$. An' -> '-j,j)+g(i-1,j-1)$. An'
en20 English Roundgod 2019-01-19 16:24:31 2 Tiny change: '\n$$N_{\subseteq T}:=' -> '\n$$N_{\supseteq T}:='
en19 English Roundgod 2019-01-19 10:10:02 2 Tiny change: '1}\cdot f(i)$$\n\nwhe' -> '1}\cdot f(s)$$\n\nwhe'
en18 English Roundgod 2019-01-18 23:20:27 5
en17 English Roundgod 2019-01-18 22:39:48 1 Tiny change: ' for the $\relax i$th eleme' -> ' for the $i$th eleme'
en16 English Roundgod 2019-01-18 21:44:53 7 Tiny change: '}"$. Let $A_i$ be th' -> '}"$. Let $\relax A_i$ be th'
en15 English Roundgod 2019-01-18 21:34:57 697 (published)
en14 English Roundgod 2019-01-18 21:27:56 1521
en13 English Roundgod 2019-01-18 21:06:41 613
en12 English Roundgod 2019-01-18 20:59:52 2119 Tiny change: 'ution is $O(n)$, due' -> 'ution is $\reO(n)$, due'
en11 English Roundgod 2019-01-18 20:23:49 1028 Tiny change: 'hen write $N_{\sups' -> 'hen write \n $N_{\sups'
en10 English Roundgod 2019-01-18 20:01:13 2 Tiny change: '\leq x_{i}\< m$? Cons' -> '\leq x_{i} < m$? Cons'
en9 English Roundgod 2019-01-18 20:00:40 1594 Tiny change: 'clusion.\n**Princi' -> 'clusion.\n\n**Princi'
en8 English Roundgod 2019-01-18 19:36:24 1162
en7 English Roundgod 2019-01-18 19:16:44 1245 Tiny change: 'm}=0$$ for $m\geq 1$,' -> 'm}=0$$ for$m\geq 1$,'
en6 English Roundgod 2019-01-18 18:49:31 699
en5 English Roundgod 2019-01-18 18:41:06 583
en4 English Roundgod 2019-01-18 18:21:38 58
en3 English Roundgod 2019-01-18 18:17:55 472
en2 English Roundgod 2019-01-18 18:14:24 423
en1 English Roundgod 2019-01-18 18:09:36 831 Initial revision (saved to drafts)