PROOF 60
증명하라.
nCr = nPr / r!
유한집합 위에서.
한 줄씩, 이유를 따라가 봅시다
먼저 이미 주어진 것과 앞으로 보여야 할 것을 나누어 읽어 보세요. 다음 줄로 넘어갈 때마다 어떤 정의나 앞의 결과를 사용했는지 묻습니다. 연결이 보이지 않으면 결론을 외우기보다 그 전제로 잠시 돌아가도 좋습니다.
정의 D1
원소가 n 개인 집합 X 에서 서로 다른 원소 r 개를 뽑아 순서대로 늘어놓은 것을 나열이라 하고, 나열의 개수를 nPr 이라 한다.
증명.
(1)나열은 (a₁, …, a_r) 이며 a_i ∈ X 이고 i ≠ j 이면 a_i ≠ a_j 다.약속
(2)자리가 다르면 다른 나열이다. 순서는 나열의 일부다.약속
∎
정의 D2
X 의 원소 r 개로 이루어진 부분집합을 조합이라 하고, 그 개수를 nCr 이라 한다.
증명.
부분집합에는 자리가 없다. 원소가 무엇인지만이 부분집합을 정한다.약속
∎
정의 D3
r! 은 r 부터 1 까지의 곱 r(r−1)⋯2·1 을 뜻한다.
증명.
r 은 1 이상의 자연수이며, r! 도 1 이상의 자연수다.약속, N
∎
정의 D4
a ÷ b 는 b × x = a 를 만족하는 x 를 뜻한다.
증명.
그러한 x 가 하나뿐일 때에만 a ÷ b 는 값을 갖는다.약속
∎
보조정리 L1
X 의 r 원소 부분집합 A 를 하나 고정하면, A 의 원소만으로 이루어진 나열은 정확히 r! 개다.
증명.
(1)A 의 원소는 r 개이므로 첫 자리에 올 수 있는 것은 r 가지다.가정, D2
(2)나열의 항은 서로 다르므로, 첫 자리를 정하면 둘째 자리는 남은 r−1 가지다.(1), D1
(3)같은 방식으로 마지막 자리에 남는 것은 1 가지다.(2), D1
(4)각 단계의 가짓수를 곱하면 r(r−1)⋯2·1(1), (2), (3), A1
(5)그 값은 r! 이다.(4), D3
∎
보조정리 L2
길이 r 인 나열 전체는 크기가 모두 r! 인 조각들로 분할되고, 조각의 개수는 nCr 이다.
증명.
(1)나열 p = (a₁, …, a_r) 에 그 항들의 집합 S(p) = {a₁, …, a_r} 을 대응시킨다.약속, D1
(2)항은 서로 다르므로 |S(p)| = r 이고, S(p) 는 X 의 r 원소 부분집합이다.(1), D1, D2
(3)p ~ q 를 S(p) = S(q) 로 정하면 이 관계는 반사·대칭·추이적이다.(1), E
(4)그러므로 나열 전체는 이 관계의 조각들로 분할된다.(3), A4
(5)각 조각은 어떤 r 원소 부분집합 A 에 대하여 {p : S(p) = A} 이다.(2), (4)
(6)그 조각은 A 의 원소만으로 이루어진 나열의 모임이므로 크기가 r! 이다.(5), L1
(7)r! 은 1 이상이므로 모든 r 원소 부분집합 A 에 대하여 그 조각은 비어 있지 않다.(6), D3, N
(8)A ≠ A′ 이면 두 조각은 서로 다르다. 한쪽의 나열은 항의 집합이 A 이고 다른 쪽은 A′ 이기 때문이다.(1), (5)
(9)그러므로 A ↦ {p : S(p) = A} 는 r 원소 부분집합 전체에서 조각 전체로 가는 전단사다.(5), (7), (8)
(10)조각의 개수는 r 원소 부분집합의 개수 nCr 이다.(9), A3, D2
∎
정리 T1
nPr = nCr × r!
증명.
(1)길이 r 인 나열의 개수는 nPr 이다.D1
(2)그 나열 전체는 크기 r! 인 조각 nCr 개로 분할된다.L2
(3)nPr = nCr × r!(1), (2), A2
∎
따름정리 C
nCr = nPr / r!
증명.
(1)nPr = nCr × r!T1
(2)nCr × r! = r! × nCrA6
(3)nPr ÷ r! 은 r! × x = nPr 를 만족하는 x 다.D4
(4)nCr 은 그러한 x 이다.(1), (2), (3)
(5)r! 은 1 이상의 자연수이므로 r! ≠ 0D3, N
(6)r!x = r!y 이면 x = y 이므로 그러한 x 는 하나뿐이다.(5), A5
(7)nCr = nPr / r!(4), (6), D4
(8)곱의 법칙으로 nPr = n(n−1)⋯(n−r+1) 이므로 nCr = n(n−1)⋯(n−r+1) / r!(7), D1, A1
∎
비고
A2 는 이 증명에서 제거할 수 있는가.
r! 로 나누는 일은 이 증명의 마지막 한 걸음이다. 제거하면 그 앞까지 무엇이 남는지 확인하라.