Chapter - Algorithm wih Math

순열

문제 : 카드 뽑기

[A, B, C, D, E]로 이루어진 5장의 카드가 있다. 이 5장의 카드 중 3장을 선택하여 나열하려고 한다. 순서를 생각하며 3장을 선택했을 때, 카드를 나열하는 방법은 모두 몇 가지가 있을까?

• 첫 번째 숫자를 선택할 수 있는 경우의 수는 5가지.
• 두 번째 숫자를 선택할 수 있는 경우의 수는 4가지.
• 세 번째 숫자를 선택할 수 있는 경우의 수는 3가지.

따라서 5x4x3 = 60가지의 방법이 있다.

이렇게 n개 중에서 일부만을 선택하여 순서를 생각하면서 나열하는 것을 순열이라고 한다. 예를 들어 [A, B, C]와 [A, C, B] 두 경우 모두 A, B그리고 C라는 카드를 선택했지만 나열하는 순서가 다르므로 서로 다른 경우로 생각해야한다.

순열은 일반화 과정을 거쳐서 Permutation의 약자 P로 표현한다.

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

여기서 $n$은 전체의 경우의 수이며 $r$은 순서를 생각하며 선택할 경우의 수가 되겠다.
위의 경우로 이야기 하자면 5장에서 3장을 선택하는 모든 순열의 수는 아래와 같이 표현 되겠다.

$_5P_3=(5*4*3*2*1)/(2*1)=60$

조합

문제 : 카드 뽑기

[A, B, C, D, E]로 이루어진 5장의 카드가 있다. 이 5장의 카드 중 3장을 선택하여 나열하려고 한다. 순서를 생각하지 않고 3장을 선택했을 때, 카드를 나열하는 방법은 모두 몇 가지가 있을까?

위의 문제와 비슷한 문제이지만, 이번엔 순서에 상관없이 카드를 뽑는 문제이다.

• 순열로 구할 수 있는 경우의 수를 찾는다.
• 순열로 구할 수 있는 경우에서 중복된 경우의 수를 나눈다.

조합은 순열과 달리 순서를 고려하지 않는다. 순열에서는 [A, B, C], [A, C, B], [B, A, C], [B, C, A], [C, A, B], [C, B, A]와 같은 경우가 서로 다른 경우로 취급하지만, 조합에서는 이 여섯가지를 하나의 경우로 취급한다.

조합은 Combination의 약자로 C로 표현한다.

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

5장에서 무작위로 선택하는 조합의 경우의 수는 아래와 같이 표현되겠다.

$_5C_3=(5*4*3*2*1)/((3*2*1)(2*1))=10$