이론/ 확률/ 12.1 순열과 조합

12.1 수능 핵심

순열과 조합

Permutations and Combinations

정의 · 공식과 증명

이 절은 «경우의 수를 센다»는 것이 정확히 무엇을 뜻하는지를 집합의 언어로 엄밀하게 정의하는 데서 출발합니다 ― 776번에서 유한집합의 원소의 개수를 8.1 616번의 일대일대응(bijection) 개념으로 정의하고, 바로 뒤 보조정리에서 그 개수가 하나로 정해진다는 것(비둘기집 원리)과 부분집합의 개수를 증명합니다. 777·778번에서 그로부터 합의 법칙과 곱의 법칙(모든 경우의 수 계산의 토대가 되는 두 원리)을 증명하고, 778번 뒤 보조정리에서 «단계마다 선택지의 개수를 곱한다»는 일반형을 증명합니다. 779번은 계승(n!)을 정의하고, 780·781번은 곱의 법칙을 반복 적용해 순열의 수와 조합의 수 공식을 유도합니다 ― 특히 781번에서는, 2.2 lemma-pascal에서 이항정리를 위해 순전히 대수적 기호로만 약속해 두었던 _nC_k가, 실제로 «n개에서 k개를 택하는 경우의 수»와 정확히 일치한다는 것을 처음으로 증명합니다(그때는 이름만 «조합 기호»였을 뿐, 그 이름에 걸맞은 의미는 증명되지 않은 채 남아 있었습니다). 782번은 조합의 대칭성과 파스칼의 규칙을 이번에는 집합을 분류하는 방법으로 다시 증명합니다(2.2의 lemma-pascal은 계승으로 직접 계산하는 대수적 증명이었음 ― 같은 정리의 서로 다른 두 증명). 783–786번은 원순열·같은 것이 있는 순열· 중복순열·중복조합을 차례로 다룹니다.

776정의유한집합의 원소의 개수(Cardinality of a Finite Set)|A|=n :⇔ A와 {1,2,…,n} 사이에 일대일대응이 존재

정의이므로 증명 대상이 아닙니다. 집합 A와 자연수 n(또는 n=0)에 대해, A와 {1,2,…,n}(n=0이면 공집합 ∅) 사이에 8.1 616번의 의미에서 일대일대응(bijection ― 일대일함수이면서 치역이 공역과 같은 함수)이 존재할 때, A를 유한집합 (finite set)이라 하고 이 n을 A의 원소의 개수(cardinality)라 하며 |A|:=n으로 씁니다. 이런 n은 많아야 하나뿐이므로(바로 뒤 보조정리 ②) |A|는 하나로 정해집니다. 12.2에서는 같은 개수를 n(A)로도 씁니다.

직관적으로 «A의 원소 개수가 n이다»는 A의 원소들을 1번, 2번, …, n번으로 중복 없이 빠짐없이 번호 매길 수 있다는 뜻이고, 이 번호 매기기가 바로 {1,…,n}으로 가는 일대일대응 입니다. 이 정의는 «개수를 센다»는 직관적인 행위를 함수(대응)의 언어로 정확하게 옮긴 것으로, 이 절의 모든 정리(777–786번)가 최종적으로 이 정의로 환원됩니다.

사용 : 8.1의 616번(일대일대응의 정의)

·보조정리유한집합의 기본 성질개수는 하나로 정해짐 · B⊆A ⇒ |B|≤|A|

증명법 : 함수의 정의로 직접 확인(①·③), 수학적 귀납법(②·④) ― 777번 이후의 결과는 쓰지 않음

주장. 아래에서 [n]:={1,2,…,n}([0]=∅)으로 씁니다.

f : A→B, g : B→C가 일대일대응이면 g∘f : A→C와 역함수 f⁻¹ : B→A도 일대일대응이다.
(비둘기집 원리) [m]→[n] 일대일함수가 있으면 m≤n이다. 따라서 [m]과 [n] 사이에 일대일대응이 있으면 m=n이다.
A가 유한집합이고 A와 B 사이에 일대일대응이 있으면 B도 유한집합이고 |B|=|A|이다.
A가 유한집합이고 B⊆A이면 B도 유한집합이고 |B|≤|A|이다.

