조합론의 포함-배제 원리: 세트 크기를 쉽게 계산하기
포함-배제 원리는 조합론에서 집합을 더 작은 하위 집합으로 나누고 교차점을 계산하여 집합의 크기를 계산하는 데 사용되는 기술입니다. 이는 A와 B라는 두 개의 세트가 있고 두 세트 모두에 있는 요소의 수를 계산하려면 A와 B의 총 요소 수에서 A에만 있는 요소를 빼면 계산할 수 있다는 아이디어에 기초합니다. A, 그런 다음 B.
More에만 있는 요소를 다시 추가합니다. 공식적으로 A와 B를 두 세트로 두고 |A| A에 있는 요소의 개수입니다. 그러면 포함-배제 원칙에 따라 다음과 같이 됩니다.
|A ∪ B| = |아| + |B| - |A ∩ B|
where |A ∪ B| 는 A와 B의 합집합에 포함된 요소의 개수이고, |A ∩ B| 는 A와 B 모두에 있는 요소의 수입니다.
이 공식의 기본 아이디어는 먼저 각 집합의 요소 수를 개별적으로 계산한 다음 해당 요소를 빼서 두 집합의 합집합 크기를 계산할 수 있다는 것입니다. 세트 중 하나(즉, 교차점의 요소)에만 있습니다. 이는 합집합의 총 요소 수를 제공하며, 이는 각 집합의 요소 수에서 집합 중 하나에만 있는 요소 수를 뺀 값입니다. 예를 들어, 두 개의 집합이 있다고 가정해 보겠습니다. A = {1, 2, 3} 및 B = {4, 5, 6}. 포함-배제 원칙을 사용하여 합집합의 크기를 계산하려면 먼저 각 집합의 요소 수를 개별적으로 계산합니다.
|A| = 3
|B| = 3
다음으로 교차점을 계산하여 두 세트에 있는 요소의 수를 계산합니다.
|A ∩ B| = 2 (1과 2가 두 세트 모두에 있으므로)
이제 포함-배제 원칙을 사용하여 합집합의 크기를 계산할 수 있습니다.
|A ∪ B| = |A| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6
따라서 A와 B의 합집합의 크기는 6입니다.
포함 배제 원리는 순열, 조합 및 해의 수를 세는 등 조합론에서 많은 응용 분야를 가지고 있습니다. 방정식에. 계산 문제를 해결하는 강력한 도구이며 복잡한 계산을 단순화하는 데 사용할 수 있습니다.
이 동영상이 마음에 듭니다.
이 동영상이 마음에 들지 않습니다.
콘텐츠 오류 보고
공유
