본문 바로가기
Topos Uranos
한국어

기초 조합론과 이항정리

요약

이 수업은 유한집합의 원소를 하나하나 나열하지 않고 세는 기초적인 기법을 다룬다. 유한집합의 원소의 개수를 전단사 함수로 정의하고, 그 정의로부터 합의 법칙과 곱의 법칙을 증명하며, 이로부터 모두 나열하는 순열, 일부를 택하는 순열, 조합의 개수를 이끌어 내고, 이항계수를 정의하여 그 대칭성과 파스칼의 법칙을 세기와 계산 두 가지로 증명한다. 이어서 이 계수들을 파스칼의 삼각형으로 배열하고, 곱셈 공식을 일반화하는 이항정리를 귀납법으로 증명하며, 이를 거듭제곱의 전개, 계수 구하기, 수치 근사에 응용한다. 자연수를 다루는 단원에서 내용을 배우는 마지막 수업이며, 이 단원은 종합과 도전 과제 수업으로 마무리된다.

학습 목표

  1. 합의 법칙과 곱의 법칙을 적용하여 나열하지 않고 세며, 선택의 조건들이 서로 간섭할 때는 경우를 나눈다.
  2. 모두 나열하는 순열, 일부를 택하는 순열, 조합을 구별하고, 계승을 이용하여 그 개수를 계산한다.
  3. 이항계수의 성질을 세기와 계산으로 증명하고, 이를 이용하여 파스칼의 삼각형을 만든다.
  4. 이항정리를 증명하고, 이를 거듭제곱의 전개, 계수의 계산, 거듭제곱의 근사에 응용한다.

세기의 원리

유한집합의 원소를 세는 일은, 그 집합을 원소 하나하나 훑어 갈 수 있는 동안에는 산술에서 가장 기초적인 연산이다. 그러나 원소들이 복합적인 선택을 수행하는 방법일 때, 예를 들어 책 열 권을 책꽂이에 배열하거나 서른 명 가운데서 대표 세 명을 뽑을 때에는 나열이 불가능해지며, 그 개수는 선택을 여러 부분이나 여러 과정으로 나누어 얻는다. 기초 조합론 전체는 두 원리에 기대며, 이 원리들은 “센다”는 것이 무엇을 뜻하는지에 대한 정확한 정의로부터 증명된다.

집합의 원소를 센다는 것은 원소에 번호를 매기는 것, 곧 11부터 nn까지의 각 수에 원소를 하나씩, 중복도 누락도 없이 대응시키는 것이다. 집합 AA가 nn개의 원소를 갖는다(nn은 자연수)는 것은 집합 {1,2,…,n}\{1, 2, \ldots, n\}에서 AA로의 전단사 함수, 곧 서로 다른 수를 서로 다른 원소로 보내고 AA의 모든 원소에 이르는 함수가 존재한다는 뜻이다. 공집합은 00개의 원소를 가지며, 집합이 유한하다는 것은 공집합이거나 nn개의 원소를 갖는다(nn은 어떤 자연수)는 뜻이다. 전단사 함수, 그 합성, 그 역함수는 집합, 관계, 함수에 관한 수업에서 다룬다.

증명 없이 받아들이는 사실 (원소의 개수). 유한집합의 원소의 개수가 잘 정의된다는 것을 증명 없이 받아들인다. 곧, 한 집합이 mm개의 원소와 nn개의 원소를 동시에 가질 수는 없다(단, m≠nm \neq n). 또한 유한집합의 모든 부분집합은 유한하다는 것도 받아들인다.

두 사실은 모두 nn에 대한 귀납법으로 증명된다. 첫째 사실은 본질적으로 비둘기집 원리이며, 이에 따르면 n+1n + 1개의 수({1,…,n+1}\{1, \ldots, n + 1\}의 수)를 {1,…,n}\{1, \ldots, n\}의 서로 다른 수로 보내는 함수는 없다. 그 증명들은 길고 뒤에서 쓰일 아이디어도 주지 않으므로 받아들이기로 한다. 첫째 사실이 없으면 “원소의 개수”라는 표현은 의미가 없을 것이고, 같은 집합을 두 가지 방식으로 세는 조합적 증명은 두 결과가 같다고 결론지을 수 없을 것이다.

명제합의 법칙

AA가 mm개의 원소를 갖고, BB가 nn개의 원소를 가지며, AA와 BB가 공통 원소를 갖지 않으면, A∪BA \cup B는 m+nm + n개의 원소를 갖는다. 그림은 m=3m = 3, n=2n = 2인 경우에 증명을 따라간다.

