순열과 조합

세 사람을 위원으로 뽑는 일과 회장, 부회장, 총무로 뽑는 일은 같은 세 사람을 고르더라도 세는 대상이 다릅니다. 위원은 누가 뽑혔는지만 중요하지만, 직책은 누가 어느 자리를 맡았는지까지 중요하기 때문입니다. 그래서 경우의 수를 셀 때는 공식부터 고르지 말고, 순서가 있는지와 같은 것을 다시 고를 수 있는지를 먼저 정해야 합니다. 이 글에서는 합과 곱의 법칙, 중복 세기의 두 법칙으로 순열과 조합의 공식을 이끌어 냅니다.

순열은 순서까지 센다

서로 다른 n개에서 r개를 골라 순서대로 늘어놓는 것을 순열(permutation)이라 하고, 그 수를 $P(n,r)$로 씁니다. 첫 자리에 n가지, 둘째 자리에 남은 n − 1가지, 이렇게 r자리를 채우므로 곱의 법칙에 따라 다음과 같습니다. 여기서 $n!=1\cdot2\cdots n$은 합·곱 기호와 계승에서 본 계승이고, $0!=1$로 약속합니다.

5명 가운데 회장과 부회장을 한 명씩 뽑으면 5 × 4 = 20가지입니다. 같은 것을 다시 고를 수 있다면 자리마다 n가지이므로 길이 r인 문자열은 $n^r$개입니다. 같은 것이 섞여 있는 배열은 먼저 모두 다르다고 보고 센 뒤 중복을 나눕니다. A, A, B, C를 늘어놓는 방법은 두 A를 A₁, A₂로 구별하면 4! = 24가지인데, A₁과 A₂를 맞바꾼 두 배열은 실제로 같은 문자열이므로 2!로 나누어 12가지입니다. 일반적으로 n개 가운데 같은 것이 $n_1,n_2,\ldots$개씩 있으면 $n!/(n_1!\,n_2!\cdots)$가지입니다.

서로 다른 n명을 둥근 탁자에 앉히는데 돌려서 같은 배치를 하나로 본다면 $(n-1)!$가지입니다. 한 사람의 자리를 기준으로 고정하면 나머지 n − 1명을 늘어놓는 것과 같기 때문입니다. 뒤집어서 같은 배치까지 하나로 볼지는 문제의 약속이므로, 그런 약속이 없으면 2로 나누지 않습니다.

조합은 고른 집합만 센다

서로 다른 n개에서 순서 없이 r개를 고르는 것을 조합(combination)이라 하고, 그 수를 $\binom nr$로 씁니다. r개를 고른 조합 하나는 그 r개를 늘어놓는 $r!$가지 순열로 세어지므로, 순열의 수를 $r!$로 나누면 조합의 수가 됩니다.

5명 가운데 위원 2명을 뽑으면 20/2 = 10가지입니다. r개를 고르는 것은 고르지 않을 n − r개를 정하는 것과 같으므로 $\binom nr=\binom n{n-r}$입니다. 같은 것을 다시 고를 수 있으면서 순서는 없는 선택을 중복조합이라고 합니다. 서로 다른 n종류에서 모두 r개를 고르는 방법은 $\binom{n+r-1}r$가지입니다. 과일 세 종류에서 4개를 고르는 일은 별 4개와 칸막이 2개를 한 줄로 놓는 일과 같은데, 칸막이가 별을 세 무리로 나누어 각 종류의 개수를 정하기 때문입니다. 자리 6개 가운데 칸막이 2개의 자리를 고르면 되므로 $\binom62=15$가지입니다.

from itertools import combinations, combinations_with_replacement, permutations
from math import comb, factorial, perm