① g∘f가 일대일 : g(f(x))=g(f(x'))이면 g가 일대일이라 f(x)=f(x'), f가 일대일이라 x=x'. 위로 : z∈C이면 g(y)=z인 y∈B, f(x)=y인 x∈A가 있어 g(f(x))=z. 역함수는 f가 일대일대응이라 있고(8.1 627번), 628번의 f⁻¹(f(x))=x에서 모든 x∈A가 f⁻¹의 값(위로), f(f⁻¹(y))=y에서 f⁻¹(y)=f⁻¹(y')이면 y=y'(일대일)입니다.

② n에 대한 귀납법. n=0이면 [n]=∅이라 [m]→∅ 함수는 m=0일 때만 있습니다. n≥1이고 n−1에서 성립한다고 하고, h : [m]→[n]이 일대일이라 합시다. m=0이면 m≤n은 당연하므로 m≥1이라 합니다. n이 h의 값이 아니면 h는 [m]→[n−1] 일대일함수이므로 귀납 가정에서 m≤n−1<n입니다. h(j)=n인 j가 있으면, j와 m의 값을 맞바꾼 함수 h'(j):=h(m), h'(m):=n(나머지는 h와 같음)도 일대일이고, h는 일대일이라 m 말고는 n을 값으로 갖지 않으므로 h'를 [m−1]로 줄이면 [m−1]→[n−1] 일대일함수입니다. 귀납 가정에서 m−1≤n−1, 곧 m≤n입니다. [m]과 [n] 사이에 일대일대응 h가 있으면 h와 h⁻¹(①)에 이를 쓰면 m≤n, n≤m이므로 m=n입니다. 따라서 A가 [m], [n]과 모두 일대일대응이면 ①로 [m]과 [n]도 일대일대응이고 m=n ― 776번의 개수는 하나로 정해집니다.

③ f : A→[n]이 일대일대응이고 g : A→B가 일대일대응이면, ①로 f∘g⁻¹ : B→[n]이 일대일대응입니다.

④ ③로 A=[n]인 경우만 보면 됩니다(A→[n] 일대일대응 f로 B를 f(B)⊆[n]에 옮기면 B와 f(B)는 일대일대응). n에 대한 귀납법. n=0이면 B=∅, |B|=0. n≥1이고 n−1에서 성립한다고 합시다. B⊆[n]에서 n∉B이면 B⊆[n−1]이라 귀납 가정에서 |B|≤n−1<n. n∈B이면 B−{n}⊆[n−1]이라 귀납 가정에서 일대일대응 g : B−{n}→[k](k≤n−1)가 있고, g에 n↦k+1을 덧붙인 함수는 B→[k+1] 일대일대응입니다(n은 B−{n}에 없고 k+1은 [k]에 없음). 따라서 |B|=k+1≤n입니다.

따름. A, B가 유한집합이면 A∩B, A−B(A의 부분집합)는 ④로 유한입니다. 특히 표본공간 S의 부분집합(12.2의 사건)과 여집합 S−A는 모두 유한집합입니다.

사용 : 776번 · 8.1의 616번·625번·627번·628번 · 수학적 귀납법

증명 끝

777정리합의 법칙(Addition Principle)A∩B=∅ ⇒ |A∪B| = |A|+|B|

증명법 : 두 일대일대응을 이어 붙여 새 일대일대응을 만듦

|A|=m, |B|=n이고 A∩B=∅(서로소)라 합시다. 776번에 의해 일대일대응 f : A→{1,…,m}과 g : B→{1,…,n}이 존재합니다. 함수 h : A∪B→{1,…,m+n}을

h(x) := f(x) (x∈A일 때), m+g(x) (x∈B일 때)

로 정의합시다(A∩B=∅이므로 이 정의에 모순이 없습니다 ― 어떤 x도 두 경우에 동시에 해당하지 않음). h가 일대일대응임을 확인합니다 :

일대일(injective) : x≠x'이면, 둘 다 A에 속하면 f가 일대일이므로 h(x)=f(x)≠f(x')=h(x'), 둘 다 B에 속하면 마찬가지로 g가 일대일이므로 h(x)≠h(x'), 하나는 A 하나는 B에 속하면 h(x)≤m<m+1≤h(x')이므로 역시 h(x)≠h(x').
치역=공역 : {1,…,m+n}의 임의의 원소 k에 대해, k≤m이면 f가 일대일대응이므로 f(x)=k인 x∈A가 존재해 h(x)=k, k>m이면 g가 일대일대응이므로 g(x)=k−m인 x∈B가 존재해 h(x)=m+(k−m)=k.

