순열과 조합

개요 — 동기·문제의식

셈의 기본 원리의 곱의 법칙과 합의 법칙만으로도 많은 것을 셀 수 있지만, 실전의 셈 문제는 거의 언제나 두 가지 축으로 갈라진다 — 순서를 구별하는가, 그리고 같은 대상을 반복해서 뽑을 수 있는가. 이 두 축의 네 가지 조합(순서 있음/없음 × 중복 허용/불허)마다 표준 공식이 하나씩 있고, 이 장은 그 네 공식 — 순열 $P(n,r)$, 조합 $\binom{n}{r}$, 중복순열 $n^r$, 중복조합 $\binom{n+r-1}{r}$ — 을 곱의 법칙에서 엄밀하게 유도한다.

이 과정에서 등장하는 이항계수 $\binom{n}{r}$는 단순한 셈 공식을 넘어 이산수학 전체를 관통하는 중심 대상이다. 이항정리는 이항계수를 다항식 전개의 계수로 재해석하고, 파스칼 항등식과 Vandermonde 항등식은 이항계수들 사이의 관계망을 드러낸다. 무엇보다 이 장의 방법론적 핵심은 조합적 증명(combinatorial proof) — 하나의 유한집합을 두 가지 방식으로 세거나 두 집합 사이에 전단사를 만들어 항등식을 증명하는 기법 — 이다. 대수적 계산으로는 "식이 맞는다"는 것만 알 수 있지만, 조합적 증명은 "왜 같을 수밖에 없는지"를 보여 주며, 포함–배제의 원리과 생성함수에서도 계속 쓰이는 사고방식이다.

직관

$n$명 중 $r$명을 뽑는 문제를 생각하자. 뽑아서 한 줄로 세우면(회장·부회장·총무처럼 역할이 다르면) 순서가 의미를 가지므로 순열이고, 뽑아서 자루에 담으면(동등한 위원 $r$명이면) 순서가 사라지므로 조합이다. 같은 $r$명의 집합이라도 줄 세우는 방법이 $r!$가지이므로, 순열은 조합을 정확히 $r!$배 과잉 계수한다 — $P(n,r)=\binom{n}{r}\cdot r!$이라는 이 관계가 조합 공식의 원천이다.

중복이 허용되면 그림이 달라진다. 순서 있는 중복 선택은 각 자리마다 $n$개의 선택지가 독립적으로 주어지는 것이므로 $n^r$로 곧장 계산된다. 순서 없는 중복 선택(중복조합)은 넷 중 가장 미묘한데, "종류별로 몇 개씩 담았는가"라는 도수 기록만 남기 때문이다. 여기서 별과 막대(stars and bars)라는 그림이 결정적이다 — $r$개의 별을 $n-1$개의 막대로 칸막이하면 각 배치가 하나의 도수 기록과 정확히 일대일로 대응한다. 좋은 전단사 하나가 공식 하나를 만든다는 것, 그것이 이 장 전체의 심상이다.

정의

순열과 $r$-순열

정의. 서로 다른 $n$개의 대상의 순열(permutation)은 그 대상들을 한 줄로 배열한 것이다. $r$개만 골라 배열한 것을 $r$-순열이라 하고, 그 개수를 $P(n,r)$로 쓴다 ($0\le r\le n$).

조합과 이항계수

정의. 서로 다른 $n$개의 대상에서 순서 없이 $r$개를 고른 것(즉 크기 $r$인 부분집합)을 $r$-조합이라 하고, 그 개수를 $C(n,r)=\binom{n}{r}$로 쓴다. 이 수를 이항계수(binomial coefficient)라 한다. $r<0$ 또는 $r>n$이면 $\binom{n}{r}=0$으로 정의한다(조건을 만족하는 부분집합이 없으므로).

중복순열

정의. $n$종류의 대상에서 중복을 허용해 순서 있게 $r$개를 뽑은 것을 중복순열이라 한다. 각 자리마다 $n$가지 선택이 독립이므로 곱의 법칙(셈의 기본 원리)에 의해 그 개수는 $n^r$이다.

같은 것이 있는 순열과 다항계수

정의. 종류 $1,\dots,k$의 대상이 각각 $n_1,\dots,n_k$개 있고 $n_1+\cdots+n_k=n$일 때, 이 $n$개 전체를 일렬로 배열하되 같은 종류끼리는 구별하지 않는 배열의 개수를 다항계수(multinomial coefficient) $\binom{n}{n_1,n_2,\dots,n_k}$로 쓴다.

중복조합

정의. $n$종류의 대상에서 중복을 허용해 순서 없이 $r$개를 뽑은 것을 중복조합($r$-multiset)이라 한다. 이는 각 종류 $i$를 몇 개 뽑았는지의 도수 $x_i\ge0$, $x_1+\cdots+x_n=r$를 지정하는 것과 같다.

주요 정리

