[Tutorial] Inclusion-Exclusion Principle, Part 1.

Правка en5, от Roundgod, 2019-01-18 18:41:06

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

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 Princinple, 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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.\n**Princi' -> 'clusion.\n\n**Princi'
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)