이 단원 목차
집합을 더할 때 왜 빼야 할까
두 데이터셋 A와 B를 합친다고 합집합 크기가 두 크기의 합은 아닙니다. 같은 관측이 두 곳에 들어 있으면 두 번 세어집니다. 실습의 전체 집합 U는 {0,1,2,3,4,5}이고 A={0,1,2}, B={2,3,4}입니다. 두 크기를 더하면 6이지만 서로 다른 원소는 다섯 개입니다.
원소별 지시함수를 쓰면 원리를 더 명확히 볼 수 있습니다. 원소가 둘 다에 속하면 우변의 기여는 1+1−1=1, 한 곳에만 속하면 1, 어느 곳에도 없으면 0입니다. 각 원소에서 성립하는 등식을 합하면 공식이 증명됩니다.
세 집합에서 교대 부호가 생기는 이유
A,B,C를 더하면 두 집합의 교집합들을 빼야 합니다. 그러나 세 집합에 모두 속한 원소의 기여는 3−3=0이 되어 버립니다. 따라서 삼중 교집합을 한 번 더합니다.
r개 집합에 들어 있는 특정 원소의 총 기여는 Σⱼ₌₁ʳ(−1)ʲ⁺¹C(r,j)=1입니다. 이는 (1−1)ʳ=0에서 얻습니다. 이 원소별 논증은 유한 개 집합에 대한 일반 포함배제 원리의 핵심입니다. 화면은 두 집합 모형만 계산하므로 세 집합 공식은 본문에서 별도로 확인합니다.
이항계수와 Pascal 항등식
n개 원소의 크기 k 부분집합을 셉니다. 특정 원소를 하나 고정하면 그 원소를 제외한 집합 C(n−1,k)개와 포함한 집합 C(n−1,k−1)개로 겹침 없이 나뉩니다.
경계에서 C(n,0)=C(n,n)=1이고 k가 범위 밖이면 0으로 셉니다. 이 분류는 Pascal 삼각형을 계산하는 점화식입니다. 계승 공식에 기대지 않고도 항등식을 증명할 수 있다는 점을 확인하세요.
이항정리와 전체 부분집합
(a+b)ⁿ의 n개 인자에서 b를 선택하는 위치 k개를 고르는 수가 C(n,k)입니다. 따라서
a=b=1이면 ΣₖC(n,k)=2ⁿ입니다. n=6의 계수는 1,6,15,20,15,6,1로 합이 64입니다. 크기 3의 부분집합은 20개입니다. 이 수열 자체는 확률분포가 아닙니다. 모든 64개 부분집합이 같은 확률일 때만 64로 나눈 값이 해당 크기의 확률입니다.
비트마스크 실습 읽기
비트 i가 1이면 원소 i가 있습니다. 예를 들어 7=1+2+4는 {0,1,2}, 28=4+8+16은 {2,3,4}입니다. 표에서 각 원소의 A,B,교집합,합집합 지시값을 직접 확인하세요. 두 집합을 같게 만들면 합집합도 그 집합이고, 한쪽을 공집합으로 만들면 다른 집합이 유지됩니다.
그림의 막대는 집합 원소의 위치가 아니라 k별 C(6,k)입니다. 표는 포함배제를, 그림은 크기별 부분집합 분류를 보여 줍니다. 두 시각화가 같은 양을 나타낸다고 읽지 마세요.
AI 데이터에서 필요한 구분
학습·평가 데이터의 중복은 ID 기준 합집합과 텍스트 유사성 기준 중복이 다를 수 있습니다. 동일성 규칙을 먼저 정한 뒤 집합 크기를 계산하세요. 단순 집합 중복률이 데이터 누출의 모든 형태를 탐지하는 것은 아닙니다.
확률 사건에서도 P(A∪B)=P(A)+P(B)−P(A∩B)가 성립합니다. 독립성을 가정하지 않습니다. 교집합을 P(A)P(B)로 대체하려면 독립성이 추가로 필요합니다.
확인 문제와 답
- A=B이고 |A|=3이면 합집합 크기는? 3입니다.
- C(6,2)를 Pascal 분류로 계산하면? C(5,2)+C(5,1)=10+5=15입니다.
- 세 집합에 모두 속한 원소는 포함배제에서 몇 번 남나요? 3−3+1=1번입니다.
- 64개 부분집합을 불균등하게 뽑아도 크기 3의 확률이 20/64일까요? 반드시 그렇지는 않습니다.
추가 읽기: MIT Mathematics for Computer Science. 원소별 계산과 실습은 독립 구성입니다.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.