정리 1 (순열 공식). $0\le r\le n$일 때 $P(n,r)=n(n-1)(n-2)\cdots(n-r+1)=\dfrac{n!}{(n-r)!}$.

정리 2 (조합 공식과 대칭성). $0\le r\le n$일 때 $\dbinom{n}{r}=\dfrac{n!}{r!\,(n-r)!}$이고, $\dbinom{n}{r}=\dbinom{n}{n-r}$.

정리 3 (같은 것이 있는 순열). $n_1+\cdots+n_k=n$일 때 $\dbinom{n}{n_1,\dots,n_k}=\dfrac{n!}{n_1!\,n_2!\cdots n_k!}$.

정리 4 (중복조합 — 별과 막대). $n$종류에서 중복을 허용해 $r$개를 뽑는 방법의 수는 $\dbinom{n+r-1}{r}$이다. 동치로, 방정식 $x_1+\cdots+x_n=r$의 음이 아닌 정수해의 개수와 같다.

정리 5 (이항정리). 임의의 $x,y$와 음이 아닌 정수 $n$에 대해 $$(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^k y^{n-k}.$$

따름정리로 $x=y=1$을 대입하면 $\sum_{k=0}^n\binom{n}{k}=2^n$ (크기 $n$인 집합의 부분집합 총수), $x=-1,y=1$을 대입하면 $\sum_{k=0}^n(-1)^k\binom{n}{k}=0$ ($n\ge1$; 짝수 크기 부분집합과 홀수 크기 부분집합의 수가 같음)을 얻는다.

정리 6 (파스칼 항등식). $1\le k\le n$일 때 $\dbinom{n+1}{k}=\dbinom{n}{k-1}+\dbinom{n}{k}$.

정리 7 (Vandermonde 항등식). 음이 아닌 정수 $m,n,r$에 대해 $$\binom{m+n}{r}=\sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}.$$

예제

예제 1 (임원 선출 대 위원회 선출). 회원 $10$명 중 회장·부회장·총무를 뽑는 방법은 역할이 구별되므로 순열: $P(10,3)=10\cdot9\cdot8=720$. 동등한 대표 $3$명을 뽑는 방법은 조합: $\binom{10}{3}=720/3!=120$. 같은 세 사람이 뽑히는 결과가 앞에서는 $3!=6$번 세어졌음을 확인할 수 있다.

예제 2 (중복순열). 길이 $8$의 비트열의 개수는 각 자리가 독립적으로 $0$ 또는 $1$이므로 $2^8=256$. 대문자 알파벳 $26$종으로 만드는 길이 $5$의 문자열은 $26^5$가지다 — "뽑은 것을 되돌려 놓는" 선택은 언제나 $n^r$이다.

예제 3 (MISSISSIPPI). 단어 MISSISSIPPI는 M $1$개, I $4$개, S $4$개, P $2$개, 총 $11$글자다. 서로 다른 배열의 수는 정리 3에 의해 $\dfrac{11!}{1!\,4!\,4!\,2!}=34650$이다.

예제 4 (별과 막대의 사용). 방정식 $x_1+x_2+x_3+x_4=17$의 음이 아닌 정수해의 개수는 $n=4$종류에서 $r=17$개를 뽑는 중복조합이므로 $\binom{17+4-1}{17}=\binom{20}{17}=\binom{20}{3}=1140$. 각 $x_i\ge1$을 요구하면 $y_i=x_i-1$로 치환해 $y_1+\cdots+y_4=13$의 음이 아닌 해를 세면 되므로 $\binom{16}{13}=\binom{16}{3}=560$이다.

예제 5 (이항정리로 계수 추출). $(2x-3y)^{25}$의 전개에서 $x^{12}y^{13}$의 계수는, 이항정리에서 $x$ 자리에 $2x$, $y$ 자리에 $-3y$를 넣은 항 $\binom{25}{12}(2x)^{12}(-3y)^{13}$에서 읽어 $\binom{25}{12}\,2^{12}\,(-3)^{13}=-\binom{25}{12}\,2^{12}\,3^{13}$이다.

예제 6 (위원회–위원장 항등식, 조합적 증명 연습). 항등식 $k\binom{n}{k}=n\binom{n-1}{k-1}$을 이중 세기로 증명한다. $n$명 중에서 위원장 $1$명이 지정된 $k$인 위원회를 뽑는 방법의 수를 센다. 위원회를 먼저 뽑고($\binom{n}{k}$) 그중 위원장을 고르면($k$) 좌변, 위원장을 먼저 뽑고($n$) 나머지 위원 $k-1$명을 남은 $n-1$명에서 고르면($\binom{n-1}{k-1}$) 우변이다. 같은 집합을 두 번 세었으므로 두 값이 같다.

흔한 오해와 함정