따라서 h : A∪B→{1,…,m+n}은 일대일대응이고, 776번의 정의에 의해 |A∪B|=m+n=|A|+|B|입니다. (m=0이나 n=0이어도 [0]=∅이라 h의 정의와 확인이 그대로 성립합니다.)

따름 ①(k개의 서로소인 집합). 유한집합 A₁,…,A_k(k≥1)가 어느 두 개를 뽑아도 서로소이면 |A₁∪…∪A_k| = |A₁|+…+|A_k|입니다. k에 대한 수학적 귀납법 : k=1은 당연하고, k−1에서 성립하면 A₁∪…∪A_k−1은 유한집합이고 A_k와 서로소(그 합집합의 원소는 어떤 A_i(i<k)에 속해 A_k에 속하지 않음)이므로 위 정리를 두 집합에 쓰면 됩니다.

따름 ②(같은 크기 조각). 유한집합 X가 서로소인 m개의 조각으로 나뉘고 조각마다 원소가 c개이면 |X|=mc입니다 (따름 ①에서 c+c+…+c (m번)). 거꾸로 |X|와 c≥1을 알면 조각의 개수는 m=|X|/c입니다 ― 783·784번의 «나눗셈 논증»이 이것입니다.

따름 ③. A, B가 유한집합이면 A∪B=A∪(B−A)(서로소, 보조정리 따름으로 B−A는 유한)도 유한집합입니다.

참고 : 이 절에서는 항상 유한 개의 집합만 다룹니다. 무한히 많은 집합으로의 확장은 대학 측도론의 영역입니다.

사용 : 776번(유한집합의 원소의 개수) · 보조정리(유한집합의 기본 성질) · 수학적 귀납법

증명 끝

778정리곱의 법칙(Multiplication Principle)|A×B| = |A|×|B|

증명법 : A×B를 |A|개의 서로소인 조각으로 나눈 뒤 777번(합의 법칙)

|A|=m, |B|=n이라 하고 A={a₁,…,a_m}이라 씁시다(776번의 일대일대응 f : A→{1,…,m}으로 A의 원소에 번호를 매긴 것). i=1,…,m에 대해

B_i := {a_i}×B = {(a_i,b) : b∈B}

로 두면, 서로 다른 i에서 B_i들은 쌍의 첫째 성분이 다르므로 서로소이고, A×B = B₁∪…∪B_m입니다(A×B의 모든 원소는 정확히 하나의 i에서 온 (a_i,b) 꼴). 각 B_i는 b↦(a_i,b)라는 대응으로 B와 일대일대응이므로 |B_i|=|B|=n(보조정리 ③)입니다.

777번의 따름 ①(k개의 서로소인 집합)을 B₁,…,B_m(서로소, 각각 크기 n)에 적용하면

|A×B| = |B₁∪…∪B_m| = |B₁|+…+|B_m| = n+n+…+n (m번) = mn = |A|×|B|

를 얻습니다. (m=0이면 A×B=∅이라 0=0×n으로 그대로 성립합니다.)

사용 : 776번(유한집합의 원소의 개수) · 보조정리(유한집합의 기본 성질) · 777번(합의 법칙, 따름 ①) · 1.1의 25번(데카르트 곱)

증명 끝

·보조정리단계별 선택의 곱의 법칙단계마다 선택지가 c_k개 ⇒ 전체 c₁c₂…c_r가지

증명법 : 수학적 귀납법(단계 수에 대한 귀납 + 777번 따름 ②)

778번은 둘째 선택의 후보가 언제나 같은 집합 B인 경우입니다. 그런데 순열(780번)에서는 둘째 자리의 후보가 첫째 자리에서 무엇을 골랐느냐에 따라 다른 집합이 되고, 같은 것은 후보의 개수뿐입니다. 교과서의 곱의 법칙은 이 경우까지 포함하므로, 그 형태를 증명해 둡니다.

주장. X를 길이 r(r≥1)인 나열 (x₁,…,x_r)들의 집합이라 하고, k=1,…,r에 대해 X_k를 X의 원소의 앞 k칸 (x₁,…,x_k)를 모은 집합이라 합시다(X_r=X). 0 이상의 정수 c₁,…,c_r이 있어서 |X₁|=c₁이고, k≥2이면 X_k−1의 어느 원소 q에 대해서도 q 다음 칸에 올 수 있는 것의 집합 C(q):={y : (q,y)∈X_k}가 정확히 c_k개의 원소를 가진다면 (집합 C(q)는 q마다 달라도 됨),

