[경우의 수] 조합부터 이항정리까지 — 중복조합·분배 완전 정복

1편에서 순서가 중요한 순열을 배웠다.
이번 2편에서는 순서를 따지지 않고 선택하는 조합, 중복을 허용하는 중복조합, 그리고 조합의 수를 이용한 강력한 공식인 이항정리까지 완전히 정리한다.

1. 조합 (Combination)

조합이란?

서로 다른 n개에서 순서를 고려하지 않고 r개를 선택하는 경우의 수를 조합이라 하고 nCr 또는 C(n,r) 또는 (n r)로 나타낸다.

📐 조합 공식

nCr = n! / (r! × (n−r)!) = nPr / r!

특수한 경우: nC0 = 1,   nCn = 1,   nC1 = n

대칭성: nCr = nC(n−r)   (선택 = 나머지 선택)

💡 순열 → 조합 관계: nCr = nPr / r!
순열에서 뽑은 r개의 순서를 무시하면 조합이 된다.
r개를 배열하는 경우 r!가지가 모두 같은 하나의 조합이므로
nCr = nPr / r! = n!/(r!(n−r)!)

예제 1   조합 계산

(1) 8C3    (2) 10C7    (3) 5명 중 대표 3명을 뽑는 경우의 수

풀이

(1) 8C3 = 8!/(3!×5!) = (8×7×6)/(3×2×1) = 336/6 = 56

(2) 10C7 = 10C3 = (10×9×8)/(3×2×1) = 720/6 = 120
(대칭성 이용: 10C7 = 10C(10−7) = 10C3)

(3) 순서 무관 → 조합: 5C3 = 5C2 = (5×4)/(2×1) = 10

답: (1) 56   (2) 120   (3) 10

조합의 핵심 성질

📐 조합의 성질

① nCr = nC(n−r)   (대칭성)

② nCr = (n−1)C(r−1) + (n−1)Cr   (파스칼의 삼각형)

③ nC0 + nC1 + nC2 + ··· + nCn = 2ⁿ   (부분집합의 수)

💡 파스칼의 삼각형 — (n−1)Cr−1 + (n−1)Cr = nCr
n개 중 r개 선택할 때, 특정 원소 A를 기준으로:
A를 포함하는 경우: 나머지 n−1개에서 r−1개 → (n−1)C(r−1)
A를 포함하지 않는 경우: 나머지 n−1개에서 r개 → (n−1)Cr
두 경우를 더하면 nCr

예제 2   조합의 활용

10명 중 위원회를 구성할 때, 남자 4명·여자 6명 중에서 남자 2명과 여자 3명을 뽑는 경우의 수를 구하여라.

풀이

남자 2명 선택: 4C2 = 6
여자 3명 선택: 6C3 = 20

두 선택이 독립적으로 동시에 → 곱의 법칙
6 × 20 = 120

답: 120

예제 3   조건부 조합 — 특정 인원 포함/배제

10명 중 5명을 뽑을 때, 특정인 A는 반드시 포함하고 B는 반드시 제외하는 경우의 수를 구하여라.

풀이

A 포함, B 제외 → 실제 선택 가능 인원: 10명 − A(이미 포함) − B(제외) = 8명
이 8명 중 4명을 추가 선택 (A 포함해서 총 5명)

8C4 = 8!/(4!×4!) = (8×7×6×5)/(4×3×2×1) = 1680/24 = 70

답: 70

 

2. 조합의 활용 — 다양한 유형

직선·삼각형·대각선의 수

📐 도형 관련 공식

직선의 수: n개의 점(어느 3점도 일직선이 아님) → nC2

삼각형의 수: n개의 점(어느 3점도 일직선이 아님) → nC3

볼록 n각형의 대각선 수: nC2 − n = n(n−3)/2

예제 4   도형의 경우의 수

(1) 평면 위 8개의 점(어느 3점도 일직선 아님)에서 만들 수 있는 삼각형의 수

(2) 팔각형(8각형)의 대각선의 수

풀이

(1) 8점 중 3점 선택 → 삼각형 1개:
8C3 = 56 → 56개

(2) 8C2 − 8 = 28 − 8 = 20개
또는 공식: n(n−3)/2 = 8×5/2 = 20 ✓

답: (1) 56   (2) 20

분할과 분배

📐 n개를 p, q, r, ... 개의 그룹으로 나누기

서로 다른 그룹으로 나눌 때: nC_p × (n−p)C_q × ···

같은 크기의 그룹으로 나눌 때: 추가로 그룹 수!로 나눈다

예제 5   분할과 분배

(1) 6명을 3명씩 두 그룹 A, B로 나누는 경우의 수

(2) 6명을 3명씩 두 그룹으로 나누는 경우의 수 (그룹에 이름 없음)

풀이

(1) A그룹 3명 선택: 6C3 = 20
(나머지 3명이 자동으로 B그룹)
→ 20가지

(2) 그룹에 이름이 없으면 {A조, B조}와 {B조, A조}가 같음
20 ÷ 2! = 20/2 = 10가지

답: (1) 20   (2) 10

 

반응형

 

3. 중복조합

조합은 같은 것을 중복 선택할 수 없었다. 중복조합은 중복을 허용하여 선택하되 순서는 고려하지 않는 경우다.

📐 중복조합 공식

