cornerstone

조합론

조합론은 주어진 원소 집합에서 특정 개수의 원소를 선택하는 경우의 수를 연구하는 기법이다. 순서가 중요하지 않은 경우의 선택을 조합이라 하고, 순서까지 고려하는 경우를 순열이라 한다.

조합의 개수를 계산할 때 이항 계수를 사용한다.
수식은 다음과 같다.

\binom{n}{k} = \frac{n!}{k!(n-k)!}

여기서 n!은 n 팩토리얼을 의미한다. 본 문제에서는 1부터 n까지의 정수 중 5개를 선택하므로 k = 5이고, 후보의 총 개수는 n5가 된다.