방송대 방통대 이산수학 12강 - 조합이론과 이산확률 - 요약 노트 시험족보 예상문제 - 올에이클래스

이산수학 12강 - 조합이론과 이산확률

조합이론은 가능한 경우를 체계적으로 세는 방법을 다루며 확률, 알고리즘, 자료구조 분석의 기초가 된다. 이 글에서는 곱셈·덧셈 법칙부터 순열과 조합, 이산확률, 점화식, 비둘기집 원리까지 12강의 핵심 내용을 예제와 함께 정리한다.

1. 조합이론의 학습 흐름

경우의 수를 구할 때 가장 먼저 판단할 것은 여러 선택 단계를 모두 거쳐야 하는지, 여러 대안 가운데 하나를 택하는지이다. 모든 단계를 연속해서 수행하면 곱의 법칙을, 서로 겹치지 않는 대안 중 하나를 선택하면 합의 법칙을 사용한다. 사건들이 겹치면 포함배제 원리를 적용하여 중복 계산을 제거한다.

선택하는 원소의 순서가 중요하면 순열, 순서가 중요하지 않으면 조합을 사용한다. 중복 허용 여부와 원형 배치 여부에 따라 공식이 달라진다. 조합은 이항정리의 계수로도 나타나며, 표본공간과 사건의 크기를 세면 이산확률을 계산할 수 있다. 이어 수열을 이전 항으로 표현하는 점화식과, 많은 물체를 적은 상자에 넣을 때 반드시 생기는 중복을 설명하는 비둘기집 원리를 학습한다.

학습 목표

• 곱의 법칙, 합의 법칙, 포함배제 원리로 경우의 수를 계산한다.
• 순열·중복순열·중복 원소가 있는 순열·원순열을 구분한다.
• 조합을 계산하고 이항정리의 특정 항의 계수를 구한다.
• 유한 표본공간에서 확률과 조건부확률을 계산한다.
• 점화식에서 일반항을 구하고 비둘기집 원리를 응용한다.

2. 기본 계수 법칙

2.1 곱의 법칙

사건 A가 일어나는 방법이 m가지이고, 각 방법에 이어 사건 B가 일어나는 방법이 n가지라면 A와 B를 모두 수행하는 방법은 m × n가지이다. 기호로 N(A × B) = N(A) × N(B) = mn으로 나타낸다. 세 단계 이상이라면 각 단계의 경우의 수를 모두 곱한다.

판별 표현: “A를 하고 B도 한다”, “각 자리마다 선택한다”, “단계를 차례로 거친다”와 같은 상황에서는 곱의 법칙을 먼저 생각한다.

중첩 반복문에서 바깥 반복이 0부터 5까지 6회, 안쪽 반복이 0부터 3까지 4회 실행되면 안쪽 출력은 6 × 4 = 24회 실행된다. 8비트 이진수는 각 비트마다 0과 1 중 하나를 독립적으로 선택하므로 2⁸ = 256개이다.

2.2 합의 법칙

사건 A가 일어나는 방법이 m가지, 사건 B가 일어나는 방법이 n가지이고 두 사건이 서로 겹치지 않으면 A 또는 B가 일어나는 방법은 m + n가지이다. 즉 A ∩ B = ∅일 때 N(A ∪ B) = N(A) + N(B)이다.

사용 가능한 숫자가 1부터 8까지이고 길이가 4자리, 5자리 또는 6자리인 비밀번호를 만든다면 각 길이의 경우는 서로 겹치지 않는다. 따라서 8⁴ + 8⁵ + 8⁶ = 4,096 + 32,768 + 262,144 = 299,008개이다.

계수 법칙	사용 상황	계산
곱의 법칙	여러 단계를 모두 수행	각 단계의 경우의 수를 곱한다.
합의 법칙	서로 겹치지 않는 대안 중 하나를 선택	각 대안의 경우의 수를 더한다.
포함배제 원리	대안들이 서로 겹침	더한 뒤 중복 계산된 교집합을 뺀다.

2.3 합집합의 크기와 포함배제 원리

두 유한집합 A와 B가 겹치면 단순히 |A| + |B|를 계산할 경우 교집합의 원소를 두 번 센다. 따라서 한 번을 빼서 |A ∪ B| = |A| + |B| − |A ∩ B|로 계산한다. 세 집합에서는 각 집합의 크기를 더하고 두 집합씩의 교집합을 뺀 뒤, 세 집합의 교집합을 다시 더한다.

|A ∪ B| = |A| + |B| − |A ∩ B|

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

