확률·통계포함배제의 원리#339

포함배제의 원리

Inclusion-Exclusion Principle

포함배제의 원리는 겹치는 유한집합의 원소를 중복 없이 세는 방법이다. 두 집합에서는 교집합을 빼고 세 집합에서는 공통 교집합을 다시 더한다. 원소별 횟수로 이유를 보이고 배수, 정확히 몇 개에 속한 원소, 빈 상자 없는 분배, 상한이 있는 정수해에 적용한다.

읽는 시간
약 9분
선수 개념
집합의 연산

직관 — 명단을 합칠 때 같은 사람을 한 번만 센다

직관

두 활동의 참가 명단을 한데 모으면 두 활동에 모두 참여한 이름은 두 번 나타난다. 참가자 전체를 셀 때는 그 이름 하나를 지워야 한다. 활동이 세 개면 지우는 과정에서 너무 많이 지운 이름도 찾아야 한다.

명단은 유한집합, 이름은 원소다. 아래 활동 자료는 실제 조사 결과가 아닌 가상 명단이다. 집합의 연산에서 배운 합집합과 교집합을 개수로 연결한다. 이 원리는 ‘적어도 하나’, ‘어느 것도 아닌’, ‘빈 상자가 없는’ 같은 조건을 셀 때 쓰인다.

포함배제의 원리는 겹쳐 센 횟수를 바로잡는다

포함배제의 원리는 여러 유한집합의 크기를 더할 때 생기는 중복을 교집합의 크기로 보정하는 원리다. 집합 XX의 원소 수를 n(X)n(X)로 쓰면 두 집합에서는

n(A∪B)=n(A)+n(B)−n(A∩B)(1)n(A\cup B)=n(A)+n(B)-n(A\cap B) \tag{1}

이다. A에만 속하거나 B에만 속하는 원소는 처음부터 한 번 센다. 양쪽에 속한 원소는 두 번 더했으므로 교집합에서 한 번 빼야 정확히 한 번 남는다. 양쪽 밖의 원소는 한 번도 세지 않는다. 이는 원소의 이름이나 실제 개수에 의존하지 않는 일반 이유다.

정의
기호이름원어뜻
UU전체집합universal set문제에서 정한 유한한 전체 범위
A,B,CA,B,C부분집합subsets세 조건을 만족하는 원소들의 집합
n(X)n(X)원소의 개수cardinality유한집합 XX의 원소 수
∪\cup합집합union적어도 한 집합에 속함
∩\cap교집합intersection해당 집합 모두에 속함
AcA^c여집합complementUU 안에서 AA에 속하지 않음

어느 쪽에도 속하지 않는 원소는 두 여집합의 교집합 Ac∩BcA^c\cap B^c다. 이는 합집합의 여집합이므로, 전체에서 식 (1)을 빼면 식 (2)를 얻는다.

n(Ac∩Bc)=n(U)−n(A)−n(B)+n(A∩B)(2)n(A^c\cap B^c)=n(U)-n(A)-n(B)+n(A\cap B) \tag{2}

교과서는 식 (1)과 식 (2)를 함께 두 집합의 포함배제의 원리라고 한다. 가상의 20명 중 A활동 참여자가 11명, B활동 참여자가 8명, 두 활동 참여자가 4명이라면 합집합은 11+8−4=1511+8-4=15명이다. 어느 활동에도 참여하지 않은 사람은 식 (2)로 20−11−8+4=520-11-8+4=5명이다. ‘적어도 하나’는 식 (1), ‘하나도 아님’은 식 (2)로 옮긴다.

포함배제의 원리에서 세 교집합은 왜 다시 더할까?

세 집합 모두에 속한 원소는 처음에 세 번 더하고, 두 집합씩의 교집합에서 세 번 빼면 0번 남는다. 한 번을 되살려야 하므로 공통 교집합을 다시 더한다.

n(A∪B∪C)=n(A)+n(B)+n(C)−n(A∩B)−n(A∩C)−n(B∩C)+n(A∩B∩C).(3)\begin{aligned} n(A\cup B\cup C) ={}&n(A)+n(B)+n(C)\\ &-n(A\cap B)-n(A\cap C)-n(B\cap C)\\ &+n(A\cap B\cap C). \end{aligned} \tag{3}