• "공식을 보고 순열인지 조합인지 판단한다" — 판단 근거는 공식이 아니라 문제 상황이다: 뽑힌 결과에서 순서(역할·자리)가 구별되면 순열, 구별되지 않으면 조합. 예제 1의 두 문제는 같은 숫자 $10,3$을 쓰지만 답이 $6$배 다르다.
• "$r>n$이면 $\binom{n}{r}$는 정의되지 않는다" — $\binom{n}{r}=0$으로 정의되며 이것이 옳은 값이다: $n$원소 집합에는 크기 $r>n$인 부분집합이 없다. 이 규약 덕분에 Vandermonde 항등식 같은 합 공식을 범위 걱정 없이 쓸 수 있다.
• "중복조합은 $\binom{n+r}{r}$ 또는 $\binom{n+r-1}{n}$" — 정확히는 $\binom{n+r-1}{r}=\binom{n+r-1}{n-1}$이다. 기호를 외우지 말고 별 $r$개·막대 $n-1$개, 총 $n+r-1$자리라는 그림에서 매번 복원하는 편이 안전하다.
• "$n!/(n_1!\cdots n_k!)$가 정수인 것은 공식에서 자명하다" — 팩토리얼 나눗셈만 보면 정수성은 전혀 자명하지 않다. 정수인 이유는 이 값이 어떤 유한집합(배열들의 집합)의 크기이기 때문이다 — 조합적 해석이 곧 정수성의 증명이다.
• "조합적 증명은 엄밀한 증명이 아니라 그럴듯한 설명이다" — 이중 세기는 "두 계산이 같은 유한집합의 크기"라는 명제의, 전단사 논법은 "전단사가 존재하면 크기가 같다"(집합과 함수)는 정리의 적용으로, 대수 계산과 동등하게 엄밀하다. 엄밀성의 요건은 분류가 서로소이고 전체를 덮는지, 대응이 실제로 전단사인지를 검증하는 것이다(증명 기법).

큰 그림 / 연결

이 장의 네 공식은 셈의 기본 원리의 곱·합의 법칙이 낳는 첫 결정체이고, 이후의 조합론은 이들을 재료로 쓴다. 포함–배제의 원리은 "적어도 하나의 조건을 어기는" 배치를 이항계수 가중합으로 세며(교란순열이 대표적), 점화식는 파스칼 항등식처럼 큰 문제를 작은 문제로 줄이는 관계식을 체계적으로 푼다. 생성함수에서는 이항정리가 수열 $\binom{n}{0},\binom{n}{1},\dots$의 생성함수 $(1+x)^n$이라는 진술로 재해석되고, 중복조합 $\binom{n+r-1}{r}$는 $1/(1-x)^n$의 계수로 다시 나타난다 — 이 장의 항등식들이 함수 등식의 계수 비교로 일괄 증명되는 광경을 보게 된다. 더 멀리는 그래프와 트리의 구조 세기와 확률적 방법의 기대값 계산이 모두 이항계수 조작을 기본기로 요구한다.

연습문제

1. $8$명의 주자가 있는 경주에서 금·은·동메달이 배정되는 경우의 수와, 상위 $3$명(순위 무관)이 결정되는 경우의 수를 각각 구하라.
2. 단어 ABRACADABRA의 글자를 재배열하는 서로 다른 방법의 수를 구하라.
3. 방정식 $x_1+x_2+x_3=11$의 음이 아닌 정수해의 개수를 구하고, 각 $x_i\ge2$인 해의 개수도 구하라.
4. $\binom{n}{r}=\binom{n}{n-r}$을 팩토리얼 공식을 쓰지 말고 전단사를 명시하여 증명하라.
5. $(x+2)^{10}$의 전개에서 $x^7$의 계수를 구하라.
6. 파스칼 항등식 $\binom{n+1}{k}=\binom{n}{k-1}+\binom{n}{k}$를 팩토리얼 공식으로(대수적으로) 다시 증명하고, 조합적 증명과 비교하라.
7. 항등식 $\sum_{k=0}^{n}k\binom{n}{k}=n\,2^{n-1}$을 이중 세기로 증명하라.
8. $(0,0)$에서 $(m,n)$까지 오른쪽 한 칸 또는 위쪽 한 칸 이동만으로 가는 격자 경로의 수가 $\binom{m+n}{m}$임을 보이고, 이를 이용해 $\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}$을 다시 증명하라.

관련 개념

• 셈의 기본 원리 — 곱·합의 법칙: 이 장의 모든 공식의 출발점
• 포함–배제의 원리 — 이항계수 가중합으로 합집합·교란순열 세기
• 점화식 — 파스칼 항등식을 비롯한 점화식의 일반 해법
• 생성함수 — $(1+x)^n$과 $1/(1-x)^n$: 이 장의 항등식들의 함수적 재해석
• 증명 기법 — 전단사 논법·이중 세기가 기대는 증명의 문법
• 집합과 함수 — 전단사와 집합의 크기