|X| = c₁×c₂×…×c_r

입니다.

증명. |X_k|=c₁…c_k를 k에 대한 귀납법으로 보입니다. k=1은 가정입니다. k−1에서 성립한다고 합시다. X_k의 원소를 앞 k−1칸 q∈X_k−1에 따라 나누면, q에 해당하는 조각은 {(q,y) : y∈C(q)}이고 y↦(q,y)로 C(q)와 일대일대응이므로 크기가 c_k입니다(보조정리 ③). 서로 다른 q의 조각은 앞 k−1칸이 달라 서로소이고, 조각은 모두 |X_k−1|개입니다. 777번 따름 ②(같은 크기 조각)에 의해 |X_k|=|X_k−1|×c_k=c₁…c_k입니다. k=r이 주장입니다.

따름(k개의 곱집합). 유한집합 A₁,…,A_k에 대해 |A₁×…×A_k|=|A₁|×…×|A_k| (나열 (a₁,…,a_k)에서 C(q)가 늘 A_i인 경우).

앞으로 «i번째 단계에서 앞의 선택과 상관없이 늘 c_i가지 중 하나를 고른다»는 말은 이 보조정리의 가정을 뜻합니다.

사용 : 보조정리(유한집합의 기본 성질) · 777번(따름 ②) · 수학적 귀납법

증명 끝

779정의계승(Factorial)0! := 1, n! := n×(n−1)! (n≥1)

정의이므로 증명 대상이 아닙니다. 자연수(0 포함) n에 대해 계승(factorial) n!을 다음과 같이 재귀적으로 정의합니다 :

0! := 1, n! := n×(n−1)! (n≥1)

이를 풀어 쓰면 n≥1일 때 n!=n×(n−1)×…×2×1입니다. 0!:=1은 임의로 정한 것이 아니라 ― 곧 확인할 780·781번의 공식이 n=0이나 r=0, r=n 같은 경계에서도 예외 없이 성립하도록 만드는 자연스러운 약속입니다(2.2 lemma-pascal에서도 이미 이 계승을 «계승의 정의»로 인용해 사용했었습니다 ― 이 절에서 비로소 그 정의를 formal하게 명시합니다).

780정리순열의 수(Number of Permutations)P(n,r) = n!(n−r)! = n(n−1)…(n−r+1)

증명법 : 보조정리(단계별 선택의 곱의 법칙)

서로 다른 n개의 원소를 가진 집합에서 r개(0≤r≤n)를 골라 순서를 구별하여 한 줄로 배열하는 것을 순열(permutation)이라 하고, 그 가짓수를 P(n,r)로 씁니다. 이 배열을 첫째 자리, 둘째 자리, …, r번째 자리를 차례로 채워 나가는 것으로 생각합니다 :

첫째 자리 : n개 중 아무거나―n가지
둘째 자리 : 이미 하나를 썼으므로 남은 n−1개 중―n−1가지
⋮
r번째 자리 : 이미 r−1개를 썼으므로 남은 n−(r−1)개 중―n−r+1가지

곧 순열은 서로 다른 원소로 이루어진 길이 r인 나열이고, k번째 자리의 후보는 «앞 k−1자리에서 아직 쓰지 않은 원소들의 집합»입니다. 이 집합은 앞에서 무엇을 골랐느냐에 따라 달라지지만 개수는 늘 n−(k−1)개이므로, 보조정리(단계별 선택의 곱의 법칙)(c_k=n−k+1)에 의해

P(n,r) = n(n−1)(n−2)…(n−r+1) (r개의 인수)

입니다. 이 식의 분모·분자에 (n−r)!을 곱하고 나누면(779번의 정의에 의해 (n−r)!×(n−r+1)×…×n = n!이므로)

P(n,r) = n(n−1)…(n−r+1) = n(n−1)…(n−r+1)×(n−r)!(n−r)!	(n−r)!/(n−r)!=1을 곱함(1.3의 45번·40번)
= n!(n−r)!	779번(계승의 정의) ― 분자는 n부터 1까지 전부 곱한 것과 같음

를 얻습니다. 특히 r=n이면 P(n,n)=n!/0!=n!(0!:=1의 역할이 바로 여기서 확인됩니다 ― n개 전체를 한 줄로 배열하는 경우의 수가 정확히 n!이 되어야 하므로). r=0이면 빈 나열 하나뿐이라 P(n,0)=1=n!/n!입니다.

