[Tutorial] Inclusion-Exclusion Principle, Part 1.

Revision en1, by Roundgod, 2019-01-18 18:09:36

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

Consider a finite set X and three subsets A, B, C

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)