[CS109] 2 - Combinatorics

앞장에서 배웠던 경우의 수 헤아리기(Counting )는 확률의 기본중의 기본이다. 이제 좀 더 구체적인 이론을 배워보자.

 

조합론 (Combinatorics)

순열과 조합에 대해 고등학교에서 배웠을 텐데, 그 기억을 다시 더듬어 보자.

 

1. Permutations (순열, 順列)

서로 다른 n개의 물건을 순서대로 정렬하기

n!은 n factorial (팩토리얼)이라고 읽는다.

 

일반적인 n개의 물건을 순서대로 정렬하기
(n개 중에서 n1, n2, ... nr개가 각각 같거나 구별이 불가능 할 때)

 

예제) MISSISSIPPI라는 단어에 있는 알파벳을 정렬하는 방법은 몇가지인가?

 

풀이) 전체 글자수는 11개이고, M이 1개, I가 4개, S가 4개, P가 2개이므로

 

2. Combinations (조합, 組合)

서로 다른 n개의 물건에서 순서에 상관없이 r개를 뽑기

참고로 영어로 읽을 때는 "n choose r"이라고 한다.

 

3. Bucketing / Group Assignment

r개의 상자에 서로 다른 n개의 물건을 넣기

물건을 순차적으로 1개씩 선택해서 r개의 상자 중에 1개를 선택하여 넣으면 되기 때문에 곱의 법칙을 활용하면 된다.

 

위와 같이 구별이 되는 물건을 버켓팅하는 경우의 수를 헤아리는 것을 쉬우나, 서로 구별이 안되는 경우는 쉽지 않다.

 

r개의 상자에 구별이 안되는 n개의 물건을 넣기

n개의 물건들 사이에 r-1개의 칸막이를 놓는 경우로 생각해 볼 수 있다.
전체 n+r-1개의 물건을 순서대로 배열하는데 n개가 동일하고 r-1개가 동일한 경우이다.

 

예제) 10만불을 4개의 스타트업에 배분하는 방법의 경우 수는? (최소 단위는 1만불)

 

풀이) 최소 단위가 1만불이므로 10개의 물건을 4개의 상자에 배분하는 방법과 같다.