8비트 이진수 가운데 ‘100’으로 시작하는 것은 나머지 5비트를 자유롭게 정하므로 2⁵ = 32개이고, ‘100’으로 끝나는 것도 32개이다. 두 조건을 모두 만족하면 가운데 2비트만 자유로워 2² = 4개이다. 따라서 적어도 한 조건을 만족하는 이진수는 32 + 32 − 4 = 60개이다.

3. 순열과 여러 배열 방법

3.1 순열

n개의 서로 다른 원소에서 순서를 고려하여 r개를 뽑는 경우의 수를 순열이라고 한다. 첫 번째 자리에 n개, 두 번째 자리에 n − 1개를 선택할 수 있으므로 곱의 법칙에 따라 다음 공식을 얻는다.

P(n, r) = n(n − 1)···(n − r + 1) = n!/(n − r)!

1부터 5까지의 숫자를 한 번씩만 사용해 3자리 수를 만들면 P(5, 3) = 5 × 4 × 3 = 60가지이다. 같은 세 숫자라도 나열 순서가 달라지면 다른 수이므로 순열을 사용한다.

3.2 중복된 원소가 있는 집합의 순열

전체 n개 원소 중 서로 같은 원소가 각각 p개, q개, …, r개 있고 n개 모두를 일렬로 배열하면, 같은 원소끼리 바꾼 배열은 구별되지 않는다. 따라서 전체 n!에서 중복되는 p!, q!, …, r!만큼을 나눈다.

중복 원소가 있는 n개 전체의 배열 수 = n!/(p!q!···r!)

격자에서 오른쪽 이동 6회와 위쪽 이동 4회로 A에서 B까지 가는 최단경로는 총 10회의 이동 순서로 결정된다. 같은 오른쪽 이동 6개와 위쪽 이동 4개를 배열하므로 10!/(6!4!) = 210가지이다.

3.3 중복순열

n개의 원소 중에서 중복을 허용하고 순서를 고려하여 r개를 뽑으면 각 자리마다 n가지 선택이 가능하므로 경우의 수는 n^r이다. 예를 들어 S, M, A, R, T의 다섯 문자로 중복을 허용해 길이 3의 문자열을 만들면 5³ = 125가지이다. 중복을 허용하지 않으면 P(5, 3) = 60가지이므로 두 상황을 구별해야 한다.

3.4 원순열

n개의 서로 다른 원소를 원형으로 나열할 때에는 전체를 같은 만큼 회전한 배치를 같은 것으로 본다. 각 원형 배치가 일렬 배열에서 n번씩 중복되므로 n!/n = (n − 1)!가지이다.

철수를 포함한 6명이 원탁에 앉고 철수와 영희가 마주 보아야 한다고 하자. 철수의 자리를 기준으로 고정하면 영희의 자리는 자동으로 정해진다. 나머지 네 사람을 배치하는 것과 같아 4! = 24가지이다.

유형	중복 허용	순서 고려	공식
순열	아니요	예	P(n, r) = n!/(n − r)!
중복순열	예	예	nr
중복 원소의 전체 배열	원소 자체가 중복	예	n!/(p!q!···r!)
원순열	아니요	회전은 같은 배치	(n − 1)!

4. 조합과 이항정리

4.1 조합

n개의 서로 다른 원소에서 순서를 고려하지 않고 r개를 뽑는 경우의 수를 조합이라고 한다. r개를 뽑은 뒤 그 r개를 배열하는 r!가지가 하나의 조합으로 합쳐지므로 P(n, r)을 r!로 나눈다.

C(n, r) = P(n, r)/r! = n!/[r!(n − r)!]

8개의 버튼 중 4개를 순서 없이 선택하는 자물쇠는 C(8, 4) = 70가지이다. 12명의 타자 중 9명을 선발하는 방법은 제외할 3명을 고르는 방법과 같으므로 C(12, 9) = C(12, 3) = 220가지이다. 일반적으로 C(n, r) = C(n, n − r)가 성립한다.

순열과 조합의 구분: 뽑힌 원소가 같아도 배치 순서가 다르면 다른 결과로 세는 경우에는 순열을, 뽑힌 집합만 중요하면 조합을 사용한다.

4.2 이항정리

임의의 실수 x, y와 음이 아닌 정수 n에 대해 (x + y)ⁿ을 전개할 때 각 항의 계수는 조합으로 나타난다.

(x + y)ⁿ = Σ_k=0ⁿ C(n, k)x^n−ky^k

