순열과 조합

수학에서, 자연수의 계승 또는 팩토리얼(factorial)은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 기호는 느낌표(!)를 쓰며 팩토리얼이라고 읽는다.

$$ n! = \prod_{k=1}^n k = n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 3 \cdot 2 \cdot 1 $$

이는 논리적으로 크기가 n인 집합의 모든 원소를 일렬로 나열하는 경우의 수이기도 하다.

팩토리얼을 처음 접할 때 직관에 어긋나는 부분이 $0!$ 의 값인데, 상식적으로 0을 곱하면 0이 되어야 할 것 같지만, 수학에서는 $0!=1$ 로 정의했다. 이는 다음과 같이 유도할 수 있다.

$$ n! = n \times (n-1)! $$

팩토리얼은 위 점화식을 항상 만족해야 하는데, 양변을 n으로 나눠보자.

$$ (n-1)! = \frac{n!}{n} $$

이 식은 n=1일 때도 참이어야 한다.

$$ (1-1)! = \frac{1!}{1} $$

$$ 0! = \frac{1}{1} = 1 $$

‘0개의 대상을 나열하는 경우의 수’는 몇일까. 아무것도 없는 빈 상태를 그대로 두는것, 그 자체로 1가지의 유효한 경우로 취급하는데, 이는 부분집합의 개수를 셀 때 공집합(원소가 0개인 집합)도 1개의 집합으로 세는 것과 같은 논리이다.

순열

permutation

순열은 서로 다른 n개의 대상중에서 $r$ 개( $0 \le r \le n$ )를 선택하여 순서를 고려하여 일렬로 나열하는 경우의 수를 의미한다. 기호로는 기호 $\mathrm{P}$ 를 사용하여 $_{n}\mathrm{P}_{r}$ (또는 $P(n, r)$ )로 표기한다. $r=n$ 인 경우에 이는 팩토리얼과 같으며, 보통 순열은 $n$ 개 중 $r$ 개만 뽑아서 나열한다.
서로 다른 $n$ 개의 원소 중 $r$ 개를 나열하기 위해 $r$ 개의 빈자리가 있다고 가정해보자. 이때 첫 번째 자리는 $n$ 개의 원소 중 하나를 선택할 수 있으므로 경우의 수는 $n$ 이다. 두 번째 자리엔 첫 번째 자리에서 선택한 1개를 제외한 $n-1$ 개 중 하나를 선택할 수 있다. 세 번째 자리엔 앞서 선택한 2개를 제외한 $n-2$ 개 중 하나를 선택할 수 있다. 이 과정을 계속하면 $r$ 번째 자리는 앞서 선택한 $r-1$ 개를 제외해야 하므로, $n-(r-1)$ 개의 선택지가 남는다.

$$ _{n}\mathrm{P}_{r} = n \times (n-1) \times (n-2) \times \dots \times (n-r+1) $$

이를 팩토리얼로 표현하면 다음과 같다.

$$ _{n}\mathrm{P}_{r} = \frac{n \times (n-1) \times \dots \times (n-r+1) \times (n-r) \times (n-r-1) \times \dots \times 2 \times 1}{(n-r) \times (n-r-1) \times \dots \times 2 \times 1} $$

$$ _{n}\mathrm{P}_{r} = \frac{n!}{(n-r)!} $$

쉬운 예시로, 집합 $A = \set{1, 2, 3, 4, 5}$ 의 5개 원소 중 3개를 골라 순서대로 나열하여 세 자리 숫자를 만드는 경우의 수를 생각해보자.

$n = 5$ (전체 원소의 수)
$r = 3$ (선택할 원소의 수)
첫 번째 자리에는 5개, 두 번째 자리에는 4개, 세 번째 자리에는 3개가 올 수 있으므로 전체 경우의 수는 다음과 같다.

$$ 5 \times 4 \times 3 = 60 $$

이를 순열로 표기하면 다음과 같다.