사용 : 보조정리(단계별 선택의 곱의 법칙) · 779번(계승의 정의) · 1.3의 40번·45번

증명 끝

781정리조합의 수(Number of Combinations)_nC_r = n!r!(n−r)! = P(n,r)r!

증명법 : 순열을 «고르기»와 «줄 세우기» 두 단계로 분해

서로 다른 n개의 원소를 가진 집합에서 r개(0≤r≤n)를 순서를 구별하지 않고 고르는 것을 조합(combination)이라 하고, 그 가짓수를 이 절에서는 잠시 K(n,r)로 씁니다(2.2의 _nC_k와 같은 것인지는 지금부터 증명할 대상이므로, 미리 그 기호를 쓰지 않습니다).

r개를 순서 있게 배열하는 것(780번의 순열)은 다음 두 단계로 분해할 수 있습니다 :

1단계 : n개 중 어떤 r개를 고를지 결정한다―K(n,r)가지
2단계 : 고른 r개를 한 줄로 배열한다―r개 전체의 순열이므로 780번(r=n인 경우)에 의해 r!가지

정확히 말하면 : r개 순열 전체(P(n,r)개)를 «어떤 r개의 원소로 이루어졌는가»에 따라 나누면, 조각은 고른 r개짜리 부분집합마다 하나씩 K(n,r)개이고 서로소이며, 각 조각은 그 r개를 한 줄로 배열한 것 전체라 크기가 r!(780번 r=n)로 모두 같습니다. 777번 따름 ②(같은 크기 조각)에 의해

P(n,r) = K(n,r) × r!

입니다. r!≠0(자연수의 곱이므로)이므로 양변을 r!로 나누면

K(n,r) = P(n,r)r! = n!/(n−r)!r!	780번(순열의 수 공식)
= n!r!(n−r)!	1.3의 45번(나눗셈의 정의)·43번(곱셈의 결합법칙)

를 얻습니다.

2.2와의 연결. 2.2 lemma-pascal은 이항정리(2.2 79번)의 계수를 다루기 위해 _nC_k := n!/(k!(n−k)!)를 순전히 대수적인 약속으로 도입했을 뿐, 그것이 «조합»이라는 이름에 걸맞게 실제로 무언가를 세는 값인지는 증명하지 않았습니다. 방금 얻은 식은 정확히 그 약속과 같은 형태이므로, 이제 비로소

K(n,r) = n!r!(n−r)! = _nC_r

즉 2.2의 대수적 기호 _nC_r이, n개에서 r개를 순서 없이 고르는 실제 경우의 수와 정확히 일치한다는 것이 증명되었습니다. 이후로는 K(n,r) 대신 _nC_r을 그대로 «조합의 수»라는 뜻으로 씁니다.

사용 : 777번(따름 ②) · 780번(순열의 수) · 1.3의 43번·45번 · 2.2의 lemma-pascal(_nC_k의 대수적 정의)

증명 끝

782정리조합의 성질 ― 대칭성과 파스칼의 규칙_nC_r = _nC_n−r, _nC_r = _n−1C_r−1 + _n−1C_r

증명법 : 대칭성은 여집합 대응, 파스칼의 규칙은 집합의 분류 + 777번(합의 법칙) ― 둘 다 계승을 계산하지 않는 조합적 증명(combinatorial proof)

⑴ 대칭성. 크기 n인 집합 S에서 r개를 고르는 것과, 고르지 않을 n−r개를 고르는 것은 사실 같은 선택입니다 ― «r개를 고른다»와 «나머지 n−r개(여집합)를 고른다» 사이에는

(고른 r개의 부분집합 T) ↔ (그 여집합 S−T, n−r개의 부분집합)

라는 일대일대응이 있습니다(서로 다른 두 개의 r개짜리 선택은 서로 다른 여집합을 주고, 모든 (n−r)개짜리 부분집합은 어떤 r개짜리 선택의 여집합으로 나타남 ― 여집합을 두 번 취하면 원래 집합으로 돌아온다는 사실에서 바로 확인됨). 여집합 S−T는 보조정리 따름으로 유한이고 |S−T|=n−r(777번, S=T∪(S−T) 서로소)이며, 일대일대응이 있으면 개수가 같으므로(보조정리 ③)

_nC_r = _nC_n−r

입니다.

⑵ 파스칼의 규칙(n≥2, 1≤r≤n−1). 크기 n인 집합 S에서 r개를 고르는 모든 방법의 집합을, S의 한 원소 a∈S를 고정하고 «a를 포함하는가»로 둘로 분류합니다(원소는 소문자 a로 써서 집합과 구별) :