x의 지수와 y의 지수의 합은 항상 n이고, y의 지수가 k인 항의 계수는 C(n, k)이다. 예를 들어 (x + y)¹²에서 x⁴y⁸의 계수는 C(12, 8) = C(12, 4) = 495이다.

5. 이산확률과 조건부확률

5.1 표본공간과 사건

어떤 실험에서 가능한 모든 결과 가운데 하나가 나타날 때, 모든 가능한 결과의 집합을 표본공간(sample space) S라고 한다. 표본공간의 부분집합 E를 사건(event)이라고 한다. 주사위를 두 번 던지면 순서쌍 (첫 번째 눈, 두 번째 눈) 36개가 표본공간을 이룬다.

5.2 수학적 확률

유한 표본공간의 모든 기본 결과가 같은 가능성으로 발생한다면 사건 E의 확률은 사건에 유리한 결과 수를 전체 결과 수로 나눈 값이다.

P(E) = |E|/|S|, 0 ≤ P(E) ≤ 1, P(∅) = 0, P(S) = 1

주사위를 두 번 던져 눈의 합이 3이 되는 사건은 (1, 2), (2, 1)의 두 결과이다. 따라서 확률은 2/36 = 1/18이다. 서로소 사건 A와 B에 대해서는 P(A ∪ B) = P(A) + P(B)이고, 일반적으로는 교집합을 한 번 빼서 P(A ∪ B) = P(A) + P(B) − P(A ∩ B)이다.

5.3 조건부확률

사건 B가 이미 발생했다고 가정할 때 사건 A가 발생할 확률을 조건부확률 P(A|B)라고 한다. B가 새로운 표본공간의 역할을 하므로 A와 B가 동시에 발생하는 부분의 확률을 B의 확률로 나눈다.

P(A|B) = P(A ∩ B)/P(B) (단, P(B) > 0)

전체 중고차의 70%가 내비게이션을, 40%가 블랙박스를 가지고 있고 90%가 둘 중 하나 이상을 가진다고 하자. 내비게이션이 없을 확률은 0.3, 둘 다 없을 확률은 0.1이다. 따라서 내비게이션이 없는 차 중 블랙박스도 없을 조건부확률은 0.1/0.3 = 1/3, 즉 약 33.3%이다.

6. 점화식과 일반항

6.1 점화식의 뜻

점화식(recurrence relation)은 수열의 항 사이에 성립하는 관계식이다. 현재 항 a_n을 이전 항 a₁, a₂, …, a_n−1의 함수로 나타낸다. 점화식만으로 수열을 하나로 결정하려면 시작항과 같은 초기조건이 필요하다.

“점화식을 푼다”는 것은 이전 항을 참조하는 표현을 반복 대입하여 제거하고, 일반항 a_n을 n만의 식으로 나타내는 것이다.

6.2 등차형 점화식

수열 1, 4, 7, 10, 13, …을 a₀부터 시작한다고 하면 a₀ = 1이고 a_n = a_n−1 + 3이다. 이전 항을 반복해서 대입하면 a_n = a₀ + 3n = 1 + 3n을 얻는다.

6.3 반복 대입과 등비급수

c_n = 2c_n−1 + 1, c₁ = 1을 풀어 보자. 반복 대입하면 2의 거듭제곱과 상수항의 합이 나타난다.

c_n = 2ⁿ⁻¹c₁ + 2ⁿ⁻² + ··· + 2 + 1 = 2ⁿ⁻¹ + (2ⁿ⁻¹ − 1) = 2ⁿ − 1이다.

검산 방법: 구한 일반항이 초기조건을 만족하는지 확인하고, 일반항을 원래 점화식의 양변에 대입하여 등식이 성립하는지 확인한다.

7. 비둘기집 원리

7.1 일반화된 비둘기집 원리

k개의 상자에 N개의 물체를 넣으면 적어도 하나의 상자에는 ⌈N/k⌉개 이상의 물체가 들어간다. 모든 상자에 ⌈N/k⌉개보다 적게 넣을 수 있다고 가정하면 전체 N개를 수용할 수 없다는 모순이 생긴다.

k개의 비둘기집에 N개의 비둘기를 넣으면 적어도 한 집에는 ⌈N/k⌉마리 이상이 들어간다.

7.2 정사각형 안의 점에 적용

한 변의 길이가 2cm인 정사각형에 점 5개를 찍는다. 큰 정사각형을 한 변이 1cm인 작은 정사각형 4개로 나누면, 5개의 점을 4개의 영역에 배치하는 것이므로 적어도 한 영역에는 점이 2개 이상 들어간다.