세 집합 중 정확히 하나, 둘, 셋에 속한 원소가 마지막에 몇 번 남는지 각각 확인하면 다음과 같다.

속한 집합 수처음 더한 횟수둘씩 겹침에서 뺀 횟수셋 겹침에서 더한 횟수최종 횟수
11001
22101
33311

따라서 합집합의 모든 원소는 정확히 한 번, 합집합 밖의 원소는 0번 센다. 이 표는 소속 유형을 모두 나누므로 식 (3)의 일반 증명이다.

점으로 표시한 원소가 A에만(위), A와 B에만(가운데), 세 집합 모두에(아래) 속할 때 식 (3)에서 더하고 빼는 횟수. 세 경우 모두 마지막 횟수가 1이므로 합집합의 원소를 한 번씩 센다.
그림 1 점으로 표시한 원소가 A에만(위), A와 B에만(가운데), 세 집합 모두에(아래) 속할 때 식 (3)에서 더하고 빼는 횟수. 세 경우 모두 마지막 횟수가 1이므로 합집합의 원소를 한 번씩 센다. figures/membership_counts.py

그림 1의 가운데 점은 n(A)n(A)와 n(B)n(B)에서 두 번 더해지고 n(A∩B)n(A\cap B)에서 한 번 빠진다. 아래 점은 세 교집합 A∩BA\cap B, A∩CA\cap C, B∩CB\cap C에 모두 들어 있어서 세 번 빠진다.

교과서는 u=n(U)u=n(U)로 두고, 세 집합의 크기의 합을 u1u_1, 두 집합씩의 교집합의 크기의 합을 u2u_2, 세 집합의 교집합의 크기를 u3u_3으로 줄여 쓴다. 그러면 식 (3)은 n(A∪B∪C)=u1−u2+u3n(A\cup B\cup C)=u_1-u_2+u_3이고, 어느 집합에도 속하지 않는 원소의 수는 다음과 같다.

n(Ac∩Bc∩Cc)=u−u1+u2−u3(4)n(A^c\cap B^c\cap C^c)=u-u_1+u_2-u_3 \tag{4}

교과서는 이 두 식을 세 집합의 포함배제의 원리라고 한다.

두 집합의 원리를 두 번 써서 식 (3) 얻기

A∪B∪CA\cup B\cup C를 AA와 B∪CB\cup C의 합집합으로 보고 식 (1)을 쓰면 n(A)+n(B∪C)−n(A∩(B∪C))n(A)+n(B\cup C)-n(A\cap(B\cup C))다.

n(B∪C)n(B\cup C)에 식 (1)을 다시 쓰면 n(B)+n(C)−n(B∩C)n(B)+n(C)-n(B\cap C)다.

분배법칙으로 A∩(B∪C)=(A∩B)∪(A∩C)A\cap(B\cup C)=(A\cap B)\cup(A\cap C)이고, 이 두 집합의 교집합은 A∩B∩CA\cap B\cap C다. 식 (1)을 세 번째로 쓰면 n(A∩B)+n(A∩C)−n(A∩B∩C)n(A\cap B)+n(A\cap C)-n(A\cap B\cap C)다.

세 결과를 모으면 식 (3)이 된다. 마지막 단계에서 빼는 식 안의 −n(A∩B∩C)-n(A\cap B\cap C)가 바깥 빼기와 만나 더하기로 바뀐다.

포함배제의 원리로 세 종류 배수를 센다

1부터 30까지의 자연수 중 2, 3, 5의 배수인 집합을 각각 A, B, C로 정하자. 합집합은 적어도 이 셋 중 하나로 나누어떨어지는 수들의 집합이다. 각 개수는 15,10,615,10,6이다. 두 조건을 동시에 만족하려면 각각 6, 10, 15의 배수여야 하므로 교집합의 개수는 5,3,25,3,2다. 세 조건은 30의 배수 하나가 만족한다.

