Inclusion and Exclusion: 포함배제 원리

Inclusion and Exclusion, Inclusion-Exclusion, 포함배제, 포함 배제

정의

$$\left|\bigcup _{\{}i=1{\}}^{\{}n\}{A}_i\right|=\sum |A_i|-\sum |A_i\cap A_j|+\sum |A_i\cap A_j\cap A_k|-\dots$$

부호가 교대로 바뀌며 홀수 개 교집합 - 짝수 개 교집합.

응용

오일러 phi

$\phi (n)=n{\prod }_{\{}p|n\}(1-1/p)$ 는 포함배제의 예.

mod 카운팅

n 이하 중 어느 소수의 배수도 아닌 수의 개수:

$$\sum _{\{}S\subseteq \{p_1,...,p_k\}\}(-1{)}^{\{}|S|\}\lfloor n/\prod S\rfloor$$

Derangement

$D_n=n!{\sum }_{\{}k=0{\}}^{\{}n\}\frac{\{}{(}-1{)}^k\}\{k!\}$

참고

• Euler Phi
• 조합론
• Mobius Inversion