한 변이 1cm인 작은 정사각형 안에서 두 점 사이의 최대 거리는 대각선 길이 √2이다. 두 점이 서로 다른 위치라면 거리는 √2 이하이며, 강의의 결론처럼 두 점 사이의 거리가 √2보다 작은 두 점이 반드시 존재하는 상황을 비둘기집 원리로 설명할 수 있다.

응용 절차: 물체와 상자를 무엇으로 볼지 정하고, 물체 수 N과 상자 수 k를 센 뒤, 한 상자에 함께 들어간 물체들이 만족하는 성질을 해석한다.

8. 핵심 개념 정리

• 연속된 선택 단계는 곱하고, 서로소인 대안은 더한다. 겹치는 대안은 포함배제 원리로 중복을 뺀다.
• 순열 P(n, r)은 순서를 고려하고, 조합 C(n, r)은 순서를 고려하지 않는다.
• 중복순열은 각 자리에 n가지 선택이 가능하므로 n^r이고, 원순열은 (n − 1)!이다.
• C(n, r) = n!/[r!(n − r)!]이며 C(n, r) = C(n, n − r)이다.
• 이항정리에서 x^n−ky^k의 계수는 C(n, k)이다.
• 동일 가능성을 가진 유한 표본공간에서 P(E) = |E|/|S|이다.
• 조건부확률은 P(A|B) = P(A ∩ B)/P(B)이다.
• 점화식의 해는 이전 항이 없는 n에 관한 일반항이며 초기조건이 함께 필요하다.
• k개 상자에 N개 물체를 넣으면 어떤 상자에는 적어도 ⌈N/k⌉개가 들어간다.

시험 직전 최종 점검

문제에서 “동시에·차례로”는 곱, “또는”은 합을 떠올리되 사건이 겹치는지 반드시 확인한다. 순열과 조합은 순서의 중요성, 중복 가능성, 원형 배치 여부를 먼저 표시한 뒤 공식을 선택한다. 확률은 표본공간의 동일 가능성을 확인하고, 조건부확률은 조건 사건을 새로운 기준으로 삼는다.

9. 예상문제 20선

1. 바깥 반복문이 5회, 안쪽 반복문이 매번 3회 실행될 때 안쪽 명령의 총 실행 횟수는?

① 3회 ② 5회 ③ 8회 ④ 15회

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
바깥 반복의 각 경우마다 안쪽 반복을 모두 실행하므로 곱의 법칙에 따라 5 × 3 = 15회이다.

2. 서로소인 두 사건 A, B의 경우의 수가 각각 7과 5일 때 A 또는 B가 일어나는 경우의 수는?

① 2 ② 12 ③ 35 ④ 7

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
두 사건이 서로소이므로 합의 법칙을 그대로 적용해 7 + 5 = 12를 얻는다.

3. |A| = 20, |B| = 15, |A ∩ B| = 6일 때 |A ∪ B|는?

① 29 ② 35 ③ 41 ④ 9

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
교집합은 두 번 더해졌으므로 한 번 뺀다. 20 + 15 − 6 = 29이다.

4. 6개의 서로 다른 원소 중 순서를 고려하여 2개를 뽑는 경우의 수는?

① 12 ② 15 ③ 30 ④ 36

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
순서를 고려하므로 P(6, 2) = 6 × 5 = 30이다.

5. 문자 A, A, B, B를 모두 일렬로 배열하는 서로 다른 방법의 수는?

① 4 ② 6 ③ 12 ④ 24

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
전체 4!에서 같은 A의 2!과 같은 B의 2!만큼 중복되므로 4!/(2!2!) = 6이다.

6. 4개의 문자를 사용하여 중복을 허용한 길이 3의 문자열을 만드는 방법의 수는?

① 12 ② 24 ③ 81 ④ 64

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
세 자리마다 네 문자 중 하나를 선택할 수 있으므로 중복순열의 수는 4³ = 64이다.

7. 서로 다른 7명을 원탁에 앉히는 원순열의 수는?

① 6! ② 7! ③ 7² ④ 5!

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
회전하여 같은 배치는 하나로 보므로 n명의 원순열은 (n − 1)!이다. n = 7이면 6!이다.

8. 10명 중 순서 없이 3명을 대표로 뽑는 경우의 수는?

① 30 ② 720 ③ 120 ④ 1,000

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
대표 세 명의 나열 순서는 중요하지 않으므로 C(10, 3) = 10×9×8/(3×2×1) = 120이다.

9. C(12, 9)와 같은 값은?