증명

  1. A={f(1),…,f(m)},B={g(1),…,g(n)}A = \{f(1), \ldots, f(m)\}, \quad B = \{g(1), \ldots, g(n)\}

    가정에 의해, 전단사 함수 ff({1,…,m}\{1, \ldots, m\}에서 AA로의)와 또 하나의 전단사 함수 gg({1,…,n}\{1, \ldots, n\}에서 BB로의)가 있다. 각 집합의 원소는 중복 없이 번호가 매겨져 있다.

  2. i≤m ∨ i=m+j,1≤j≤n\dato{p}{i \leq m \ \vee \ i = m + j, \quad 1 \leq j \leq n}

    삼분법에 의해, 각 수 ii(11부터 m+nm + n까지)는 i≤mi \leq m 또는 i>mi > m을 만족한다. 두 번째 경우에는 순서의 정의에 의해 i=m+ji = m + j인 자연수 jj가 있고, 이는 덧셈의 소거법칙에 의해 유일하며, 덧셈의 단조성에 의해 j≤nj \leq n이다.

  3. h(i)=f(i),h(m+j)=g(j)\dato{h}{h(i) = f(i), \quad h(m + j) = g(j)}

    hh를 {1,…,m+n}\{1, \ldots, m + n\}에서 정의한다. 처음 mm개의 수는 ff와 같이 번호를 매기고, 그 뒤의 nn개의 수는 gg와 같이 번호를 매긴다.

  4. A∩B=∅→f(i)≠g(j)A \cap B = \emptyset \rightarrow \resaltar{f(i) \neq g(j)}

    함수 hh는 서로 다른 수를 서로 다른 원소로 보낸다. 같은 부분에 속하는 두 수는 ff와 gg가 그렇게 하기 때문이고, 서로 다른 부분에 속하는 두 수는 하나는 AA의 원소로, 다른 하나는 BB의 원소로 가며 두 집합은 공통 원소가 없기 때문이다.

  5. A∪B={h(1),…,h(m),h(m+1),…,h(m+n)}A \cup B = \{h(1), \ldots, h(m), h(m + 1), \ldots, h(m + n)\}

    함수 hh는 합집합의 모든 원소에 이른다. AA의 원소는 ff의 값이고, BB의 원소는 gg의 값이다.

  6. h:{1,…,m+n}→A∪Bh : \{1, \ldots, \resaltar{m + n}\} \to A \cup B

    따라서 hh는 {1,…,m+n}\{1, \ldots, m + n\}에서 A∪BA \cup B로의 전단사 함수이고, 합집합은 m+nm + n개의 원소를 갖는다. 두 집합 중 하나가 공집합이면 주장은 자명하다.

부분의 개수에 대한 귀납법으로, 이 원리는 어느 두 집합도 공통 원소를 갖지 않는 임의의 유한 개의 집합으로 확장된다. A1,…,ArA_1, \ldots, A_r의 합집합은, 원소가 각각 n1,…,nrn_1, \ldots, n_r개일 때, n1+⋯+nrn_1 + \cdots + n_r개의 원소를 갖는다. 처음 r+1r + 1개의 합집합은 처음 rr개의 합집합과 마지막 집합의 합집합이고, 마지막 집합은 그것들과 공통 원소를 갖지 않기 때문이다. 이 원리로부터 여러 과정에 걸쳐 이루어지는 선택을 세는 둘째 원리가 나온다.

명제곱의 법칙

어떤 선택이 두 과정으로 이루어지고, 첫째 과정은 mm 가지 방법으로, 둘째 과정은 첫째 과정의 결과와 상관없이 nn 가지 방법으로 이루어지면, 선택 전체는 m⋅nm \cdot n 가지 방법으로 이루어질 수 있다. 그림은 n=4n = 4로 놓고 각 선택 전체를 그 첫째 과정의 행에 놓인 점으로 그린다.

