Lesson 15 of 20

조합 — 순서를 따지지 않는 뽑기

파스칼 삼각형과 이항정리

이번엔 학생 5명 중 3명을 뽑아 청소 당번을 정합니다. 등수는 없어요. "민준·서연·지호"와 "지호·민준·서연"은 같은 조입니다.

순열로는 60가지였죠. 그런데 같은 3명을 늘어놓는 방법이 3! = 6가지이므로, 6개씩 묶어서 하나로 세야 합니다.

C(5,3) = P(5,3) / 3! = 60 / 6 = 10

일반적으로 조합(combination)은 이렇게 씁니다.

C(n, r) = n! / (r! (n−r)!) (읽기: n개 중 r개 뽑기)

High school순서를 따지지 않는 뽑기

14강의 순열에서 순서를 지우면 조합입니다.

C(n,r) = P(n,r) / r!

왜 r! 로 나누나

같은 r 개의 조합이 순열에서는 r! 번 세어집니다.

조합 {A,B,C}	순열에서
—	ABC, ACB, BAC, BCA, CAB, CBA — 6가지

6 = 3! — 그만큼 나누면 된다 (14강의 기술)

언제 조합인가

상황	순서	—
1·2·3등 뽑기	중요	순열
대표 3명 뽑기	상관없다	조합 ✔
로또 번호	상관없다	조합
비밀번호	중요	순열

"뽑아서 무엇을 하나" 를 보면 판단된다

비유 — 반장 선거와 대표단

—	—
반장·부반장 뽑기	A반장 B부반장 ≠ B반장 A부반장 → 순열
대표 2명 뽑기	A,B = B,A → 조합

뽑은 뒤에 역할이 다르면 순열, 같으면 조합

같은 3명을 늘어놓는 6가지를 하나로 묶은 것이 조합입니다.

Python Runs in your browser

from itertools import combinations, permutations
import math

학생 = ["민준", "서연", "지호", "하윤", "예준"]
r = 3
조합들 = list(combinations(학생, r))
for 조 in 조합들:
    print("  ", " · ".join(조))
print()
print(f"순열 P(5,3) = {math.perm(5,3)}  → {r}! = {math.factorial(r)} 로 나누면")
print(f"조합 C(5,3) = {math.comb(5, r)}  (실제로 센 개수 {len(조합들)})")

🎮 파스칼 삼각형을 쌓아 보세요

양옆의 두 수를 더하면 아래 수가 됩니다. 그 수가 바로 C(n, r) 이에요. 칸을 눌러 그 수가 무슨 뜻인지 확인해 보세요.

High school파스칼 삼각형이 왜 그렇게 되나

조합수를 표로 배열하면 아름다운 규칙이 나옵니다.

C(n,r) = C(n−1, r−1) + C(n−1, r)

왜 그런가 — 아주 예쁜 논증

n 명 중 r 명을 뽑는데, 특정 한 명(A)을 기준으로 나눕니다.

경우	남은 선택
A 를 뽑는다	나머지 n−1 중 r−1 명
A 를 안 뽑는다	나머지 n−1 중 r 명

두 경우가 겹치지 않고 빠짐없다 → 13강 합의 법칙

계산 없이 논리만으로 공식이 나왔습니다. 이런 걸 조합적 증명이라 해요.

"같은 것을 두 가지로 센다" 는 조합론의 핵심 기술이다

삼각형의 다른 성질들

성질	뜻
각 줄의 합 = 2ⁿ	7강의 부분집합 개수 ⭐
좌우 대칭	C(n,r) = C(n,n−r)
대각선	1, 자연수, 삼각수, …

한 표에서 여러 사실이 동시에 보인다

12강과도 이어집니다

이 식이 점화식입니다. 그래서 동적 계획법으로 계산할 수 있어요.

C(n,r) 을 재귀로 그냥 짜면 느리다 — 12강의 그 문제

파스칼의 항등식 — 왜 더하면 될까

C(n, r) = C(n−1, r−1) + C(n−1, r)

공식을 외우는 대신 이야기로 이해해 봅시다. n명 중 r명을 뽑는데, 그중 민준이를 기준으로 경우를 나눕니다.

민준이가 뽑힌 경우 — 나머지 n−1명 중 r−1명을 더 뽑는다 → C(n−1, r−1)
민준이가 안 뽑힌 경우 — 나머지 n−1명 중 r명을 뽑는다 → C(n−1, r)

둘은 겹치지 않고 이 둘이 전부이므로 합의 법칙으로 더하면 됩니다. 이런 증명을 조합적 증명이라고 해요 — 계산 없이 세는 방식만으로 등식을 세웁니다.

덧셈만으로 조합의 수가 전부 만들어집니다.

Python Runs in your browser

import math

# 파스칼 삼각형을 직접 쌓아 보기
줄 = [1]
for n in range(9):
    print("".join(f"{x:>5}" for x in 줄).center(50))
    줄 = [1] + [줄[i] + 줄[i + 1] for i in range(len(줄) - 1)] + [1]

print()
print("5번째 줄 =", [math.comb(5, r) for r in range(6)], "← C(5,0) ~ C(5,5)")
print("C(5,2) =", math.comb(5, 2), "= C(4,1) + C(4,2) =", math.comb(4,1), "+", math.comb(4,2))

High school대칭성 — C(n,r) = C(n,n−r)

note 의 이 성질을 왜 당연한지 봅시다.

"뽑을 것을 고르기" = "안 뽑을 것을 고르기"

