순열, 조합, 중복 순열, 중복 조합 (1/5)

이번 시간에는 "순열, 조합, 중복 순열, 중복 조합"에 대해서 알아보겠습니다.

순열과 조합에 대해서 생각하면 가장 먼저 생각 나는 것이 아마 C(Combination)과 P(Permutation)일 겁니다.

$$_{n}\!C_{r} , _{n}\!P_{r}$$

다만, 이걸 단순히 외웠다면 각 항이 어떤 의미였는지, 또 실생활에 어떻게 적용할지 생각하려면 조금 시간이 걸릴 수 있는데요

이번 포스팅에서 관련 내용들을 정리해보겠습니다.

 

먼저 이 4가지 요소의 공통점은

n개에서 r개를 뽑을 때의 경우의 수

라는 것입니다.

 

여기서 먼저 "경우의 수"를 생각해 봅시다.

"경우의 수"라 함은 말 그대로 "특정 행위를 했을 때 나올 수 있는 경우(Case)의 가지수"입니다

여기서 각각의 경우가 나올 확률은 고려하지 않습니다.

예를 들어, 특정 행위를 했을 때 A라는 경우는 1%로 나오고, B라는 경우는 99%로 나온다 하더라도, 해당 행위를 했을 때는 A 아니면 B가 나오기 때문에 경우의 수는 2입니다.

 

위에서 말하는 특정 행위는 바로 "n개에서 r개를 뽑는다"라는 행위입니다.

예를 들면 "5가지 숫자 카드에서 2개를 뽑는다"라는 행위가 될 수 있습니다.

 

나중에 예제로 많이 나오는 줄 세우기도 사실은 뽑는다는 행위로 치환해서 생각할 수 있습니다.

일단은 복잡하기 때문에 뽑는다라고만 생각해도 좋습니다.

 

다만, n개에서 r개를 뽑을 때 그냥 뽑는 것이 아니라 신경써야 하는 요소 두 가지가 있습니다.

1) 뽑는 과정에서 뽑을 때마다 뽑은 요소를 다시 되돌릴 것이냐 말 것이냐

2) 뽑는 과정에서 어떤 요소를 먼저 뽑았는지를 신경쓸 것이냐 말 것이냐

1번에서 뽑은 요소를 되돌리는 것을 원래대로 복원한다는 의미에서 "복원 추출"이라고 하고, 되돌리지 않는 것을 "비복원 추출"이라고 합니다.

2번에서 "신경을 쓴다"는 말은 경우의 수를 따질 때 누구를 먼저 뽑았는지에 따라 다른 경우로 봐서 경우의 수에 일조한다는 뜻입니다. 반대로 "신경을 쓰지 않는다"는 말은 누구를 먼저 뽑았는지 신경쓰지 않고 같은 경우라고 봐서 경우의 수에 일조하지 않는다는 뜻입니다.

 

이렇게 생각하면 4가지 경우에 대해서 아래 표로 깔끔하게 정리할 수 있습니다.

	어떤 요소를 먼저 뽑았는지 신경씀	어떤 요소를 먼저 뽑았는지 신경 안씀
뽑은 요소를 되돌림	중복 순열 $$_{n}\!\Pi_{r}$$	중복 조합 $$_{n}\!H_{r}$$
뽑은 요소를 되돌리지 않음	순열 $$_{n}\!P_{r}$$	조합 $$_{n}\!C_{r}$$

 

행과 열을 따로 나눠서 생각하면, 뽑은 요소를 되돌리면 "중복"이 붙고, 안 되돌리면 "중복"이 안 붙습니다.

먼저 뽑았는지 신경 쓰면 "순열"이고, 신경 안 쓰면 "조합"입니다.

표를 보시면 각 항에 대해서 수학 기호로도 표현을 했습니다.

 

수학 기호에 문자가 들어가는데 해당 문자가 어떤 의미인지 알아보겠습니다.

1) 순열은 영어로 번역하면 Permutation이기 때문에 P입니다.

2) 조합은 영어로 번역하면 Combination이기 때문에 C입니다.

3) 중복 순열에서 쓰인 문자는 대문자 파이(pi)입니다. 중복 순열의 계산식이 \(n^r\)이라서 곱하는 것 Product의 P로 쓰면 좋지만 이미 순열에서 P를 쓰고 있기 때문에 대신 Pi를 썼다고 합니다.

4) 중복 조합의 H는 Homogeneous의 첫 글자라고 합니다. 이는 동차 다항식(homogeneous polynomials)과 관련이 있습니다.

\((x+y)^2\)의 항의 개수는 \(_{2}\!\Pi_{2}\)

\((x+y+z)^5\)의 항의 개수는 \(_{5}\!\Pi_{3}\)

\((x_{1}+x_{2}+x_{3}+...+x_{r})^n\)의 항의 개수는 \(_{n}\!\Pi_{r}\)

이기 때문이라고 합니다.

 

일단 이번 시간에는 순열, 조합, 중복 순열, 중복 조합에 대해서 전체적으로 알아보았습니다.

각각이 어떤 상황을 의미하는지, 어떻게 계산되는지에 대해서는 다음 포스팅에서 알아보도록 하겠습니다.