a를 포함하는 경우 : a는 이미 뽑힌 것으로 정해졌으므로, 나머지 n−1개(S−{a}) 중에서 r−1개만 더 고르면 됩니다(T↦T−{a}가 일대일대응, 보조정리 ③)―_n−1C_r−1가지
a를 포함하지 않는 경우 : a를 제외한 n−1개 중에서 r개를 모두 골라야 합니다―_n−1C_r가지

n개에서 r개를 택하는 전체 경우를, 특정 원소 a를 포함하는지 여부로 분류하면 두 갈래로 완전히 갈라집니다(겹치지도, 빠뜨리지도 않음).

이 두 경우는 서로소이고(한 선택에서 a를 포함하는 동시에 포함하지 않을 수는 없음), 합쳐서 전체 _nC_r가지를 빠짐없이 덮습니다(임의의 선택은 a를 포함하거나 포함하지 않거나 둘 중 하나이므로). 따라서 777번(합의 법칙)에 의해

_nC_r = _n−1C_r−1 + _n−1C_r

를 얻습니다. 경계 r=0, r=n(n≥1)에서는 2.2 lemma-pascal의 약속(범위 밖의 C는 0)으로 1=0+1, 1=1+0이 바로 확인됩니다.

참고 : 이 등식은 이미 2.2 lemma-pascal에서 계승을 직접 계산해(대수적으로) 증명된 바 있습니다(단, 그때의 기호 _kC_j−1+_kC_j=_k+1C_j는 지금의 n=k+1, r=j로 바꿔 읽으면 완전히 같은 식입니다). 방금 한 증명은 계승을 전혀 계산하지 않고 순수하게 집합을 세는 방법만으로 같은 결론에 도달했다는 점에서 다릅니다 ― 두 증명이 서로를 검산해 주는 관계입니다(순환 논증이 아닙니다 ― 이번 증명은 781번의 조합적 정의에서 곧바로 시작하고, 2.2의 증명은 계승의 대수적 정의에서 시작하므로 서로 독립적입니다).

사용 : 보조정리(유한집합의 기본 성질) · 777번(합의 법칙) · 781번(조합의 수) · 2.2의 lemma-pascal

증명 끝

783정리원순열(Circular Permutations)(n−1)!

증명법 : 일렬 순열을 회전으로 묶어 모둠의 크기를 셈(777번 따름 ②, 나눗셈 논증)

서로 다른 n개(n≥1)를 원형으로 배열하는 것을 원순열이라 합니다. 원순열끼리는(일렬 순열과 달리) «어디가 시작점인가»를 구별하지 않으므로―즉 회전하면 같은 배열로 봅니다. 정확히는 : 일렬 순열 (x₁,…,x_n)을 k칸 회전한 것을 (x_k+1,…,x_n,x₁,…,x_k)(k=0,1,…,n−1)라 하고, 한 순열을 회전해 얻는 n개의 순열을 한 모둠으로 묶을 때, 원순열의 수는 이 모둠의 개수로 정의합니다.

780번에 의해 n개의 일렬 순열은 n!가지입니다. 각 일렬 순열을 원형으로 이어 붙이면 원순열이 하나 얻어지는데, 이 대응은 n대1입니다―같은 원순열이라도 시작점을 어디로 잡느냐에 따라 n가지의 서로 다른 일렬 순열이 나오기 때문입니다(회전 0칸, 1칸, …, n−1칸).

n=4인 예 ― 원형 배열 1개가 회전에 의해 4가지의 서로 다른 일렬 순열과 대응합니다. 일렬 순열 전체(4!=24가지)를 이렇게 4가지씩 묶으면 원순열은 4!/4=(4−1)!=6가지가 됩니다.

보다 정확하게는, «서로 회전으로 얻어지는 일렬 순열끼리»를 같은 모둠으로 묶으면 (동치관계에 의한 분류), 각 모둠은 정확히 n개의 일렬 순열로 이루어져 있습니다 ― k칸 회전(0<k<n)한 순열의 첫 원소는 x_k+1이고 n개가 모두 서로 다르므로 x_k+1≠x₁, 마찬가지로 k≠k'이면 k칸·k'칸 회전은 첫 원소가 달라 서로 다른 순열입니다. 또 회전한 것을 다시 회전하면 회전이고 거꾸로 되돌리는 회전도 있으므로, 두 모둠은 같거나 서로소이며 모둠들은 전체 n!개의 일렬 순열을 빠짐없이 덮습니다. 777번 따름 ②(같은 크기 조각)에 의해 ― 크기가 똑같이 n인 서로소 모둠이 (원순열의 수)개 있고 그 합이 n!이므로 ―

