Permutation and Factorial | 순열과 팩토리얼

조합론(Combinatorics)의 중요한 요소 중 하나인 순열(Permutation)은 요소들을 어떻게 나열할 수 있는지를 구하는 것에 집중합니다.

 

예를 들어 월드컵에서 A, B, C 국가가 1~3등을 차지했다는 정보만 알고 있을 때, 가능한 모든 등수를 구해봅시다.

1등	2등	3등
A	B	C
A	C	B
B	A	C
B	C	A
C	A	B
C	B	A

총 가능한 경우의 수는 6개로, 그 가능한 가짓수는 3 * 2 * 1 = 3! 이였습니다.

 

n개의 요소들 중에서 r개의 요소를 나열할 때 (혹은 뽑을 때), 가능한 가짓수인 nPr은 다음과 같습니다.

nPr = n! / (n-r)!

우리의 예시에서 n = 3, r = 3 이였으므로 3P3 = 3! / (3-3)! = 3! / 1 = 3! = 6 이였습니다.

(0 팩토리얼은 1입니다)

 

 

여기서 다 아시겠지만 팩토리얼에 대한 부연 설명을 하겠습니다.

n 팩토리얼은 n!으로 표기하며, 1부터 n까지의 자연수에 대해서 n! = 1 * 2 * ... * (n-1) * n 의 값을 가집니다.

중요한 점은 음수 n에 대해서 n!은 존재하지 않고, 0! = 1 이라는 점 입니다.

 

 

이를 조금 응용하면 (n+k)!과 (n-k)!을 구할 수 있습니다.

(n+k)! = n! * (n+1) * (n+2) * ... * (n+k) 이고,

(n - k)! = n ! / (n-k+1) * (n-k+2) * ... * n 입니다.

 

또한 n!/k!도 구할 수 있겠죠?

When (n > k): n!/k! = (k+1) * (k+2) * ... * n 이고,

When (n < k): n!/k! = 1/(n+1) * (n+2) * ... * k 가 되겠습니다.