순열과 조합

[순열 - Permutation]

순열은 뽑는 순서를 고려하여 n개의 원소 중에 r개를 뽑아 나열할 수 있는 경우의 수이다.

여기서 '뽑은 순서를 고려'한다는 말은 만약 a, b, c 3개의 원소를 뽑는다고 했을 때 a를 뽑고 b를 뽑고 c를 뽑는 경우와 b를 뽑고 a를 뽑고 c를 뽑는 경우를 각각 다른 경우로 인정한다는 말이다. 즉, {a, b, c} ≠ {b, c, a}이다.

 

순열 공식은 다음과 같이 간단하게 생각해볼 수 있다.

₅P₃ 을 구해보도록 하자. 5개의 원소를 가진 집합 S가 S = {1, 2, 3, 4, 5}라 할 때, 여기서 순서를 고려하여 원소를 3개씩 뽑아보자.

 

가장 처음 수를 뽑을 때는 {1, 2, 3, 4, 5} 중에 하나를 뽑을 수 있다.

두 번째 뽑을 수는 처음 뽑은 수를 제외한 나머지 4개의 수 중 하나를 뽑을 수 있다.

세 번째 뽑을 수는 지금까지 뽑은 두 수를 제외한 나머지 3개의 수 중 하나를 뽑을 수 있다.

 

따라서 모든 경우의 수는 5 x 4 x 3 = 60이 된다.

 

위의 식을 좀 더 자세히 풀어보면 고를 수 있는 원소의 수를 하나씩 줄여가면서  r번 곱하는 것이다.

 

팩토리얼을 사용하여 위의 수식을 표현하면 다음과 같다.

 

따라서 순열을 구하는 공식은 다음과 같다.

 

 

[조합 - Combination]

조합은 뽑은 순서와 상관없이 n개의 원소 중에 r개를 뽑을 수 있는 경우의 수이다.

조합은 뽑는 순서를 고려하지 않기 때문에  a, b, c 3개의 원소를 뽑는다고 했을 때 {a, b, c} = {a, c, b} = {b, a, c} = {b, c, a} = {c, a, b} = {c, b, a}와 같이 동일한 원소로 구성된 경우에는 뽑은 순서에 상관없이 같은 경우라고 본다.

이와 같이 조합은 뽑는 순서를 고려하지 않기 때문에 조합 원소를 구하기 위해 모든 순열 가운데 중복되는 조합원소들 중 하나만 남기고 제거하는 과정이 필요하다.

 

S = {1, 2, 3, 4, 5}에서 순서를 고려하지 않고 3개를 뽑는 경우의 수 ₅C₃을 구하기 위해 우선 ₅P₃의 모든 경우를 나열하면 다음과 같다.

₅P₃ = {

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1},

{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1},

{1, 2, 5}, {1, 5, 2}, {2, 1, 5}, {2, 5, 1}, {5, 1, 2}, {5, 2, 1},

{1, 3, 4}, {1, 4, 3}, {3, 1, 4}, {3, 4, 1}, {4, 1, 3}, {4, 3, 1},

{1, 3, 5}, {1, 5, 3}, {3, 1, 5}, {3, 5, 1}, {5, 1, 3}, {5, 3, 1},

{1, 4, 5}, {1, 5, 4}, {4, 1, 5}, {4, 5, 1}, {5, 1, 4}, {5, 4, 1},

{2, 3, 4}, {2, 4, 3}, {3, 2, 4}, {3, 4, 2}, {4, 2, 3}, {4, 3, 2},

{2, 3, 5}, {2, 5, 3}, {3, 2, 5}, {3, 5, 2}, {5, 2, 3}, {5, 3, 2},

{2, 4, 5}, {2, 5, 4}, {4, 2, 5}, {4, 5, 2}, {5, 2, 4}, {5, 4, 2},

{3, 4, 5}, {3, 5, 4}, {4, 3, 5}, {4, 5, 3}, {5, 3, 4}, {5, 4, 3}

} = 60개

 

여기서 순서만 다르고 구성원소는 같은 경우를 모두 제거해보자.

₅P₃ = {

{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}, => {1, 2, 3}과 동일한 6개의 원소 중 5개를 제거

{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2}, {4, 2, 1}  => {1, 2, 4}와 동일한 6개의 원소 중 5개를 제거

{1, 2, 5}, {1, 5, 2}, {2, 1, 5}, {2, 5, 1}, {5, 1, 2}, {5, 2, 1}, => {1, 2, 5}와 동일한 6개의 원소 중 5개를 제거

{1, 3, 4}, {1, 4, 3}, {3, 1, 4}, {3, 4, 1}, {4, 1, 3}, {4, 3, 1}, => {1, 3, 4}와 동일한 6개의 원소 중 5개를 제거

{1, 3, 5}, {1, 5, 3}, {3, 1, 5}, {3, 5, 1}, {5, 1, 3}, {5, 3, 1}, => {1, 3, 5}와 동일한 6개의 원소 중 5개를 제거

{1, 4, 5}, {1, 5, 4}, {4, 1, 5}, {4, 5, 1}, {5, 1, 4}, {5, 4, 1}, => {1, 4, 5}와 동일한 6개의 원소 중 5개를 제거

{2, 3, 4}, {2, 4, 3}, {3, 2, 4}, {3, 4, 2}, {4, 2, 3}, {4, 3, 2}, => {2, 3, 4}와 동일한 6개의 원소 중 5개를 제거

{2, 3, 5}, {2, 5, 3}, {3, 2, 5}, {3, 5, 2}, {5, 2, 3}, {5, 3, 2}, => {2, 3, 5}와 동일한 6개의 원소 중 5개를 제거

{2, 4, 5}, {2, 5, 4}, {4, 2, 5}, {4, 5, 2}, {5, 2, 4}, {5, 4, 2}, => {2, 4, 5}와 동일한 6개의 원소 중 5개를 제거

{3, 4, 5}, {3, 5, 4}, {4, 3, 5}, {4, 5, 3}, {5, 3, 4}, {5, 4, 3}  => {3, 4, 5}와 동일한 6개의 원소 중 5개를 제거

}

 

위의 과정을 거친 후 남은 것들이 조합의 원소가 된다.

₅C₃ = {

{1, 2, 3},

{1, 2, 4},

{1, 2, 5},

{1, 3, 4},

{1, 3, 5},

{1, 4, 5},

{2, 3, 4},

{2, 3, 5},

{2, 4, 5},

{3, 4, 5}

} = 10개

 

위의 순열 원소 가운데 중복된 조합 원소를 제거하는 과정을 다시 살펴보면 ₅C₃ 을 구성하는 하나의 조합 원소와 동일한 순열 원소는 ₅P₃에서  6개씩 존재하는 것을 확인할 수 있다. 그렇다면 ₅P₃을 6으로 나누면 ₅C₃의 원소 갯수를 알 수 있다는 말이 된다.

 

이때 나누는 수 6은 어떻게 구할 수 있을까? 이는 3개의 원소 가운데 3개를 뽑는 순열 원소의 갯수( ₃P₃ )라고 볼 수 있다.

 

위의 ₅C₃ 을 도출하는 과정을 식으로 옮기면 다음과 같이 된다.

 

 

이를 일반화 시켜키면 다음과 같다.

 

따라서 n개의 원소 중에 r개를 고르는 조합 nCr의 공식은 다음과 같다.