[Tutorial] Inclusion-Exclusion Principle, Part 1.

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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, To obtain $\text{[math]}$ , we take the sum $\text{[math]}$ + $\text{[math]}$ + $\text{[math]}$ . Unless A, B, C are pairwise distinct, we have an overcount, since the elements of $\text{[math]}$ has been counted twice. So we subtract $\text{[math]}$ . Now the count is correct except for the elements in $\text{[math]}$ which have been added three times

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

History