조합적 증명(Combinatorial proof)

 조합적 증명(combinatorial proof)은 어떤 등식을 대수적 방법(이항, 소거 등등)없이 물체를 세는 방법을 위주로 사용하는 증명을 말한다. 때로 combinatorial argument라고 불리기도 하거나, 아예 조합적 증명이란 말 없이 counting을 잘 하면 된다는 식으로 구체적인 언급 없이 말하기도 한다.

 어떤 등식을 증명할 때 매우 보편적으로 쓰이는 방식으로는 이항이나 소거를 이용하여 0=0꼴로 만드는 대수적방법이 있고 좀 더 고등적인 방법으로는 수학적 귀납법이 있다. 그런데 등식의 좌우변이 특정 셈법과 맞물려 있을 때 쓸 수 있는 또 다른 증명법이 있는데 바로 그것이 조합적 증명이다.

 이 조합적 증명에는 크게 두가지 방법이 있다. 하나는 double counting(이중집계), 다른 하나는 bijective proof(전단사증명)이다. double counting은 어떤 경우의 수를 세는 데 2가지 서로다른 방법이 있음을 밝힌 뒤 각 방법이 하나는 좌변, 다른 하나는 우변을 뜻함을 보이는 방법이고, bijective proof는 좌우변이 서로다른 경우의 수를 뜻하는데 그 경우들끼리 전단사(일대일 완전대응)를 만들어 냄으로서 결국 같다는 것을 보이는 방법이다.

(사실 bijective proof는 큰 범주에서 double counting으로도 볼 수 있는데, 그 이유는 전단사 매칭이 만들어지면 바로 그 매칭을 이용해 새로운 counting 방법을 구성할 수 있기 때문이다.)

 구체적인 예시를 통해 알아보자.

 우선 C(n,r)이 n개의 물체 중 r개를 순서없이 뽑는 경우의 수, 즉 조합(combination)의 수라고 하자.(굳이 따지자면 n과 r은 자연수이고 n은 r보다 크거나 같다고 이야기해야하지만 이후 글에서는 생략한다.) 이 C(n,r)에는 매우 중요한 수학적 성질들이 가득한데 그 중 쉬운 것 몇가지를 조합적 증명을 통해 살펴본다.

1. C(n,r) = C(n,n-r)

 n개 중 r개를 뽑는다는 이야기는 거꾸로 n개중 n-r개를 제외한다는 이야기와 같다. 제외할 것들을 '선택'한다는 관점에서 이는 C(n,n-r)로 표현된다. 

 n=5, r=2로 잡고 구체적인 bijection을 보이면 아래 그림과 같이 된다.

2. Pascal's Identity: C(n,r) = C(n-1,r) + C(n-1,r-1)

 n개 중 r개를 뽑는다는 이야기를 다르게 할 수 있을까? 한 번 특정 물체 A에 주목해보자. r개를 뽑을 때 특정 물체 A가 포함시킬 수도 있고 시키지 않을 수 도 있다. A가 포함되면 남은 일은 (A를 제외한)n-1개 중 (A를 제외한)r-1개를 뽑는 것이다. 이것은 C(n-1,r-1)을 의미한다. A가 포함되지 않으면 남은 일은 (A를 제외한)n-1개 중에서 r개를 뽑는 것이다. 이것은 C(n-1,r)을 의미한다. 두 경우는 배타적이므로 서로 합했을 때 온전히 C(n,r)이 나오게 될 것이다. 

 n=5, r=3로 잡고 구체적인 double Counting을 보이면 아래 그림과 같이 된다.

 위 예시들에서 알 수 있듯이 조합적 증명은 수학적 직관성과 매우 깊은 관련이 있다. 또한 그것이 대수적 방법과 다르게 복잡한 계산을 수반하지 않는다는 점에서 굉장히 우아한 증명으로 이어질 가능성이 높다. 이런 특징들은 모두 퍼즐, 내지는 수학적 유희에서 느껴지는 아름다움과 일맥상통한다. 많은 조합론, 경우의 수 퍼즐에서 이 조합적 증명이 쓰이는 것은 우연이 아닐 것이다.

참고

Discrete Mathemetics and Its Applications, by Kenneth H. Rosen

https://www.cut-the-knot.org/arithmetic/combinatorics/CombinatorialProofs.shtml