(+)분류 : 가져온 문서/오메가
Inclusion–exclusion principle
유한집합의 합집합의 원소의 개수를 나타내는 공식이다.
1. 진술 ✎ ⊖
유한집합 A_1,A_2,\\cdots,A_n에 대해, 다음 식이 성립한다.
더 간단하게 표현하면,
을 얻는다.
\\displaystyle |A_1 \\cup A_2 \\cup \\cdots \\cup A_n|=\\sum_{1\\le i \\le n}|A_i|-\\sum_{1\\le i<j \\le n}|A_i\\cap A_j| + \\sum_{1\\le i<j<k \\le n}|A_i\\cap A_j \\cap A_k| +\\cdots+(-1)^{n+1}|A_1\\cap A_2\\cap \\cdots \\cap A_n|
더 간단하게 표현하면,
\\displaystyle \\left\\vert\\bigcup_{i=1}^n A_i\\right\\vert=\\sum_{k=1}^n(-1)^{k+1}\\left( \\sum_{1\\le i_1 < <\\cdots < i_k\\le n}| A_{i_1}\\cap\\cdots\\cap A_{i_k}|\\right)
을 얻는다.