n(A∪B∪C)=15+10+6−5−3−2+1=22.(5)n(A\cup B\cup C) =15+10+6-5-3-2+1=22. \tag{5}
1부터 30까지를 2, 3, 5의 배수 소속에 따라 나눈 일곱 영역의 개수와 셋 모두 밖의 개수. 각 숫자는 그 영역에만 속한 개수이며 전체 합은 30이다.
그림 2 1부터 30까지를 2, 3, 5의 배수 소속에 따라 나눈 일곱 영역의 개수와 셋 모두 밖의 개수. 각 숫자는 그 영역에만 속한 개수이며 전체 합은 30이다. figures/three_set_regions.py

그림 2의 두 집합만 겹친 영역과 두 집합의 교집합 전체를 혼동하지 말자. 예를 들어 n(A∩B)=5n(A\cap B)=5에는 세 집합 모두에 속한 30도 들어간다. A와 B에만 속한 개수는 5−1=45-1=4다.

어느 조건도 만족하지 않는 개수는 식 (4)에 u1=31u_1=31, u2=10u_2=10, u3=1u_3=1을 넣어 30−31+10−1=830-31+10-1=8이다. 이 8개 1, 7, 11, 13, 17, 19, 23, 29는 2, 3, 5 어느 것으로도 나누어떨어지지 않으므로 30과 서로소인 수다.

포함배제의 원리로 정확히 두 집합이나 한 집합에 속한 원소를 센다

정확히 kk개의 집합에 속한 원소의 수를 NkN_k라 하면, 세 집합에서는 N2N_2와 N1N_1도 u1,u2,u3u_1,u_2,u_3만으로 구한다. 배수 예에서는 정확히 두 조건만 만족하는 수가 7개, 한 조건만 만족하는 수가 14개다.

N2=u2−3u3=10−3×1=7(6)N_2=u_2-3u_3=10-3\times1=7 \tag{6} N1=u1−2u2+3u3=31−2×10+3×1=14(7)N_1=u_1-2u_2+3u_3=31-2\times10+3\times1=14 \tag{7}

세 집합 모두에 속한 원소는 두 집합씩의 교집합 세 개에 다 들어 있어 u2u_2에서 세 번 세어진다. 그래서 식 (6)은 u3u_3을 세 번 뺀다. 식 (7)에서 정확히 두 집합에 속한 원소는 2−2×1=02-2\times1=0번, 세 집합 모두에 속한 원소는 3−2×3+3×1=03-2\times3+3\times1=0번 남는다. 정확히 한 집합에 속한 원소만 한 번씩 남는다.

그림 2에서 확인하면 둘만 겹친 영역은 4+2+1=74+2+1=7, 한 원에만 있는 영역은 8+4+2=148+4+2=14다. 세 집합 모두의 1을 더한 14+7+1=2214+7+1=22가 식 (5)의 합집합이다.

포함배제의 원리는 금지 조건이 있는 배열에도 적용된다

서로 다른 세 카드 1, 2, 3을 세 번호 자리에 놓되 같은 번호 자리에는 놓지 않는다고 하자. 전체는 순열 3!=63!=6가지다. A는 1번 카드가 제자리, B는 2번 카드가 제자리, C는 3번 카드가 제자리인 배열의 집합으로 정한다. 각 집합은 남은 두 카드를 바꾸는 2!=22!=2가지다.

두 카드가 제자리면 세 번째 카드도 제자리다. 따라서 두 집합의 교집합은 각각 1가지이고 세 집합 교집합도 1가지다. 적어도 하나가 제자리인 배열은 식 (3)에 따라 2+2+2−1−1−1+1=42+2+2-1-1-1+1=4가지다. 원하는 배열은 6−4=26-4=2가지이며 231, 312다. 조건을 집합으로 먼저 정하면 ‘적어도’와 ‘모두 아님’의 혼동을 줄일 수 있다.

빈 상자가 없게 나누는 경우는 포함배제의 원리로 어떻게 세나?

빈 상자가 하나라도 생기는 경우를 집합으로 정해 전체에서 뺀다. 서로 다른 공 5개를 서로 다른 상자 3개에 빈 상자 없이 넣는 방법은 150가지다.

