순열(Permutation)과 조합(Combination)에 대해 이해하기

 

순열(Permutation)

순열이란 어떠한 수들의 집합에서 특정 개수의 숫자를 뽑아 중복 없이 나열한 것을 의미합니다.

1~9까지 수 중에서 3개의 숫자를 뽑아 나열한다고 해봅시다.

첫 번째 숫자가 올 수 있는 경우의 수 1~9 = 9개

두 번째 숫자가 올 수 있는 경우의 수 1~9에서 첫 번째 뽑힌 숫자를 제외한 수 = 8개

세 번째 숫자가 올 수있는 경우의 수 1~9에서 첫 번째, 두 번째 뽑힌 숫자를 제외한 수 = 7개

 

즉, 9개중 3개의 숫자를 뽑아 나열하는 모든 경우의 수는 곱의 법칙을 통해 9 x 8 x 7 이 됩니다.

이를 9P3 이라고 나타냅니다.

 

수 집합에서 특정 개수의 수를 뽑아 나열한 것은 순열이고, 모든 수를 나열하는 것을 팩토리얼(factorial)이라고 합니다.

즉 1~9 까지의 수를 9개 뽑아 나열할 수 있는 모든 경우의 수를 9 팩토리얼, 9! 라고 합니다.

9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 9!

그리고 순열을 팩토리얼로 나타낼 수 있습니다.

9P3을 팩토리얼로 나타낸다고 한다면,

우선 9! , 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 에서 6 x 5 x 4 x 3 x 2 x 1을 나눠서 없애버리면

→ 9 x 8 x 7 = 9P3이 됩니다.

즉, 9P3 = 9! / 6!

 

그래서! n가지 중에서 r개를 뽑아 줄을 나열한다고 했을 때

nPr = n! / (n-r)! 이 됩니다.

조합(Combination)

조합은 순열 안에 포함된 개념입니다.

순열은 특정 개수의 숫자를 뽑아서 나열하는 것이고, 나열하지 않고 뽑기만 한다면 조합입니다.

1~9까지 수 중 3개를 뽑아라(조합)를 9C3으로 표현합니다.

그리고 3개를 뽑고 (9C3) 이를 나열(3!)한다면 순열이 됩니다. 즉, 9C3 x 3! = 9P3이라는 공식이 성립합니다.

이를 이항하면 9C3 = 9P3 / 3! 이 됩니다.

9C3 = 9 x 8 x 7 / 3!

 

즉, n가지 중에서 r개를 뽑아 조합한다고 했을 때

nCr = nPr / r!

= (n! / (n-r)!) / r!

= n! / (n-r)! x r!

라는 식이 성립됩니다.