순열과 조합

세 사람을 위원으로 고르는 일과 회장·부회장·간사로 배정하는 일은 같은 인원을 고르더라도 다른 결과를 셉니다. 합과 곱의 법칙을 바탕으로 공식부터 고르지 않고 순서와 중복 허용 여부를 먼저 정합니다.

순열은 역할 순서가 있다

계승 기호에서 $n!=1\cdot2\cdots n$, $0!=1$을 복습합니다. 이 절의 n과 r은 정수이며 중복 없는 선택에서는 $0\le r\le n$입니다. n개의 서로 다른 대상에서 r개를 중복 없이 순서 있게 고르면 첫 자리 n, 다음 n−1,… 선택으로 $P(n,r)=n!/(n-r)!$입니다. 5명 중 회장·부회장을 서로 다르게 뽑으면 5×4=20개입니다. 중복을 허용하는 길이 r의 문자열이면 각 자리가 n개라 nʳ개입니다. 0!=1은 아무것도 배치하지 않는 하나의 경우와 일관됩니다.

같은 물건이 반복된 전체 배열은 $n!/(n_1!n_2!\cdots)$입니다. A,A,B,C 배열은 4!/2!=12개입니다. A 두 개를 임시로 다른 것으로 세면 각각의 실제 문자열이 두 번씩 나오므로 나누었습니다. 서로 다른 n명을 원탁에 앉히고 회전만 같다고 보면 (n−1)!입니다. 한 사람을 기준 자리에 고정합니다. 거울상까지 같다고 보는 조건이면 다른 문제이므로 자동으로 2로 나누지 않습니다.

조합은 선택한 집합만 본다

순서 없이 r개 고르는 $\binom nr$는 같은 r원소가 r!가지 순서로 중복 세어진 순열을 나눈 것입니다.

$$\binom nr=\frac{n!}{r!(n-r)!}.$$

5명 중 위원 2명을 고르는 경우의 수는 20/2=10개입니다. 고를 r개와 안 고를 n−r개가 서로 대응하므로 $\binom nr=\binom n{n-r}$입니다.

Pascal 관계의 끝점과 시작 행

n≥1이면 특정 인물 한 명을 골라, 그 사람이 포함된 선택과 포함되지 않은 선택을 나눕니다. 포함되면 나머지 n−1명 중 r−1명, 포함되지 않으면 나머지 중 r명을 고르므로

$$\binom nr=\binom{n-1}{r-1}+\binom{n-1}r\quad(n\ge1,\ 0\le r\le n)$$

입니다. 여기서는 비음수 정수 m에 대해 아래 첨자가 범위 밖이면 $\binom m k=0$으로 약속합니다. $k<0$이면 음수 개를 고를 수 없고 $k>m$이면 가진 대상보다 많이 고를 수 없기 때문입니다. 이 약속은 계승 공식에 음수 계승을 대입한다는 뜻이 아닙니다. r=0이면 오른쪽은 0+1=1, r=n이면 1+0=1이 됩니다. 범위 밖에서 0이라는 약속 없이 계승식만 사용한다면 Pascal 관계는 내측 범위 1≤r≤n−1에서 사용합니다.

n=0에는 구분할 특정 인물이 없으므로 위 재귀를 적용하지 않습니다. 기저는 $\binom00=1$이며 빈 집합에서 빈 집합을 고르는 한 가지입니다. m=0에서도 k≠0은 범위 밖이므로 0입니다. C(0,0)을 C(−1,−1)+C(−1,0)으로 계산하지 않습니다.

예를 들어 C(1,0)=0+C(0,0)=1, C(1,1)=C(0,0)+0=1을 시작으로 n=2 행은 1,2,1입니다. 저장소의 docs/cs-textbooks/discrete-math-examples/pascal_boundary.py는 기저와 n=1부터 4까지의 행을 계승 기반 math.comb와 대조합니다. Python math.comb는 음수 인자에서 예외를 내므로 위 범위 밖에서 0이라는 약속은 따로 감싼 함수에서 처리합니다. n=0에 재귀를 요청하면 실패를 표시합니다. 수학적 범위 약속과 API의 입력 조건은 구별합니다. Python 공식 math.comb 설명도 참고할 수 있습니다. 기존 Pascal 항등식을 다른 식으로 바꾼 것이 아니라 적용 범위와 기저를 분명히 한 것입니다.