증명

  1. E=E1∪E2∪⋯∪EmE = E_1 \cup E_2 \cup \cdots \cup E_m

    선택 전체를 첫째 과정에 따라 묶는다. mm개의 부류 E1,…,EmE_1, \ldots, E_m에는 공통 원소가 없고, 각 부류는 nn개의 원소, 곧 그 첫째 과정의 선택을 완성하는 nn 가지 방법을 갖는다.

  2. 1⋅n=n1 \cdot n = n

    부류의 개수 mm에 대한 귀납법으로 진행한다. 기초 단계: m=1m = 1이면 모든 선택이 E1E_1에 속하며, 이것은 nn개의 원소를 갖는다.

  3. E1∪⋯∪Ek,k⋅n\dato{h}{E_1 \cup \cdots \cup E_k}, \quad k \cdot n

    귀납 단계: 공통 원소가 없는 kk개의 부류(각각 nn개의 원소를 갖는)의 합집합이 k⋅nk \cdot n개의 원소를 갖는다고 가정한다.

  4. (E1∪⋯∪Ek)∪Ek+1,k⋅n+n(E_1 \cup \cdots \cup E_k) \cup \resaltar{E_{k + 1}}, \quad k \cdot n + \resaltar{n}

    k+1k + 1개의 부류의 합집합은 처음 kk개의 부류의 합집합과 마지막 부류의 합집합이며, 마지막 부류는 그것들과 공통 원소를 갖지 않는다. 합의 법칙에 의해 이 합집합은 k⋅n+nk \cdot n + n개의 원소를 갖는다.

  5. k⋅n+n=(k+1)⋅nk \cdot n + n = \resaltar{(k + 1) \cdot n}

    연산에 관한 수업에서 곱셈의 교환법칙을 증명할 때 보인 보조정리 S(k)⋅n=k⋅n+nS(k) \cdot n = k \cdot n + n에 의해, 이 수는 (k+1)⋅n(k + 1) \cdot n이다.

  6. E1∪⋯∪Em,m⋅nE_1 \cup \cdots \cup E_m, \quad \resaltar{m \cdot n}

    수학적 귀납법의 원리에 의해 mm개의 부류의 합집합은 m⋅nm \cdot n개의 원소를 갖는다. 곧 선택 전체는 m⋅nm \cdot n 가지 방법으로 이루어질 수 있다. 그림에서는 3⋅4=123 \cdot 4 = 12가 성립한다.

마찬가지로, 과정의 개수에 대한 귀납법으로 곱의 법칙은 임의의 유한 개의 과정으로 확장된다. rr개의 과정으로 이루어지고 각 과정이 각각 n1,n2,…,nrn_1, n_2, \ldots, n_r 가지 방법으로 이루어지는 선택은 n1n2⋯nrn_1 n_2 \cdots n_r 가지 방법으로 이루어질 수 있다. 예를 들어 위치적 기수법에 관한 수업에서 다룬 십진법에서 세 자리 수는 9⋅10⋅10=9009 \cdot 10 \cdot 10 = 900개이다. 첫째 자리 숫자는 00이 될 수 없고 나머지 두 자리는 자유롭기 때문이다. 주의할 점은, 곱의 법칙이 요구하는 것은 각 과정의 선택지 개수가 앞에서 고른 것에 의존하지 않는 것이며, 선택지 자체는 의존해도 된다는 것이다. 이 조건이 깨지면 조건이 성립하는 경우들로 나누고 그 결과를 합의 법칙으로 더한다.

선택의 잇따른 과정은 수형도로 나타낸다. 뿌리라 부르는 시작점에서 첫째 과정의 선택지 수만큼 가지가 나오고, 각 가지의 끝에서 둘째 과정의 선택지 수만큼 가지가 나오며, 이렇게 계속된다. 뿌리에서 마지막 끝, 곧 잎까지 가는 각 길이 하나의 선택 전체이며, 곱의 법칙은 잎을 그리지 않고 그 수를 센다.

예시숫자 11, 22, 33으로 만드는 세 자리 수

숫자 11, 22, 33을 반복 없이 써서 만들 수 있는 세 자리 수를 세고, 반복을 허용할 때 얻는 수와 비교하라.

증명

  1. 3\resaltar{3}

    첫째 자리 숫자는 세 숫자 중 어느 것이든 될 수 있다. 뿌리에서 가지 세 개가 나온다.

  2. 3⋅2=63 \cdot \resaltar{2} = \resaltar{6}

    첫째 자리 숫자를 고르면, 그것이 무엇이든 둘째 자리에는 숫자 두 개가 남는다. 각 가지는 둘로 갈라지고, 곱의 법칙에 의해 가능한 시작은 여섯 가지이다.

  3. 3⋅2⋅1=6\dato{p}{3 \cdot 2 \cdot \resaltar{1} = \resaltar{6}}

    셋째 자리에는 한 가지 가능성만 남으므로 각 시작은 단 한 가지 방법으로 완성된다.

  4. 123, 132, 213, 231, 312, 321123, \ 132, \ 213, \ 231, \ 312, \ 321

    뿌리에서부터 읽은 나무의 잎이 구하는 여섯 수이며, 작은 것부터 큰 것 순으로 놓여 있다.

  5. 3⋅3⋅3=27\resaltar{3 \cdot 3 \cdot 3} = \resaltar{27}

    숫자의 반복을 허용하면 각 과정의 선택지가 세 개가 되고, 나무의 잎은 반복이 없을 때보다 훨씬 많아진다.