(원순열의 수) × n = n! ⇒ (원순열의 수) = n!n = (n−1)!

를 얻습니다(마지막 등식은 779번의 정의 n!=n×(n−1)!에서 바로 나옵니다).

대학 «n개씩 서로소로 묶이는 모둠이 k개 있으면 전체는 nk개다»라는 이 역방향 논증(나눗셈 논증)은 777번의 합의 법칙을 모든 조각의 크기가 똑같을 때로 특수화한 것이며, 형식적으로는 유한군의 작용에 대한 궤도-안정자군 정리(orbit–stabilizer theorem)의 가장 간단한 경우(안정자군이 자명군인 경우)에 해당합니다. 이 절에서는 이 특수한 경우를 집합을 직접 세는 것으로 충분히 정당화했으므로 더 일반적인 이론은 필요하지 않습니다.

사용 : 777번(따름 ②) · 779번(계승의 정의) · 780번(순열의 수)

증명 끝

784정리같은 것이 있는 순열(Permutations with Indistinguishable Objects)n!p₁!p₂!…p_k! (p₁+…+p_k=n)

증명법 : 원순열(783번)과 같은 나눗셈 논증(777번 따름 ②), 묶음의 크기는 단계별 선택의 곱의 법칙으로 구함

n개의 물건이 k가지 종류로 나뉘고, i번째 종류가 p_i개씩 있다고 합시다 (p₁+p₂+…+p_k=n, 같은 종류끼리는 서로 구별하지 않음). 이 n개를 한 줄로 배열하는 경우의 수를 구합니다.

만약 n개가 전부 서로 다르다면(예를 들어 같은 종류 안에서도 1번, 2번, …로 임시 번호를 매긴다면) 780번(r=n)에 의해 n!가지입니다. 이제 이 임시 번호를 다시 지워, 같은 종류 안에서 번호만 다른 배열들을 하나로 묶습니다.

i번째 종류의 p_i개에 매긴 임시 번호를 서로 뒤바꾸는 방법은(그 종류만 따로 보면) 780번에 의해 p_i!가지이고, 이 재배열은 전체 배열에서 그 종류가 차지하는 자리들만 바꿀 뿐 다른 종류에는 영향을 주지 않습니다. 따라서 하나의 «번호 지운 배열»에 대응하는 «번호 붙인 배열»의 개수는, 종류 1, 2, …, k의 순서로 «그 종류가 차지한 자리들에 임시 번호를 어떻게 매길지»를 차례로 고르는 것이고 i번째 단계는 앞의 선택과 상관없이 늘 p_i!가지이므로, 보조정리(단계별 선택의 곱의 법칙)에 의해

p₁! × p₂! × … × p_k!

로 모든 배열에서 항상 같습니다(783번의 원순열에서 모든 원순열이 정확히 n개의 일렬 순열과 대응했던 것과 완전히 같은 구조 ― 이번에는 그 일정한 개수가 n이 아니라 p₁!p₂!…p_k!일 뿐입니다). 783번과 똑같은 나눗셈 논증(777번 따름 ②)에 의해

(구별 없는 배열의 수) × (p₁!p₂!…p_k!) = n! ⇒ (구별 없는 배열의 수) = n!p₁!p₂!…p_k!

를 얻습니다.

활용 예. «ABBCCC»(A 1개, B 2개, C 3개, 전체 6개)를 한 줄로 배열하는 방법의 수는 6!/(1!2!3!)=72012=60가지입니다.

사용 : 보조정리(단계별 선택의 곱의 법칙) · 777번(따름 ②) · 780번(순열의 수) · 783번(원순열―같은 나눗셈 논증)

증명 끝

785정리중복순열(Permutations with Repetition)_nΠ_r = n^r

증명법 : 보조정리(단계별 선택의 곱의 법칙)의 직접 적용

서로 다른 n개의 원소에서 중복을 허용하여(즉 한 번 뽑은 것을 다시 뽑아도 되도록) r개를 뽑아 한 줄로 배열하는 것을 중복순열이라 하고, 그 가짓수를 _nΠ_r로 씁니다.