중복조합은 개수 배정

서로 다른 n종류에서 합 r개를 중복 허용·순서 무관하게 고르면 $\binom{n+r-1}r$입니다. 세 종류 과일 4개를 고르는 일은 비음수 정수 $x_1+x_2+x_3=4$의 해를 세는 것과 같습니다. 물건을 나타내는 별 4개와 구분선 2개를 놓는 자리 6개 중 구분선 2자리를 고르므로 $\binom62=15$입니다. 종류별 최소 하나라면 먼저 하나씩 배정하고 남은 개수를 셉니다.

$(a+b)^n$의 각 항은 n개 괄호에서 b를 고를 k개 위치를 선택하여 생깁니다. 따라서 $\sum_{k=0}^n\binom nk a^{n-k}b^k$인 이항정리를 얻습니다. 조합 계수는 확률의 반복 시행에서도 사용합니다.

선택 심화: 이름 있는 그룹과 이름 없는 분할

서로 다른 5명을 빨강 팀 2명, 파랑 팀 3명으로 나누면 빨강 2명을 고르는 $\binom52=10$가지입니다. 파랑은 남은 3명으로 정해집니다. 그룹 이름과 크기를 고정해 n명을 크기 $n_1,\ldots,n_k$인 팀에 배정하는 일반식은 $n!/(n_1!\cdots n_k!)$이며, 각 크기는 양의 정수이고 합은 n입니다. 첫 팀부터 조합으로 골라 곱하면 중간 계승이 약분되어 이 식을 얻습니다.

예를 들어 6명을 이름 있는 빨강·파랑·초록 팀에 2명씩 배정하면 $\binom62\binom42\binom22=15\cdot6\cdot1=90$입니다. 이름 없는 2명짜리 그룹 세 개로 나누는 집합의 분할이라면 같은 세 그룹에 색 이름을 붙이는 3!=6가지가 중복이므로 90/6=15개입니다. 그룹 이름이 있으면 크기가 같아도 나누지 않습니다. 이름이 없고 여러 그룹의 크기가 같을 때만 그 크기끼리 바꿔 붙인 중복을 제거합니다. 크기가 다른 그룹까지 무조건 k!로 나누면 틀립니다.

스스로 풀어보기

문제 1. 6명 중 대표 3명을 순서 없이 고르는 경우와 세 개의 서로 다른 직책을 맡기는 경우를 비교하세요.

풀이: 대표 집합은 $\binom63=20$, 직책 배정은 6×5×4=120입니다. 각 대표 집합에 직책을 부여하는 3!=6가지가 있어 20×6=120입니다.

문제 2. 세 종류 스티커를 총 5개 고르되 종류별 하나 이상이어야 합니다. 순서는 없고 같은 종류는 구별하지 않습니다.

힌트: 처음 세 개를 미리 하나씩 배정합니다.

풀이: 남은 2개를 세 종류에 비음수로 배정하므로 $\binom{3+2-1}2=\binom42=6$입니다. (추가수) 200,020,002,110,101,011 여섯 가지로 검산할 수 있습니다. 원래 선택 수는 각각에 1을 더한 값입니다.

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

힌트: 같은 두 쌍에서 A팀과 B팀의 이름을 바꾸면 이름 있는 배정은 달라지지만, 이름 없는 분할은 같습니다. 크기가 다르면 작은 그룹과 큰 그룹을 크기로 구분할 수 있습니다.

풀이: 이름 있는 2명·2명 배정은 $\binom42=6$입니다. 이름 없는 두 쌍은 6/2!=3개이며 $\{1,2\}|\{3,4\}$, $\{1,3\}|\{2,4\}$, $\{1,4\}|\{2,3\}$입니다. 이름 없는 1명·3명 분할은 혼자일 1명을 고르는 4개입니다. 혼자와 세 명 그룹은 크기가 다르므로 같은 분할을 두 번 세지 않았고, 다시 2!로 나누면 2라는 잘못된 답이 됩니다.

공식 이름 대신 '순서 있음/없음, 중복 허용/금지, 같은 결과의 기준'을 적으세요. 개수를 확률로 바꾸려면 표본공간의 동일 가능성 조건도 필요합니다.