알고리즘 기초 연습문제 3장 해설

2. 등식 (3.1)을 기초로 하여 이항계수 문제(알고리즘 3.1)를 ... 증명하시오.

\(\binom{n}{k} = \frac{n!}{k!(n-k)!} \). 여기서 \(n \)은 원소의 총 개수, \(k \)는 선택할 원소의 수이다. 이항계수가 중요하게 다루어지는 첫 번째 이유는 조합의 기초를 형성하기 때문이다. 이는 다양한 문제를 해결하는 데 이용될 수 있으며, 조합적 성질을 연구하는 데 기본적인 도구가 된다. 이항계수를 설명하기 위한 우선 간단한 경우를 생각해볼 수 있다. 주어진 집합 \(S \)에서 \(n \)개의 원소 중 \(k \)개를 임의로 선택하는 행위를 생각해보면, 이 선택의 수는 조합의 개념에 따라 \(\binom{n}{k} \)로 표현된다. 이제 이항계수의 성질을 탐구해보자. \[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]이 등식은 \(n \)개의 원소 중 \(k \)개를 선택하는 방법을 두 가지 경우로 나눌 수 있음을 보여준다. 첫 번째 경우는, 선택한 원소 중 하나가 특정 원소라고 가정하는 경우이다. 이 경우, 나머지 \(k-1 \)개 원소를 \(n-1 \)개 원소에서 선택해야 하므로 \(\binom{n-1}{k-1} \)의 경우가 발생한다. 두 번째 경우는 선택한 원소에 특정 원소가 포함되지 않는 경우로, …