공마다 상자를 하나씩 고르므로 전체는 중복순열 35=2433^5=243가지다. ii번 상자가 비는 경우의 집합을 EiE_i라 하자. EiE_i에서는 각 공이 ii번이 아닌 두 상자 중 하나를 고르므로 n(Ei)=25=32n(E_i)=2^5=32이다. 두 상자 ii, jj가 함께 비면 다섯 공이 나머지 한 상자에 들어가므로 n(Ei∩Ej)=1n(E_i\cap E_j)=1이다. 세 상자가 모두 빌 수는 없다.

35−3×25+3×15−0=243−96+3=150(8)3^5-3\times2^5+3\times1^5-0=243-96+3=150 \tag{8}
서로 다른 공 5개를 서로 다른 상자 3개에 넣는 243가지를 i번 상자가 비는 집합 E_i의 영역으로 나눈 개수. 한 상자만 비는 경우가 30가지씩, 두 상자가 비는 경우가 1가지씩이고, 세 원 밖의 150가지가 빈 상자가 없는 경우다.
그림 3 서로 다른 공 5개를 서로 다른 상자 3개에 넣는 243가지를 ii번 상자가 비는 집합 EiE_i의 영역으로 나눈 개수. 한 상자만 비는 경우가 30가지씩, 두 상자가 비는 경우가 1가지씩이고, 세 원 밖의 150가지가 빈 상자가 없는 경우다. figures/empty_box_venn.py

그림 3에서 E1E_1의 32가지는 1번 상자만 비는 30가지와 2번 또는 3번 상자도 함께 비는 1가지씩으로 나뉜다. 두 원이 겹친 이 1가지씩은 3×253\times2^5에서 두 번 빠졌으므로 3×153\times1^5로 한 번씩 되돌린다.

교과서는 같은 문제를 치역이 공역 전체인 함수의 개수로 묻는다. 공을 정의역의 원소, 상자를 공역의 원소로 보면 빈 상자가 없다는 것은 모든 상자가 치역에 들어간다는 뜻이다. 집합의 분할의 수 S(5,3)=25S(5,3)=25에 상자 이름을 붙이는 3!3!을 곱해도 150이다.

포함배제의 원리로 상한이 있는 방정식의 정수해를 센다

x+y+z=10x+y+z=10을 만족하는 0 이상의 정수 중 x,y,zx,y,z가 모두 4 이하인 해는 6개다. 상한을 어긴 해를 집합으로 정하고, 중복조합으로 센 전체에서 뺀다.

전체 해는 3H10=12C10=66{}_3H_{10}={}_{12}C_{10}=66개다. x≥5x\ge5인 해의 집합을 XX라 하면, x=5+x′x=5+x'로 바꾼 x′+y+z=5x'+y+z=5의 해 3H5=7C5=21{}_3H_5={}_7C_5=21개다. y≥5y\ge5, z≥5z\ge5인 집합도 21개씩이다. x≥5x\ge5이고 y≥5y\ge5이면 합이 10이므로 (5,5,0)(5,5,0) 하나뿐이고, 세 변수가 모두 5 이상일 수는 없다.

66−3×21+3×1−0=6(9)66-3\times21+3\times1-0=6 \tag{9}
x+y+z=10을 만족하는 0 이상의 정수해 66개를 삼각형 모양으로 놓았다. 왼쪽 아래·오른쪽 아래·위 꼭짓점 쪽으로 갈수록 각각 x, y, z가 크다. 각 점선은 그 변수가 4 이하인 해와 5 이상인 해를 가르며, 꼭짓점 쪽 점선 바깥의 21개가 그 변수가 5 이상인 해다. 주황 점 3개는 두 점선 바깥에 함께 놓여 두 조건을 어긴 해이고, 가운데 파란 점 6개가 모두 4 이하인 해다.
그림 4 x+y+z=10x+y+z=10을 만족하는 0 이상의 정수해 66개를 삼각형 모양으로 놓았다. 왼쪽 아래·오른쪽 아래·위 꼭짓점 쪽으로 갈수록 각각 xx, yy, zz가 크다. 각 점선은 그 변수가 4 이하인 해와 5 이상인 해를 가르며, 꼭짓점 쪽 점선 바깥의 21개가 그 변수가 5 이상인 해다. 주황 점 3개는 두 점선 바깥에 함께 놓여 두 조건을 어긴 해이고, 가운데 파란 점 6개가 모두 4 이하인 해다. figures/bounded_solutions_lattice.py