① C(12, 3) ② P(12, 3) ③ C(9, 3) ④ 12³

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
r개를 선택하는 것은 선택하지 않을 n − r개를 정하는 것과 같으므로 C(n, r) = C(n, n − r)이다.

10. (x + y)⁸에서 x³y⁵의 계수는?

① 8 ② 40 ③ 64 ④ 56

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
y의 지수가 5인 항의 계수는 C(8, 5) = C(8, 3) = 56이다.

11. 이산확률에서 표본공간에 대한 설명으로 옳은 것은?

① 반드시 발생하지 않는 결과의 집합이다. ② 하나의 사건에 포함된 결과만의 집합이다. ③ 실험에서 가능한 모든 결과의 집합이다. ④ 확률이 0인 결과만의 집합이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
표본공간은 실험에서 나타날 수 있는 모든 결과를 모은 집합이며, 사건은 그 표본공간의 부분집합이다.

12. 공정한 주사위를 두 번 던질 때 눈의 합이 3일 확률은?

① 1/6 ② 1/18 ③ 1/12 ④ 1/36

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
전체 순서쌍은 36개이고 합이 3인 것은 (1, 2), (2, 1) 두 개이므로 2/36 = 1/18이다.

13. 일반적인 두 사건 A, B에 대한 확률의 합집합 공식은?

① P(A ∪ B) = P(A)P(B) ② P(A ∪ B) = P(A) − P(B) ③ P(A ∪ B) = P(A) + P(B) + P(A ∩ B) ④ P(A ∪ B) = P(A) + P(B) − P(A ∩ B)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
A와 B의 교집합은 P(A)와 P(B)에 각각 포함되어 두 번 더해지므로 한 번 빼야 한다.

14. P(B) > 0일 때 조건부확률 P(A|B)는?

① P(A ∩ B)/P(B) ② P(A ∪ B)/P(B) ③ P(A)/P(A ∩ B) ④ P(A) + P(B)

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
B가 발생한 경우만을 기준으로 삼으므로 A와 B가 동시에 발생하는 확률을 B의 확률로 나눈다.

15. 점화식에 대한 설명으로 옳은 것은?

① 수열의 모든 항을 서로 무관하게 정하는 식이다. ② 현재 항을 이전 항들의 함수로 나타내는 관계식이다. ③ 표본공간의 원소 수를 나타내는 식이다. ④ 순열과 조합을 항상 같은 값으로 만드는 식이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
점화식은 수열 항 사이의 관계를 나타낸다. 수열을 하나로 결정하려면 보통 초기조건도 함께 필요하다.

16. a₀ = 2, a_n = a_n−1 + 4일 때 일반항은?

① a_n = 2n + 4 ② a_n = 4n ③ a_n = 2 + 4n ④ a_n = 2 · 4ⁿ

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
초기항 2에서 한 단계마다 4씩 증가하므로 n단계 뒤에는 4n이 더해져 a_n = 2 + 4n이다.

17. c_n = 2c_n−1 + 1, c₁ = 1의 일반항은?

① 2n + 1 ② 2ⁿ − 1 ③ 2ⁿ⁻¹ ④ n² − 1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
반복 대입하면 2의 거듭제곱의 합이 나타나며 정리하면 c_n = 2ⁿ − 1이다.

18. 6개의 상자에 25개의 물체를 넣을 때 비둘기집 원리로 보장되는 것은?

① 모든 상자에 정확히 4개가 들어간다. ② 어떤 상자에도 5개는 들어가지 않는다. ③ 적어도 두 상자는 비어 있다. ④ 적어도 한 상자에는 5개 이상이 들어간다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
⌈25/6⌉ = 5이므로 적어도 하나의 상자에는 물체가 5개 이상 들어간다.

19. 비둘기집 원리를 적용할 때 가장 먼저 정해야 할 것은?

① 모든 물체의 순열 ② 이항계수의 대칭성 ③ 문제에서 물체와 상자에 해당하는 대상을 무엇으로 볼지 ④ 사건들의 조건부확률

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
비둘기집 원리의 응용에서는 어떤 대상을 물체로 세고 어떤 분류 영역을 상자로 볼지 정하는 것이 핵심이다.

20. 순열과 조합의 가장 중요한 차이는?

① 선택한 원소의 순서를 구별하는지 여부 ② 표본공간이 유한한지 여부 ③ 모든 원소가 같은지 여부 ④ 초기조건이 존재하는지 여부

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
순열은 같은 원소를 골라도 나열 순서가 다르면 다른 결과로 세지만, 조합은 선택된 원소 집합만 같으면 같은 결과로 센다.