$$ _{5}\mathrm{P}_{3} = \frac{5!}{(5-3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{2 \times 1} = 5 \times 4 \times 3 = 60 $$

순열은 ‘순서’가 결과에 영향을 미치는 경우(예: $\set{1, 2}$ 와 $\set{2, 1}$ 을 다른 것으로 취급)에 사용된다. 이어서 순서를 고려하지 않고 ‘선택’하는 것에 초점을 둔 조합에 대해 알아보자.

조합

combination

조합은 유한 개의 원소에서 주어진 수만큼의 원소들을 고르는 방법이다. 조합의 수는 이항 계수로 주어진다. 서로 다른 n개의 대상 중에서 순서를 고려하지 않고 $r$ 개( $0 \le r \le n$ )를 선택하는 경우의 수이다.
기호로는 영어 Combination의 첫 글자를 따서 $_{n}\mathrm{C}_{r}$ 로 표기하며, $\binom{n}{r}$ 형태로도사용된다.

앞에 순열에서, 미리 $n$ 개 중에서 $r$ 개를 선택해 두었다고 가정했을때, 이 선택된 $r$ 개의 원소들을 일렬로 나열하는 경우의 수는 앞서 다룬 팩토리얼의 정의에 따라 $r!$ 이다.
즉, 합의 관점에서 뽑힌 ‘하나의 집합’은 순열의 관점에서는 $r!$ 개의 서로 다른 배열로 흩어져 존재한다. 따라서 순열의 총 경우의 수 $_{n}\mathrm{P}_{r}$ 안에는 동일한 원소 구성이 정확히 $r!$ 번씩 중복되어있다.
이 중복을 제거하기 위해 순열의 총 경우의 수를 $r!$ 로 나누어주면 조합이 유도된다.

$$ _{n}\mathrm{C}_{r} = \frac{_{n}\mathrm{P}_{r}}{r!} $$

$$ _{n}\mathrm{C}_{r} = \frac{n!}{r!(n-r)!} $$

같은 상황을 생각해보자. 집합 $A = \set{1, 2, 3, 4, 5}$ 에서 3개의 원소를 선택하는 조합 $_{5}\mathrm{C}_{3}$ 을 계산해보자.

$$ _{5}\mathrm{C}_{3} = \frac{5!}{3!(5-3)!} = \frac{5!}{3! \times 2!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (2 \times 1)} = \frac{120}{12} = 10 $$

이 10가지 경우가 무엇을 의미하는지 논리적으로 확인해 보면, $\set{1, 2, 3}$ 과 $\set{3, 2, 1}$ 을 순열에서는 다른 2개의 사건으로 보았지만, 조합에서는 동일한 1개의 집합으로 간주하여 정확히 중복을 배제한 결과이다.

조합은 다음 등식을 만족한다.

$$ _{n}\mathrm{C}_{r} = _{n}\mathrm{C}_{n-r} $$

논리적으로 생각했을 때, $n$ 개의 대상 중에서 내가 취할 $r$ 개를 ‘선택’하는 행위는, 동시에 내가 남겨둘 $(n-r)$ 개를 ‘선택’하는 행위와 동일한 사건이기 때문이다.

$$ _{n}\mathrm{C}_{n-r} = \frac{n!}{(n-r)!(n - (n-r))!} = \frac{n!}{(n-r)!r!} = _{n}\mathrm{C}_{r} $$

경우의 수와 확률의 관계

순열과 조합은 확률이 아니라, 특정 사건이 발생할 수 있는 모든 경우의 수를 빠짐없이, 그리고 중복 없이 논리적으로 세는 것이다. 확률을 다루기 전에 경우의 수를 알아야 하는 이유는 고전적 확률의 정의를 보면 명확하다.

어떤 시행에서 일어날 수 있는 모든 경우의 집합을 표본공간(Sample space) $S$ 라고 하고, 특정 사건을 $A$ 라고 할 때, 사건 $A$ 가 일어날 확률 $P(A)$ 는 다음과 같다.

$$ P(A) = \frac{n(A)}{n(S)} $$

여기서 $n(S)$ 는 일어날 수 있는 전체 경우의 수이고, $n(A)$ 는 사건 $A$ 가 일어나는 경우의 수이다. 이때 분모와 분자에 들어갈 값을 도출해내는 연산이 앞서 다룬 팩토리얼, 순열, 조합이다.

위 등식이 타당하기 위해서는 전제가 하나 필요한데, 표본 공간 $S$ 에 속하는 각각의 개별 근원사건이 일어날 가능성이 모두 같아야 한다는 것이다. 동전을 던졌을 때 앞면과 뒷면이 나올 가능성이 동일하고, 주사위를 던졌을 때 1부터 6까지의 눈이 나올 가능성이 동일해야만 분수 형태의 확률 계산이 성립한다.

“그럼 ‘각 근원사건이 통계적으로 독립적’인가?”
‘각각 개별 근원사건이 일어날 가능성이 모두 같다(등확률성, uniformity)’는 것은 단일 확률 실험에서 표본공간 $S$ 내에 존재하는 각각의 근원사건이 가지는 확률값 자체의 분포를 의미한다.
표본공간 $S$ 가 $n$ 개의 근원사건 $\set{e_1, e_2, \dots, e_n}$ 으로 이루어져 있다면, 등확률성 가정 하에서 수학적 확률은 다음과 같이 정의된다.

$$ P(e_1) = P(e_2) = \dots = P(e_n) = \frac{1}{n} $$

이는 고전적 확률의 정의가 성립하기 위한 전제 조건일 뿐, 사건들 사이의 관계를 설명하는 개념이 아니다.

통계학에서 ‘독립(Independent)’이라는 것은 두 개 이상의 사건 사이의 관계를 정의하는 개념이다. 하나의 사건이 발생하는 것이 다른 사건의 발생 확률에 어떠한 수학적 영향도 주지 않을 때 두 사건을 독립이라고 한다.
사건 $A$ 와 사건 $B$ 가 독립일 경우, 교집합의 확률은 각 사건의 확률의 곱과 같다.

$$ P(A \cap B) = P(A) \times P(B) $$

동일한 표본공간 내 근원사건들이 독립일 수 있는가? 아니다. 구조적으로 이들은 완벽하게 종속되어있다. 이들은 서로 배반사건이다.
근원사건은 더 이상 쪼개질 수 없는 단일 결과이므로, 한 번의 시행에서 두 근원사건이 동시에 일어나는 교집합은 공집합이 된다.

$$ P(e_i \cap e_j) = 0 $$

두 사건이 독립이려면 $P(e_i \cap e_j) = P(e_i) \times P(e_j)$ 가 성립해야 하는데, 확률이 $0$ 이 아닌 두 근원사건의 곱은 절대 $0$ 이 될 수 없으므로 모순이 발생한다.
오히려, 근원사건 $e_i$ 가 발생했다는 사실은 근원사건 $e_j$ 가 발생할 확률을 완전히 $0$ 으로 만들어버리므로, 이 둘은 종속 관계에 있다.

Reference
위키백과