그림 4의 주황 점은 3×213\times21을 뺄 때 두 번 빠졌으므로 한 번씩 되돌린다. 남은 6개는 (4,4,2)(4,4,2)와 (4,3,3)(4,3,3)의 자리를 바꾼 해다.

포함배제의 원리는 네 집합 이상에서도 더하고 빼기를 번갈아 한다

집합이 네 개 이상이어도 한 개씩의 크기는 더하고, 두 개씩의 교집합은 빼고, 세 개씩은 더하고, 네 개씩은 빼는 식으로 번갈아 계산한다. 정확히 kk개의 집합에 속한 원소가 이 계산에서 kC1−kC2+kC3−⋯{}_kC_1-{}_kC_2+{}_kC_3-\cdots번 세어지고, 그 값이 1이기 때문이다.

네 집합 모두에 속한 원소라면 4−6+4−1=14-6+4-1=1이다. 일반적인 kk에서 1이 되는 이유는 이항정리를 배웠다면 (1−1)k=0(1-1)^k=0을 전개해 확인할 수 있다. 카드 제자리 문제처럼 대상 수만큼 조건이 늘어나는 문제에서 이 확장을 쓴다.

핵심

포함배제의 원리는 각 원소가 한 번씩 남도록 중복을 보정해 합집합을 센다. 세 집합에서는 크기의 합에서 쌍별 교집합을 빼고 삼중 교집합을 더한다.

포함배제의 원리에서 두 집합이 겹치지 않으면 어떻게 되나요?

교집합이 공집합이면 원소 수가 0이므로 두 집합의 크기를 그대로 더한다. 이는 합의 법칙의 서로 겹치지 않는 경우와 같다. 예를 들어 4개와 7개가 겹치지 않으면 합집합은 11개다.

포함배제의 원리에서 두 집합의 교집합은 세 집합 공통 부분을 빼고 세나요?

아니다. 두 집합의 교집합에는 세 집합 모두에 속한 원소도 포함한다. 배수 예에서 30은 A와 B의 교집합에 들어가므로 그 개수는 5이며, A와 B에만 속한 개수 4와 다르다.

포함배제의 원리는 집합의 크기만 알면 계산할 수 있나요?

일반적으로는 겹치는 개수도 알아야 한다. 크기가 각각 2인 두 집합은 서로소이면 합집합이 4개지만, 두 집합이 같으면 2개다. 같은 집합 크기만으로 합집합 크기가 정해지지 않는다.

포함배제의 원리의 흔한 오해

  • 세 집합 모두 겹친 부분은 이미 많이 셌으니 마지막에도 빼야 한다 — 처음 3번 더하고 쌍별로 3번 뺀 뒤 다시 빼면 −1번이 된다. 정확히 한 번 남기려면 3−3+1=13-3+1=1이어야 한다.
  • 어떤 크기와 교집합 수를 넣어도 가능한 자료다 — A가 3개인데 A와 B의 교집합이 5개일 수는 없다. 교집합은 A의 부분집합이며 영역별 원소 수가 음수가 아닌지도 확인해야 한다.
  • 4의 배수와 6의 배수의 교집합은 24의 배수다 — 두 조건을 함께 만족하는 수는 최소공배수 12의 배수다. 1부터 50까지에서 12의 배수는 4개인데 24의 배수 2개로 세면 12와 36을 빠뜨려, 4 또는 6의 배수를 16개가 아니라 18개로 잘못 센다.

직접 해보기