일대일 대응입니다

10명 중 3명 뽑기	10명 중 7명 안 뽑기
C(10,3) = 120	C(10,7) = 120 ✔

뽑으면 나머지가 자동으로 정해진다 — 10강의 전단사

계산에 유용합니다

계산	—
C(100, 98)	계산이 크다
C(100, 2)	100×99/2 = 4950 ✔

r 이 크면 n−r 로 바꿔 계산한다 — 실전 요령

그리고 이항정리

(x+y)ⁿ 의 전개에서 계수가 C(n,r) 이다

왜 그런가

(x+y)(x+y)…(x+y) 를 펼칠 때 각 괄호에서 x 또는 y 를 고릅니다.

x 를 r 번 고르는 방법	—
C(n,r) 가지	그래서 계수가 그것 ✔

전개는 고르기였다 — 대수와 조합론이 만난다

특별한 값들

x, y	결과
x=y=1	합 = 2ⁿ (7강)
x=1, y=−1	교대합 = 0 — 17강 ⭐

두 번째가 17강 포함배제의 부호가 상쇄되는 근거다

이항정리 — 괄호를 펼치면 조합이 나온다

(x + y)ⁿ = Σ C(n,r) x^n−r y^r

왜 조합이 나올까요? (x+y)(x+y)(x+y) 를 펼칠 때, 각 괄호에서 x나 y를 하나씩 골라 곱합니다. x²y 항이 나오려면 세 괄호 중 어느 하나에서 y를 고르면 되므로 C(3,1) = 3가지 — 그래서 계수가 3입니다.

덤으로, x = y = 1 을 넣으면 2ⁿ = C(n,0) + C(n,1) + … + C(n,n). 7강에서 본 부분집합의 개수 2ⁿ이 여기서 다시 나옵니다 — "0개 뽑기 + 1개 뽑기 + … + n개 뽑기 = 모든 부분집합"이니까요.

이항계수는 파스칼 삼각형의 한 줄이고, 그 합은 2ⁿ입니다.

Python Runs in your browser

import math

n = 4
항들 = []
for r in range(n + 1):
    계수 = math.comb(n, r)
    항들.append(f"{계수 if 계수 != 1 else ''}x^{n-r}y^{r}")
print(f"(x + y)^{n} = " + " + ".join(항들).replace("x^0", "").replace("y^0", ""))
print("계수:", [math.comb(n, r) for r in range(n + 1)], "← 파스칼 삼각형 그 줄")
print()
합 = sum(math.comb(n, r) for r in range(n + 1))
print(f"계수를 모두 더하면 {합} = 2^{n} = 부분집합의 개수 (7강!)")

로또는 순서를 따지지 않으므로 조합입니다.

Python Runs in your browser

import math
# 로또 1등 확률 — 45개 중 6개를 순서 없이 뽑기
전체 = math.comb(45, 6)
print(f"C(45,6) = {전체:,} 가지")
print(f"1등 확률 = 1 / {전체:,} ≈ {1/전체:.10f}")
print()
print(f"매주 1장씩 사면 평균 {전체/52:,.0f}년 걸립니다.")
print(f"순서까지 따진다면 P(45,6) = {math.perm(45,6):,} — 720배 더 어렵습니다.")

High school꼭 기억하세요

15강의 정리와 실전입니다.

조합 = 순서를 안 따지는 뽑기 — C(n,r) = n!/(r!(n−r)!)

순열과 조합 고르는 법

물음	답
순서가 결과를 바꾸나	바꾸면 순열
—	안 바꾸면 조합

헷갈리면 작은 예로 직접 세어 본다 — 13강의 조언

중복을 허용하면

종류	공식	예
중복 순열	nʳ	비밀번호
중복 조합	C(n+r−1, r)	같은 종류를 여러 개

네 가지 조합이 있다 — 순서 O/X × 중복 O/X

계산할 때 주의

# 나쁘다 — 큰 수 계산
math.factorial(100) // (math.factorial(3) * math.factorial(97))

# 좋다
math.comb(100, 3)     # 파이썬 3.8+

팩토리얼을 직접 계산하면 자릿수가 폭발한다 — 약분이 먼저다

알고리즘에서

구조	경우의 수
n 개 중 r 개 고르기	C(n,r)
n 개 중 임의 개수	2ⁿ (7강)

"몇 개인지 정해져 있으면" 조합, "아무 개수나" 면 부분집합

🤔 Check yourself

10명의 학생 중 4명을 뽑아 조 편성을 하는 방법의 수는?

Answer 조에는 순서·직책이 없으므로 조합입니다 — C(10,4) = 210. P(10,4)=5040은 네 명에게 서로 다른 직책을 줄 때의 수이고, 정확히 4! = 24배 큽니다.

🤔 Check yourself

C(8, 6) 을 가장 쉽게 계산하는 방법은?

Answer 대칭성 C(n,r) = C(n,n−r) 을 쓰면 6개 뽑기가 2개 안 뽑기가 됩니다 — C(8,2) = (8×7)/2 = 28. 뽑을 쪽과 남길 쪽 중 작은 쪽으로 계산하세요.

🤔 Check yourself

C(n,0) + C(n,1) + … + C(n,n) 의 값은?

Answer 0개 뽑기부터 n개 뽑기까지 모두 더하면 모든 부분집합의 개수가 되므로 2ⁿ입니다 (7강). 이항정리에 x = y = 1을 넣어도 같은 결과가 나와요.