이 배열의 각 자리(1번째, 2번째, …, r번째)는 이전에 무엇을 뽑았는지와 무관하게 (중복이 허용되므로 이미 뽑힌 것도 다시 후보) 항상 같은 n개 중 하나를 고르는 선택입니다. 보조정리의 따름(k개의 곱집합, 780번의 증명에서 각 자리마다 후보가 줄어들던 것과 달리, 여기서는 매 자리 후보가 항상 같은 n개로 일정합니다)에 의해 r≥1이면

_nΠ_r = n×n×…×n (r번) = n^r

를 얻습니다. r=0이면 빈 나열 하나뿐이라 _nΠ₀=1=n⁰입니다.

780번과의 비교. 순열의 수 P(n,r)=n(n−1)…(n−r+1)(780번)은 자리마다 후보가 하나씩 줄어드는 경우이고, 중복순열 n^r(785번)은 자리마다 후보가 항상 n개로 그대로인 경우입니다 ― 785번의 증명(곱집합을 그대로 셈)은 780번의 증명(매번 후보가 하나씩 줄어든 집합에서 고름)보다 오히려 더 단순합니다(줄어드는 후보를 추적할 필요가 없음).

사용 : 보조정리(단계별 선택의 곱의 법칙) · 780번(순열의 수, 비교 대상)

증명 끝

786정리중복조합(Combinations with Repetition)_nH_r = _n+r−1C_r

증명법 : «별과 막대(stars and bars)» ― 중복조합과 한 줄 배열 사이의 일대일대응(보조정리 ③)

서로 다른 n가지(n≥1) 종류에서 중복을 허용하여 순서 없이 r개를 뽑는 것을 중복조합이라 하고, 그 가짓수를 _nH_r로 씁니다. 이는 «종류 1을 x₁개, 종류 2를 x₂개, …, 종류 n을 x_n개 뽑는다(x₁+…+x_n=r, 각 x_i≥0인 정수)»는 것과 같은 뜻입니다.

이런 (x₁,…,x_n)을, r개의 별(★)과 n−1개의 막대(|)를 한 줄로 배열하는 것과 다음과 같이 대응시킵니다 : 앞에서부터 x₁개의 별, 막대 하나, x₂개의 별, 막대 하나, …, 막대 하나, x_n개의 별을 순서대로 나열합니다 (막대는 정확히 n−1개 필요―n개의 종류를 나누는 경계가 n−1군데).

n=4가지, r=6개를 뽑는 한 가지 방법(딸기 2, 포도 0, 메론 3, 바나나 1)이 «별 6개 + 막대 3개»의 한 줄 배열 하나와 대응합니다. 포도처럼 0개인 종류는 막대 두 개가 사이에 빈틈 없이 붙어 있는 것으로 나타납니다.

이 대응이 일대일대응임을 확인합니다(그러면 보조정리 ③로 개수가 같음) :

서로 다른 (x₁,…,x_n)은 서로 다른 별·막대 배열을 줍니다 ― 각 x_i의 값이 그대로 그 구간의 별의 개수로 나타나므로, 배열을 보고 원래 (x₁,…,x_n)을 그대로 복원할 수 있습니다(막대 사이사이의 별의 개수를 세면 됨).
모든 별·막대 배열은 어떤 (x₁,…,x_n)에서 나온 것입니다 ― 임의로 별 r개, 막대 n−1개를 배열해도, 막대들 사이(와 양 끝)에 있는 별의 개수를 순서대로 x₁,…,x_n이라 하면 그것이 바로 원래 대응 규칙과 일치합니다.

따라서 중복조합의 개수 _nH_r은 별 r개와 막대 n−1개, 합쳐서 (r+n−1)개의 기호를 한 줄로 배열하는 방법의 수와 같습니다. 이 배열은 (r+n−1)개의 자리 중에서 막대가 들어갈 n−1개의 자리를 고르면(나머지 자리는 자동으로 별) 완전히 결정되므로, 781번(조합의 수)에 의해

_nH_r = _n+r−1C_n−1 = _n+r−1C_r

입니다(마지막 등식은 782번의 대칭성 (n+r−1)−(n−1)=r을 적용한 것).

활용 예. 옆 그림의 예(n=4, r=6)에서 ₄H₆ = ₉C₆ = ₉C₃ = 84가지입니다.

사용 : 보조정리(유한집합의 기본 성질) ③ · 781번(조합의 수) · 782번(조합의 대칭성)

증명 끝

chapter:12-probability section:12.1