다음 활동 명단은 가상 자료다. 각 문제의 전체집합과 조건의 집합을 말로 먼저 정해 보자.

  1. 1부터 100까지의 자연수 중 2, 3, 7 어느 것의 배수도 아닌 수는 몇 개인가?
  2. 전체 30명 중 A, B, C 활동의 인원은 14, 13, 12이고 두 활동씩 함께 하는 인원은 AB 6, AC 5, BC 4다. 세 활동을 모두 하는 사람은 2명이다. 어느 활동도 하지 않는 사람, 정확히 두 활동만 하는 사람, 정확히 한 활동만 하는 사람은 각각 몇 명인가?
  3. 서로 다른 공 4개를 서로 다른 상자 3개에 빈 상자가 없도록 넣는 방법은 몇 가지인가?
  4. 1부터 6까지의 숫자를 한 번씩 써서 일렬로 나열할 때, 12, 34, 56 중 어느 것도 이 순서로 붙어 나오지 않는 경우는 몇 가지인가?
  5. 서로 다른 카드 네 장을 번호가 붙은 네 자리에 놓을 때 어느 카드도 제 번호 자리에 놓이지 않는 경우는 몇 가지인가?
답과 풀이
  1. 2, 3, 7의 배수는 50, 33, 14개이고, 6, 14, 21의 배수는 16, 7, 4개이며, 42의 배수는 2개다. 식 (4)로 100−97+27−2=28100-97+27-2=28개다.
  2. 식 (4)로 30−39+15−2=430-39+15-2=4명이 어느 활동도 하지 않는다. 식 (6)으로 정확히 두 활동은 15−3×2=915-3\times2=9명, 식 (7)로 정확히 한 활동은 39−2×15+3×2=1539-2\times15+3\times2=15명이다. 합집합 26명이 15+9+215+9+2와 같다.
  3. 전체 34=813^4=81가지에서 한 상자가 비는 24=162^4=16가지씩을 세 번 빼고, 두 상자가 비는 1가지씩을 세 번 더한다. 81−48+3=3681-48+3=36가지다.
  4. 12가 붙어 나오는 순열은 12를 한 글자로 보아 5!=1205!=120가지다. 두 묶음이 함께 나오면 4!=244!=24가지, 세 묶음이면 3!=63!=6가지다. 720−3×120+3×24−6=426720-3\times120+3\times24-6=426가지다.
  5. ii번 카드가 제자리인 배열의 집합 네 개를 정한다. 정한 jj장이 제자리인 교집합은 남은 카드의 배열 (4−j)!(4-j)!가지이고, 그런 교집합이 4Cj{}_4C_j개다. 24−4×6+6×2−4×1+1=924-4\times6+6\times2-4\times1+1=9가지다.

더 읽기

영상 노트

영상 노트
  • 00:00 두 활동 명단을 합치고 중복 이름을 지워 식 (1)과 식 (2)를 만든다.
  • 00:50 그림 1의 점 위치별 횟수로 식 (3)의 마지막 덧셈을 설명한다.
  • 01:40 교과서 기호 u1,u2,u3u_1,u_2,u_3로 식 (4)를 적는다.
  • 02:20 배수의 교집합을 구해 식 (5)를 계산하고 그림 2를 읽는다.
  • 03:10 그림 2의 영역으로 식 (6)과 식 (7)의 정확히 둘·하나를 확인한다.
  • 04:00 카드 제자리 조건을 집합으로 옮겨 센다.
  • 04:40 그림 3의 빈 상자 집합으로 식 (8)을 계산한다.
  • 05:30 그림 4의 삼각형 격자로 식 (9)의 상한 조건을 센다.
  • 06:20 네 집합 이상의 부호 규칙과 연습 문제의 범위를 확인한다.

지도에서의 위치

부분집합기초수학집합의 연산기초수학포함배제의 원리지금 이 페이지
선수 개념
이 페이지
완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-16 · 에이전트 초안
  2. 2026-11-17 · 전수 검수 반영 — 교과서의 여집합 꼴과 u₁·u₂·u₃ 표기 연결, 두 집합 원리를 두 번 쓰는 유도, 정확히 하나·둘에 속한 원소의 식, 빈 상자 없는 분배(치역이 공역 전체인 함수)·상한이 있는 정수해·네 집합 이상의 부호 규칙 추가, 원소 위치를 보이는 횟수 그림으로 교체, 최소공배수 오해 추가, 연습을 새 유형 5문항으로 교체, 상한 정수해 그림의 경계 점선을 4와 5 사이로 옮겨 21개씩을 바로 읽게 함 (에이전트 수정, 그림 2→4)
  3. 2026-11-17 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림