[Algorithm] 이항계수 (Binomial Coefficient)

알고리즘 문제를 풀다 보면 기본적인 수학지식이 많이 필요하다. 그중에 이항계수가 사용되는 경우가 많은 것 같아서 정리해보았다.

Factorial (!)

Factorial of x. The factorial of a natural number x is the product of all positive integers less than and equal to x
특정 수를 주면 1부터 주어진 수까지 모든 수의 곱의 결과값
예: 5! = 5 * 4 * 3 * 2 * 1

nPr (Permutation)

The number of possibilities for choosing an ordered set of r objects (a permutation) from a total of n objects
계산 방법: nPr(n,r) = n! / (n-r)!
순서를 따지는 조합의 수를 계산하는 방법
예: A B C D 중 2개를 선택하는 경우의 수를 계산하면 총 12개임 (4!/2!)
- AB 와 BA는 서로 다른 것으로 판단함
- A가 먼저 나온 경우와 A가 나중에 나오는 등의 순서가 중요함

nCr (Combination)

The number of different, unordered combinations of r objects from a set of n objects
주어진 크기의 (순서 없는) 조합의 가짓수 (출처 1)
순서를 따지지 않는 조합의 수를 계산하는 방법
계산 방법: nCr(n,r) = nPr(n,r) / r! = n! / ((n-r)! * r!)
예: A B C D 중 2개를 선택하는 조합의 수를 계산하면 총 6개임 (4!/(2!*2!))
- AB와 BA가 서로 동일한 조합
nCr(n,r) = nCr(n-1, r) + nCr(n, r-1)
- nCr(n,r)은 r이 선택된 경우의 수와 r이 선택되지 않은 조합의 수와 동일함
- “예를 들어 생각해보면 쉬운데 어떤 반에서 n명의 학생중 r명의 대표를 뽑으려고하는데 이 때의 경우의 수는 특정 학생 x 에 대해 두가지의 케이스로 나누어 생각해 볼 수가있다. 학생 x를 뽑는 경우와 뽑지 않는 경우 이렇게 두 가지의 케이스이다.” (출처 3)

nPr – nCr 예제 정리

모스 부호 사전 문제 (algospot – MORSE): 가능한 Input이 단점(o)와 장점(-)으로 구성되어 있다. 장점이 사전 순으로 앞에 온다. 단점과 장점의 개수가 주어졌을 때 총 조합을 수를 계산하는 문제이다. 이 문제의 경우의 수를 계산할 때는 nCr을 사용해야 한다. 처음에는 nPr을 사용해야 한다고 생각했는데 답안을 찾아보면 nCr을 사용했다. 내 생각에는 단점 또는 장점만 남은 경우 어떠한 순서로 나와도 같기 때문에 nCr을 사용하여 수를 계산한 것 같다.

출처