서로 다른 n개에서 중복을 허용하여 r개를 선택 (순서 무관):

nHr = (n+r−1)Cr

기호: ₙHᵣ (H는 Homogeneous의 H)

💡 중복조합 공식 유도 — "칸막이" 방법
n종류 중 r개 선택(중복허용) = r개의 ●와 (n−1)개의 | 를 일렬로 배열하는 경우
총 (r+n−1)개 중 r개의 ●를 선택 = (n+r−1)Cr

예제 6   중복조합

(1) 4종류 과자에서 중복 허용해 3개를 선택하는 경우의 수

(2) x + y + z = 5 를 만족하는 음이 아닌 정수해의 수

💡 (2) 3개의 변수(x,y,z)에 5를 분배하는 것 = 중복조합

풀이

(1) 4H3 = (4+3−1)C3 = 6C3 = 20

(2) x+y+z=5, x,y,z≥0 → 3가지에서 중복허용 5개 선택
3H5 = (3+5−1)C5 = 7C5 = 7C2 = 21

답: (1) 20   (2) 21

예제 7   중복조합 활용 — 정수해

x + y + z = 10 을 만족하는 양의 정수해의 수를 구하여라. (x, y, z ≥ 1)

💡 x'=x−1, y'=y−1, z'=z−1로 치환하면 x'+y'+z'=7 (음이 아닌 정수)

풀이

x'=x−1≥0, y'=y−1≥0, z'=z−1≥0으로 놓으면
x'+y'+z' = 10−3 = 7

3H7 = (3+7−1)C7 = 9C7 = 9C2 = 36

답: 36

 

4. 이항정리

이항정리란?

(a+b)ⁿ을 전개할 때 각 항의 계수를 조합의 수로 나타내는 공식이다. 직접 계산하지 않아도 특정 항의 계수를 바로 구할 수 있어서 매우 강력하다.

📐 이항정리

(a+b)ⁿ = Σ_r=0ⁿ nCr · a^n−r · b^r

= nC0·aⁿ + nC1·aⁿ⁻¹b + nC2·aⁿ⁻²b² + ··· + nCn·bⁿ

일반항 (r번째 항 = r+1번째 항):

T_r+1 = nCr · a^n−r · b^r

예제 8   이항정리 — 특정 항 계수

(1) (x+2)⁵의 전개식에서 x³의 계수를 구하여라.

(2) (2x−1)⁶의 전개식에서 x⁴의 계수를 구하여라.

💡 일반항 공식 T(r+1) = nCr · aⁿ⁻ʳ · bʳ 이용

풀이

(1) (x+2)⁵에서 a=x, b=2, n=5
T(r+1) = 5Cr · x^(5−r) · 2^r
x³이 되려면 5−r=3 → r=2
T3 = 5C2 · 2² = 10 × 4 = 40

(2) (2x−1)⁶에서 a=2x, b=−1, n=6
T(r+1) = 6Cr · (2x)^(6−r) · (−1)^r
= 6Cr · 2^(6−r) · (−1)^r · x^(6−r)
x⁴이 되려면 6−r=4 → r=2
T3 = 6C2 · 2⁴ · (−1)² = 15 × 16 × 1 = 240

답: (1) 40   (2) 240

📐 이항정리의 주요 공식 (x=1, −1 대입)

2ⁿ = nC0 + nC1 + nC2 + ··· + nCn   (x=1, b=1 대입)

0 = nC0 − nC1 + nC2 − ··· + (−1)ⁿnCn   (x=1, b=−1 대입)

→ 짝수 번째 합 = 홀수 번째 합 = 2ⁿ⁻¹

예제 9   이항계수의 합

nC0 + nC1 + nC2 + ··· + nCn = 256 일 때, n을 구하여라.

풀이

nC0 + nC1 + ··· + nCn = 2ⁿ = 256 = 2⁸
→ n = 8

답: n = 8

종합 예제   경우의 수 종합

A, B, C, D, E, F 6명 중에서 4명을 뽑아 위원회를 구성할 때,
A와 B 중 적어도 한 명은 포함되는 경우의 수를 구하여라.

💡 (전체) − (A, B 모두 제외)로 구한다.

풀이

전체: 6C4 = 15
A, B 모두 제외(C~F 4명 중 4명): 4C4 = 1

적어도 한 명 포함 = 15 − 1 = 14

답: 14

📌 핵심 정리

• 조합 nCr: n!/(r!(n−r)!). 순서 X, 중복 X
• 대칭성: nCr = nC(n−r). 계산 시 활용
• 파스칼: nCr = (n−1)C(r−1) + (n−1)Cr
• 이항계수 합: nC0+nC1+···+nCn = 2ⁿ
• 도형: 직선=nC2, 삼각형=nC3, 대각선=nC2−n=n(n−3)/2
• 분할: 같은 크기 그룹 → 그룹 수!로 나눔
• 중복조합 nHr: (n+r−1)Cr. 중복 O, 순서 X
• 정수해: x+y+z=n (음이 아닌 정수) → 3Hn = (n+2)C2
• 양의 정수해: xi≥1이면 x'i=xi−1로 치환 후 음이 아닌 정수해
• 이항정리: (a+b)ⁿ의 일반항 T(r+1) = nCr·aⁿ⁻ʳ·bʳ
• 적어도: 전체 − (모두 해당 안 됨)