목록합집합 공식 (1)
코딩딩딩
(python)포함-배제 원칙(The principle of Inclusion-exclusion)
1. 개념 포함-배제 원칙은 합집합의 원소의 개수를 구하는 것과 동일하다고 볼 수 있다. 집합 2개: |A∪B| = |A| + |B| - |A∩B| 집합 3개: |A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C| 집합 4개: |A∪B∪C∪D | = |A| + |B| + |C| + |D| - |A∩B| - |A∩C| - |B∩C| - |A∩D| - |B ∩D| - |C∩D| + |A∩B∩C| + |A∩B∩D| + |A∩C∩D| + |B∩C∩D| - |A∩ B∩C∩D| 위의 공식에서 나타나듯이 집합의 개수를 늘려가면서 교집합 연산을 하는 것을 확인할 수 있다. 부호는 양수, 음수를 번갈아 가며 나타난다. 그러므로 집합 n개에 대하여 아래와 같은 공식이 ..
이산수학 프로그래밍
2022. 11. 20. 18:00