12.1 수능 핵심
순열과 조합
Permutations and Combinations
정의 · 공식과 증명
이 절은 «경우의 수를 센다»는 것이 정확히 무엇을 뜻하는지를 집합의 언어로 엄밀하게 정의하는 데서 출발합니다 ― 776번에서 유한집합의 원소의 개수를 8.1 627번의 일대일대응(bijection) 개념으로 정의하고, 777·778번에서 그로부터 합의 법칙과 곱의 법칙(모든 경우의 수 계산의 토대가 되는 두 원리)을 증명합니다. 779번은 계승(n!)을 정의하고, 780·781번은 곱의 법칙을 반복 적용해 순열의 수와 조합의 수 공식을 유도합니다 ― 특히 781번에서는, 2.2 lemma-pascal에서 이항정리를 위해 순전히 대수적 기호로만 약속해 두었던 nCk가, 실제로 «n개에서 k개를 택하는 경우의 수»와 정확히 일치한다는 것을 처음으로 증명합니다(그때는 이름만 «조합 기호»였을 뿐, 그 이름에 걸맞은 의미는 증명되지 않은 채 남아 있었습니다). 782번은 조합의 대칭성과 파스칼의 규칙을 이번에는 집합을 분류하는 방법으로 다시 증명합니다(2.2의 lemma-pascal은 계승으로 직접 계산하는 대수적 증명이었음 ― 같은 정리의 서로 다른 두 증명). 783–786번은 원순열·같은 것이 있는 순열· 중복순열·중복조합을 차례로 다룹니다.
- 일대일(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.
- 첫째 자리 : n개 중 아무거나―n가지
- 둘째 자리 : 이미 하나를 썼으므로 남은 n−1개 중―n−1가지
- ⋮
- r번째 자리 : 이미 r−1개를 썼으므로 남은 n−(r−1)개 중―n−r+1가지
- 1단계 : n개 중 어떤 r개를 고를지 결정한다―K(n,r)가지
- 2단계 : 고른 r개를 한 줄로 배열한다―r개 전체의 순열이므로 780번(r=n인 경우)에 의해 r!가지
- A를 포함하는 경우 : A는 이미 뽑힌 것으로 정해졌으므로, 나머지 n−1개(S−{A}) 중에서 r−1개만 더 고르면 됩니다―n−1Cr−1가지
- A를 포함하지 않는 경우 : A를 제외한 n−1개 중에서 r개를 모두 골라야 합니다―n−1Cr가지
- 서로 다른 (x1,…,xn)은 서로 다른 별·막대 배열을 줍니다 ― 각 xi의 값이 그대로 그 구간의 별의 개수로 나타나므로, 배열을 보고 원래 (x1,…,xn)을 그대로 복원할 수 있습니다(막대 사이사이의 별의 개수를 세면 됨).
- 모든 별·막대 배열은 어떤 (x1,…,xn)에서 나온 것입니다 ― 임의로 별 r개, 막대 n−1개를 배열해도, 막대들 사이(와 양 끝)에 있는 별의 개수를 순서대로 x1,…,xn이라 하면 그것이 바로 원래 대응 규칙과 일치합니다.
776정의유한집합의 원소의 개수(Cardinality of a Finite Set)|A|=n :⇔ A와 {1,2,…,n} 사이에 일대일대응이 존재
정의이므로 증명 대상이 아닙니다. 집합 A와 자연수 n(또는 n=0)에 대해, A와 {1,2,…,n}(n=0이면 공집합 ∅) 사이에 8.1 627번의 의미에서 일대일대응(bijection ― 일대일함수이면서 치역이 공역과 같은 함수)이 존재할 때, A를 유한집합 (finite set)이라 하고 이 n을 A의 원소의 개수(cardinality)라 하며 |A|:=n으로 씁니다.
직관적으로 «A의 원소 개수가 n이다»는 A의 원소들을 1번, 2번, …, n번으로 중복 없이 빠짐없이 번호 매길 수 있다는 뜻이고, 이 번호 매기기가 바로 {1,…,n}으로 가는 일대일대응 입니다. 이 정의는 «개수를 센다»는 직관적인 행위를 함수(대응)의 언어로 정확하게 옮긴 것으로, 이 절의 모든 정리(777–786번)가 최종적으로 이 정의로 환원됩니다.
사용 : 8.1의 627번(일대일대응의 정의)
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가 일대일대응임을 확인합니다 :
따라서 h : A∪B→{1,…,m+n}은 일대일대응이고, 776번의 정의에 의해 |A∪B|=m+n=|A|+|B|입니다.
사용 : 776번(유한집합의 원소의 개수)
증명 끝
778정리곱의 법칙(Multiplication Principle)|A×B| = |A|×|B|
증명법 : A×B를 |A|개의 서로소인 조각으로 나눈 뒤 777번(합의 법칙)
|A|=m, |B|=n이라 하고 A={a1,…,am}이라 씁시다(776번의 일대일대응 f : A→{1,…,m}으로 A의 원소에 번호를 매긴 것). i=1,…,m에 대해
Bi := {ai}×B = {(ai,b) : b∈B}
로 두면, 서로 다른 i에서 Bi들은 쌍의 첫째 성분이 다르므로 서로소이고, A×B = B1∪…∪Bm입니다(A×B의 모든 원소는 정확히 하나의 i에서 온 (ai,b) 꼴). 각 Bi는 b↦(ai,b)라는 대응으로 B와 일대일대응이므로 |Bi|=|B|=n(776번)입니다.
777번의 univ-note에서 확인한 m개 집합에 대한 합의 법칙(수학적 귀납법으로 일반화한 것)을 B1,…,Bm(서로소, 각각 크기 n)에 적용하면
|A×B| = |B1∪…∪Bm| = |B1|+…+|Bm| = n+n+…+n (m번) = mn = |A|×|B|
를 얻습니다.
사용 : 776번(유한집합의 원소의 개수) · 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)
증명법 : 778번(곱의 법칙)을 r번 적용
서로 다른 n개의 원소를 가진 집합에서 r개(0≤r≤n)를 골라 순서를 구별하여 한 줄로 배열하는 것을 순열(permutation)이라 하고, 그 가짓수를 P(n,r)로 씁니다. 이 배열을 첫째 자리, 둘째 자리, …, r번째 자리를 차례로 채워 나가는 것으로 생각합니다 :
각 자리의 선택은 이전 자리에서 무엇을 골랐는지와 무관하게 «아직 쓰지 않은 원소들의 집합»에서 하나를 고르는 독립적인 선택이므로, 778번의 univ-note에서 확인한 일반화된 곱의 법칙(r번의 선택을 곱함)에 의해
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)!을 분모·분자에 곱함(1.3의 45번과 같은 통분 기법) |
| = n!(n−r)! | 779번(계승의 정의) ― 분자는 n부터 1까지 전부 곱한 것과 같음 |
를 얻습니다. 특히 r=n이면 P(n,n)=n!/0!=n!(0!:=1의 역할이 바로 여기서 확인됩니다 ― n개 전체를 한 줄로 배열하는 경우의 수가 정확히 n!이 되어야 하므로).
사용 : 778번(곱의 법칙) · 779번(계승의 정의)
증명 끝
781정리조합의 수(Number of Combinations)nCr = n!r!(n−r)! = P(n,r)r!
증명법 : 순열을 «고르기»와 «줄 세우기» 두 단계로 분해
서로 다른 n개의 원소를 가진 집합에서 r개(0≤r≤n)를 순서를 구별하지 않고 고르는 것을 조합(combination)이라 하고, 그 가짓수를 이 절에서는 잠시 K(n,r)로 씁니다(2.2의 nCk와 같은 것인지는 지금부터 증명할 대상이므로, 미리 그 기호를 쓰지 않습니다).
r개를 순서 있게 배열하는 것(780번의 순열)은 다음 두 단계로 분해할 수 있습니다 :
이 두 단계는 독립적인 선택이므로(무엇을 골랐든 그 r개를 배열하는 방법의 수는 항상 r!로 같음), 778번의 곱의 법칙(일반화된 형태)에 의해
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)! | 분수 나눗셈 정리 |
를 얻습니다.
2.2와의 연결. 2.2 lemma-pascal은 이항정리(2.2 79번)의 계수를 다루기 위해 nCk := n!/(k!(n−k)!)를 순전히 대수적인 약속으로 도입했을 뿐, 그것이 «조합»이라는 이름에 걸맞게 실제로 무언가를 세는 값인지는 증명하지 않았습니다. 방금 얻은 식은 정확히 그 약속과 같은 형태이므로, 이제 비로소
K(n,r) = n!r!(n−r)! = nCr
즉 2.2의 대수적 기호 nCr이, n개에서 r개를 순서 없이 고르는 실제 경우의 수와 정확히 일치한다는 것이 증명되었습니다. 이후로는 K(n,r) 대신 nCr을 그대로 «조합의 수»라는 뜻으로 씁니다.
사용 : 778번(곱의 법칙) · 780번(순열의 수) · 2.2의 lemma-pascal(nCk의 대수적 정의)
증명 끝
782정리조합의 성질 ― 대칭성과 파스칼의 규칙nCr = nCn−r, nCr = n−1Cr−1 + n−1Cr
증명법 : 대칭성은 여집합 대응, 파스칼의 규칙은 집합의 분류 + 777번(합의 법칙) ― 둘 다 계승을 계산하지 않는 조합적 증명(combinatorial proof)
⑴ 대칭성. 크기 n인 집합 S에서 r개를 고르는 것과, 고르지 않을 n−r개를 고르는 것은 사실 같은 선택입니다 ― «r개를 고른다»와 «나머지 n−r개(여집합)를 고른다» 사이에는
(고른 r개의 부분집합) ↔ (그 여집합, n−r개의 부분집합)
라는 일대일대응이 있습니다(서로 다른 두 개의 r개짜리 선택은 서로 다른 여집합을 주고, 모든 (n−r)개짜리 부분집합은 어떤 r개짜리 선택의 여집합으로 나타남 ― 여집합을 두 번 취하면 원래 집합으로 돌아온다는 사실에서 바로 확인됨). 776번(일대일대응이 있으면 개수가 같음)에 의해
nCr = nCn−r
입니다.
⑵ 파스칼의 규칙. 크기 n인 집합 S에서 r개를 고르는 모든 방법의 집합을, S의 한 원소 A∈S를 고정하고 «A를 포함하는가»로 둘로 분류합니다 :
n개에서 r개를 택하는 전체 경우를, 특정 원소 A를 포함하는지 여부로 분류하면 두 갈래로 완전히 갈라집니다(겹치지도, 빠뜨리지도 않음).
이 두 경우는 서로소이고(한 선택에서 A를 포함하는 동시에 포함하지 않을 수는 없음), 합쳐서 전체 nCr가지를 빠짐없이 덮습니다(임의의 선택은 A를 포함하거나 포함하지 않거나 둘 중 하나이므로). 따라서 777번(합의 법칙)에 의해
nCr = n−1Cr−1 + n−1Cr
를 얻습니다.
참고 : 이 등식은 이미 2.2 lemma-pascal에서 계승을 직접 계산해(대수적으로) 증명된 바 있습니다(단, 그때의 기호 kCj−1+kCj=k+1Cj는 지금의 n=k+1, r=j로 바꿔 읽으면 완전히 같은 식입니다). 방금 한 증명은 계승을 전혀 계산하지 않고 순수하게 집합을 세는 방법만으로 같은 결론에 도달했다는 점에서 다릅니다 ― 두 증명이 서로를 검산해 주는 관계입니다(순환 논증이 아닙니다 ― 이번 증명은 781번의 조합적 정의에서 곧바로 시작하고, 2.2의 증명은 계승의 대수적 정의에서 시작하므로 서로 독립적입니다).
사용 : 776번(일대일대응) · 777번(합의 법칙) · 781번(조합의 수) · 2.2의 lemma-pascal
증명 끝
783정리원순열(Circular Permutations)(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가지가 됩니다.
보다 정확하게는, «서로 회전으로 얻어지는 일렬 순열끼리»를 같은 모둠으로 묶으면 (이는 776번의 일대일대응 개념을 확장한 동치관계에 의한 분류입니다―6.1 501번에서 평행이동에 대해 이미 같은 방식의 동치류 분류를 사용한 적이 있습니다), 각 모둠은 정확히 n개의 일렬 순열로 이루어져 있고 (서로 다른 두 시작점에서 얻은 배열이 우연히 같아지려면 원래 배열에 회전 대칭이 있어야 하는데, n개가 모두 서로 다르므로 자명한 회전(0칸)이 아니면 절대 같아질 수 없습니다), 이 모둠들은 서로소이며 전체 n!개의 일렬 순열을 빠짐없이 덮습니다. 777번(합의 법칙)의 역방향으로 ― 크기가 똑같이 n인 서로소 모둠이 (원순열의 수)개 있고 그 합이 n!이므로 ―
(원순열의 수) × n = n! ⇒ (원순열의 수) = n!n = (n−1)!
를 얻습니다(마지막 등식은 779번의 정의 n!=n×(n−1)!에서 바로 나옵니다).
사용 : 777번(합의 법칙) · 779번(계승의 정의) · 780번(순열의 수)
증명 끝
784정리같은 것이 있는 순열(Permutations with Indistinguishable Objects)n!p1!p2!…pk! (p1+…+pk=n)
증명법 : 원순열(783번)과 같은 «n대1 대응» 전략, 이번엔 곱의 법칙으로 묶음의 크기를 구함
n개의 물건이 k가지 종류로 나뉘고, i번째 종류가 pi개씩 있다고 합시다 (p1+p2+…+pk=n, 같은 종류끼리는 서로 구별하지 않음). 이 n개를 한 줄로 배열하는 경우의 수를 구합니다.
만약 n개가 전부 서로 다르다면(예를 들어 같은 종류 안에서도 1번, 2번, …로 임시 번호를 매긴다면) 780번(r=n)에 의해 n!가지입니다. 이제 이 임시 번호를 다시 지워, 같은 종류 안에서 번호만 다른 배열들을 하나로 묶습니다.
i번째 종류의 pi개에 매긴 임시 번호를 서로 뒤바꾸는 방법은(그 종류만 따로 보면) 780번에 의해 pi!가지이고, 이 재배열은 전체 배열에서 그 종류가 차지하는 자리들만 바꿀 뿐 다른 종류에는 영향을 주지 않습니다. 따라서 하나의 «번호 지운 배열»에 대응하는 «번호 붙인 배열»의 개수는, 778번(곱의 법칙, k가지 종류에 대해 독립적으로 재배열)에 의해
p1! × p2! × … × pk!
로 모든 배열에서 항상 같습니다(783번의 원순열에서 모든 원순열이 정확히 n개의 일렬 순열과 대응했던 것과 완전히 같은 구조 ― 이번에는 그 일정한 개수가 n이 아니라 p1!p2!…pk!일 뿐입니다). 783번과 똑같은 나눗셈 논증(합의 법칙의 역)에 의해
(구별 없는 배열의 수) × (p1!p2!…pk!) = n! ⇒ (구별 없는 배열의 수) = n!p1!p2!…pk!
를 얻습니다.
활용 예. «ABBCCC»(A 1개, B 2개, C 3개, 전체 6개)를 한 줄로 배열하는 방법의 수는 6!/(1!2!3!)=720/12=60가지입니다.
사용 : 778번(곱의 법칙) · 780번(순열의 수) · 783번(원순열―같은 나눗셈 논증)
증명 끝
785정리중복순열(Permutations with Repetition)nΠr = nr
증명법 : 778번(곱의 법칙)의 직접 적용
서로 다른 n개의 원소에서 중복을 허용하여(즉 한 번 뽑은 것을 다시 뽑아도 되도록) r개를 뽑아 한 줄로 배열하는 것을 중복순열이라 하고, 그 가짓수를 nΠr로 씁니다.
이 배열의 각 자리(1번째, 2번째, …, r번째)는 이전에 무엇을 뽑았는지와 무관하게 (중복이 허용되므로 이미 뽑힌 것도 다시 후보) 항상 n개 중 하나를 고르는 독립적인 선택입니다. 778번(곱의 법칙의 일반화된 형태 ― 780번의 증명에서 각 자리마다 후보가 줄어들던 것과 달리, 여기서는 매 자리 후보가 항상 n개로 일정합니다)에 의해
nΠr = n×n×…×n (r번) = nr
를 얻습니다.
780번과의 비교. 순열의 수 P(n,r)=n(n−1)…(n−r+1)(780번)은 자리마다 후보가 하나씩 줄어드는 경우이고, 중복순열 nr(785번)은 자리마다 후보가 항상 n개로 그대로인 경우입니다 ― 785번의 증명 방법(778번을 그대로 적용)은 780번의 증명(778번을 매번 후보가 하나씩 줄어든 집합에 적용)보다 오히려 더 단순합니다(줄어드는 후보를 추적할 필요가 없음).
사용 : 778번(곱의 법칙) · 780번(순열의 수, 비교 대상)
증명 끝
786정리중복조합(Combinations with Repetition)nHr = n+r−1Cr
증명법 : «별과 막대(stars and bars)» ― 중복조합과 한 줄 배열 사이의 일대일대응(776번)
서로 다른 n가지 종류에서 중복을 허용하여 순서 없이 r개를 뽑는 것을 중복조합이라 하고, 그 가짓수를 nHr로 씁니다. 이는 «종류 1을 x1개, 종류 2를 x2개, …, 종류 n을 xn개 뽑는다(x1+…+xn=r, 각 xi≥0인 정수)»는 것과 같은 뜻입니다.
이런 (x1,…,xn)을, r개의 별(★)과 n−1개의 막대(|)를 한 줄로 배열하는 것과 다음과 같이 대응시킵니다 : 앞에서부터 x1개의 별, 막대 하나, x2개의 별, 막대 하나, …, 막대 하나, xn개의 별을 순서대로 나열합니다 (막대는 정확히 n−1개 필요―n개의 종류를 나누는 경계가 n−1군데).
n=4가지, r=6개를 뽑는 한 가지 방법(딸기 2, 포도 0, 메론 3, 바나나 1)이 «별 6개 + 막대 3개»의 한 줄 배열 하나와 대응합니다. 포도처럼 0개인 종류는 막대 두 개가 사이에 빈틈 없이 붙어 있는 것으로 나타납니다.
이 대응이 776번의 의미에서 일대일대응임을 확인합니다 :
따라서 중복조합의 개수 nHr은 별 r개와 막대 n−1개, 합쳐서 (r+n−1)개의 기호를 한 줄로 배열하는 방법의 수와 같습니다. 이 배열은 (r+n−1)개의 자리 중에서 막대가 들어갈 n−1개의 자리를 고르면(나머지 자리는 자동으로 별) 완전히 결정되므로, 781번(조합의 수)에 의해
nHr = n+r−1Cn−1 = n+r−1Cr
입니다(마지막 등식은 782번의 대칭성 (n+r−1)−(n−1)=r을 적용한 것).
활용 예. 옆 그림의 예(n=4, r=6)에서 4H6 = 9C6 = 9C3 = 84가지입니다.
사용 : 776번(일대일대응) · 781번(조합의 수) · 782번(조합의 대칭성)
증명 끝