[Probability] Counting Methods

Counting Methods

확률을 계산하기 위해서는 outcome의 개수를 알 필요가 있다.
(어디까지나 discrete한 공간에서의 이야기이다.)
지금까지의 예제들은 모든 outcome들을 일일이 찾아주는 방법을 취했으나
subexperiment가 여러번 겹친다든지, experiment가 복잡한 경우에는
좀 더 간단한 방법을 사용할 필요가 있다. 이 포스트에서는 그 방법에 대해 설명하려고 한다.
대부분의 내용은 중고등학교 교육과정상에 포함되어 있으므로
앞으로 이어질 포스트에 사용될 대략적인 notation 위주로 보아도 무관할 것이다.

Fundamental Principle of Counting

여러개의 subexperiment가 있고, 각각의 subexperiment들을 모두 수행했을 때,
가능한 outcome의 가지수는 각 subexperiment의 outcome의 곱이다.

이전 포스트의 예제였던 주사위와 동전을 던지는 experiment를 떠올려보면 쉬울 것이다.
주사위를 던졌을 때의 outcome은 6가지, 동전을 던졌을 때의 outcome은 2가지 이므로,
총 12가지의 outcome이 가능하다. Sample space S의 원소가 12개인 것은 그것을 증명해주고 있다.
Counting method의 가장 기본적인 원리다.

Permutation

n개의 서로 다른 object들을 k개만 뽑아서 배열할때의 가능한 가지수는

이다.

굳이 공식을 외우는 것 보다는 직관적으로 생각하면 된다.
바구니가 3개 있고, 각 바구니에 7가지 색깔의 공중 3가지를 택해서 넣는다고 했을 때,
첫번째 바구니에 들어갈 수 있는 공의 가지수는 7가지가 가능하다.
7개 중 하나를 골라 넣으면 6개가 남으므로 그 다음 바구니에는 앞에 뭘 넣었든 6가지 중 하나를 선택해서 넣는다.
세번째 바구니도 마찬가지이므로 결국 7 x 6 x 5 가지가 나오는 셈이다.
이는 7! / (7-3)! = 7! / 4! = 7 x 6 x 5 와 같은 결과다.

Permutation에서는 order, 즉 순서가 중요하다.
다시말해서 빨간색, 노란색, 파란색의 공을 뽑아들었다 하더라도 그 공을 어떤 순서로 배치하느냐에 따라
경우의 수를 모두 다르게 생각하겠다는 의미이다. 

Combination

n개의 서로 다른 object 중에서 k개를 선택하는 경우의 수는

와 같다. 

Permutation에서 order가 상관없게 되어버렸기 때문에,
위 예제에서는 3가지를 뽑아서 나열하는 것이 아니라 그냥 3가지를 뽑는 것 자체를 의미하고,
그 순서는 상관이 없게 되었기 때문에, 3가지를 배치하는 경우의 수, 즉 3! 만큼을 나눠주는 것이다.
보통 이것을 n choose k, 즉 n개중 k개를 고른다고 한다.
식을 잘 살펴보면 k 대신 n-k를 넣어도 동일한 결과가 나온다.
k가 너무 커지는 되는 경우 계산의 편의를 위해서 n-k를 넣어 계산할 수 있다. 

Sampling with Replacement

n개의 서로 다른 object를 k번 뽑아 나열하되,
뽑았은 것을 다시 뽑을 수 있는 경우에 가능한 방법은 n^k 가지이다.

Sampling은 말 그대로 여러가지의 가능성 중에서 하나를 고르는 것이며
replacement는 고른것을 다시 복구시키는 것이다. 즉, 공을 뽑는 행위라면, 그 공을 다시 뽑을 수 있다는 의미다.
이전의 permutation에서 뽑았던 공을 다시 사용할 수 없었다면, 이번엔 뽑았던 공을 다시 사용할 수 있게 되었다면,
각 바구니에는 항상 7가지의 선택권이 주어진다. 따라서 경우의 수는 7^3가지가 된다.
마찬가지로 n개의 outcome을 가진 experiment를 k번 수행하는 경우에도 가능한 방법은 n^k가지이다.

Using Multinomial Coefficient

위와 같은 Sample space를 가진 subexperiment를 n번 반복해 수행한다고 하자.

n이 위와 같이 정의될 때, 어떤 outcome s_i가 n_i번 출현할 경우의 수는 아래와 같다.

(단, 순서가 존재한다.)

이해하기가 쉽지 않은데, 주사위를 예로 들어보자.
주사위를 105번 던진다. 던져서 나온 눈은 차례로 종이에 적는다고 하자.
단, 이때 1의 눈이 5번, 2의 눈이 10번, 3의 눈이 15번, 4의 눈이 20번, 5의 눈이 25번, 6의 눈이 30번 나오도록 한다면,
나올 수 있는 경우의 수는 얼마일까?... 와 같은 문제를 계산하기 위해 위와 같은 식을 사용한다.
이 예에서는 n = 105가 되며 n_0 = 5, n_1 = 10, ... n_5 = 30 이 되는 식이다.
이런 류의 문제에 대해서 permutation이나 combination과 같은 특별한 이름은 없으며
식을 간단히 하기 위해서 multinomial coefficient을 이용해 표기한다.

대부분의 문제들은 위에서 소개한 counting method들을 응용하거나 복잡하게 섞어놓은 형태가 된다.