people = "ABCDE"
print(len(list(permutations(people, 2))), perm(5, 2))
print(len(list(combinations(people, 2))), comb(5, 2))
print(len(set(permutations("AABC"))), factorial(4) // factorial(2))
print(len(list(combinations_with_replacement("xyz", 4))), comb(3 + 4 - 1, 4))

20 20
10 10
12 12
15 15

itertools의 세 함수는 순열, 조합, 중복조합을 실제로 하나씩 만들어 내고, math의 perm과 comb는 공식으로 개수를 계산합니다. 줄마다 직접 만든 개수와 공식의 값이 같습니다. 셋째 줄에서 permutations("AABC")는 두 A를 서로 다른 자리의 문자로 보고 24개를 만드는데, set으로 같은 문자열을 하나로 모으면 12개가 남습니다.

Pascal 관계와 범위 밖의 약속

n ≥ 1일 때 특정한 한 사람을 정해 두면, r명을 고르는 방법은 그 사람을 고르는 경우와 고르지 않는 경우로 나뉩니다. 고르면 나머지 n − 1명에서 r − 1명을, 고르지 않으면 r명을 더 고르므로 다음이 성립합니다. 이것을 Pascal 관계(Pascal's rule)라고 합니다.

r = 0이나 r = n에서는 오른쪽에 $\binom{n-1}{-1}$이나 $\binom{n-1}n$처럼 범위 밖의 값이 나옵니다. 음수 개를 고르거나 가진 것보다 많이 고르는 방법은 없으므로, 이런 값은 0으로 약속합니다. 그러면 r = 0에서 0 + 1 = 1, r = n에서 1 + 0 = 1로 관계가 그대로 맞습니다. 재귀의 출발점은 $\binom00=1$, 곧 빈 집합에서 아무것도 고르지 않는 한 가지입니다. n = 0에는 정해 둘 사람이 없으므로 Pascal 관계를 쓰지 않습니다.

from math import comb


def c(n, k):
    if k < 0 or k > n:
        return 0
    if n == 0:
        return 1
    return c(n - 1, k - 1) + c(n - 1, k)


for n in range(5):
    row = [c(n, k) for k in range(n + 1)]
    print(row, row == [comb(n, k) for k in range(n + 1)])

[1] True
[1, 1] True
[1, 2, 1] True
[1, 3, 3, 1] True
[1, 4, 6, 4, 1] True

c는 범위 밖이면 0을, $\binom00$이면 1을 돌려주고, 나머지는 Pascal 관계로 계산합니다. 각 행을 계승 공식으로 계산하는 math.comb의 값과 비교하면 모두 같습니다. math.comb도 k가 n보다 크면 0을 돌려주지만 음수 인자에서는 ValueError를 내므로, 범위 밖을 0으로 보는 약속은 이처럼 함수를 감싸서 처리해야 합니다. 수학의 약속과 라이브러리의 입력 조건은 따로 확인해야 합니다. 자세한 조건은 Python 공식 문서의 math.integer.comb에 있습니다. Python 3.15부터 math.comb는 새 math.integer 모듈의 같은 함수를 가리키는 별칭이라, 이 글의 코드는 3.14와 3.15에서 똑같이 동작합니다.

이항정리

$(a+b)^n$을 전개하면 괄호 n개에서 a나 b를 하나씩 골라 곱한 항들의 합이 됩니다. $a^{n-k}b^k$ 꼴의 항은 n개 괄호 가운데 b를 고를 k개를 정하는 방법만큼 나오므로, 그 계수는 $\binom nk$입니다. 이것을 이항정리(binomial theorem)라고 합니다.

a = b = 1을 넣으면 $\sum_k\binom nk=2^n$이 되는데, 원소 n개인 집합의 부분집합을 크기별로 세어 더한 것이 부분집합 전체의 수 $2^n$과 같다는 뜻입니다. 위 코드의 행들은 이 계수를 늘어놓은 Pascal 삼각형이고, 넷째 행 1, 4, 6, 4, 1의 합은 $2^4=16$입니다. 같은 계수는 독립과 반복 시행의 확률에서도 쓰입니다.

더 깊이: 부호를 번갈아 더하면 0이 되는 이유

이항정리에 $a=1$, $b=-1$을 넣으면 $n\ge1$일 때 $\sum_{k=0}^{n}(-1)^k\binom nk=(1-1)^n=0$입니다. 짝수 k의 항을 한쪽으로 옮기면, 원소 n개인 집합에서 원소를 짝수 개 고르는 방법과 홀수 개 고르는 방법의 수가 같다는 뜻이고, 둘을 더하면 $2^n$이므로 각각 $2^{n-1}$입니다. $n=4$라면 짝수 개를 고르는 1 + 6 + 1과 홀수 개를 고르는 4 + 4가 모두 8입니다.

식 없이 짝을 지어 보일 수도 있습니다. 집합의 원소 하나 x를 정해 두고, 부분집합마다 x가 있으면 빼고 없으면 넣는 짝을 지으면 크기가 정확히 1만큼 달라지므로, 짝수 크기의 부분집합과 홀수 크기의 부분집합이 하나씩 빠짐없이 짝지어집니다. 원소가 하나 이상 있어야 x를 정할 수 있으므로, 빈 집합 하나만 있는 $n=0$에서는 짝수 쪽만 1개라 성립하지 않습니다.

이 등식은 포함·배제가 왜 맞는지도 설명합니다. 어떤 원소가 집합 m개($m\ge1$)에 속한다면, 포함·배제의 식에서 그 원소는 한 집합씩 더할 때 $\binom m1$번, 두 집합의 교집합을 뺄 때 $\binom m2$번, 이렇게 부호를 바꾸어 가며 세어집니다. 그 합은 $\sum_{k=1}^{m}(-1)^{k+1}\binom mk=1-\sum_{k=0}^{m}(-1)^k\binom mk=1$이므로, 합집합의 원소는 몇 개의 집합에 겹쳐 있든 정확히 한 번씩 세어집니다.

이름 있는 팀과 이름 없는 분할

서로 다른 6명을 빨강, 파랑, 초록 팀에 2명씩 배정하면, 빨강 팀 2명을 고르고 남은 4명에서 파랑 팀 2명을 고르면 초록 팀이 정해지므로 $\binom62\binom42\binom22=15\cdot6\cdot1=90$가지입니다. 팀에 이름이 없는 2명짜리 블록 세 개로 나누는 집합의 분할이라면 사정이 다릅니다. 같은 세 블록에 색 이름을 붙이는 3! = 6가지가 모두 같은 분할이므로 90/6 = 15가지입니다.

이름이 없더라도 크기가 다른 블록끼리는 크기로 구별되므로 나누지 않습니다. 크기가 같은 블록끼리만 서로 바꾸어도 같은 분할이 되므로, 크기가 같은 블록의 수의 계승으로 나눕니다. 블록의 수 k만 보고 언제나 k!로 나누면 틀립니다.

정리

• 순서가 있으면 순열 $P(n,r)=n!/(n-r)!$, 순서가 없으면 조합 $\binom nr=n!/(r!(n-r)!)$이고, 조합은 같은 선택을 $r!$번 센 순열을 나눈 것입니다.
• 같은 것을 다시 고를 수 있는 문자열은 $n^r$개, 순서 없는 중복조합은 $\binom{n+r-1}r$개이며, 같은 것이 섞인 배열은 중복된 순서를 나눕니다.
• Pascal 관계는 한 원소를 고르는 경우와 고르지 않는 경우로 나누어 얻고, 범위 밖의 값을 0으로 약속하면 끝에서도 성립합니다.
• 이항정리의 계수는 괄호 n개에서 b를 고를 자리를 정하는 조합의 수입니다.
• 이름 있는 팀은 나누지 않고, 이름 없는 분할에서는 크기가 같은 블록끼리 바꾼 중복만 나눕니다.

연습 문제

1. 위원과 직책

6명 가운데 대표 3명을 순서 없이 뽑는 경우와, 서로 다른 직책 세 개를 맡기는 경우의 수를 비교하세요.

2. 종류마다 하나 이상

스티커 세 종류에서 모두 5개를 고르는데, 종류마다 하나 이상 고르려고 합니다. 같은 종류끼리는 구별하지 않고 순서도 없을 때 방법은 몇 가지인가요?

3. 두 팀으로 나누기

서로 다른 4명을 이름 있는 A팀과 B팀에 2명씩 나누는 경우와, 이름 없는 두 쌍으로 나누는 경우를 비교하세요. 이름 없이 1명과 3명으로 나눌 때는 왜 2!로 나누지 않나요?

공식 이름보다 먼저 "순서가 있는가, 같은 것을 다시 고를 수 있는가, 무엇을 같은 결과로 보는가"를 적어 보세요. 다음 장의 표본공간과 조건부확률에서는 이렇게 센 경우의 수로 확률을 계산하고, 그렇게 해도 되는 조건을 따집니다.