[CS109] 1 - Counting

최근 스탠포드 대학교의 확률에 대한 인기 강좌(CS109) 를 인터넷을 통해 공부하고 있다. 기본부터 하나씩 정리해보자.

경우의 수 세기

첫 시작은 카운팅이다. 사건의 경우의 수를 헤아리는 것이다.

 

1. Sum Rule (합의 법칙)

사건 A가 일어나는 경우의 수가 m가지, 사건 B가 일어나는 경우의 수가 n가지 이고, 사건 A와 B가 동시에 일어나는 경우의 수가 없을 때, 사건 A 또는 B가 일어나는 경우의 수는 m + n 가지이다.

위의 법칙을 수식으로 나타내면 다음과 같다.

 

 

2. Product Rule (곱의 법칙)

사건 A가 일어나는 경우의 수가 m가지, 사건 B가 일어나는 경우의 수가 n가지 일이고, 사건 A가 사건 B에 영향을 주지 않을 때, 사건 A와 B가 동시에 일어나는 경우의 수는 m * n 이다.

위의 법칙을 수식으로 나타내면 다음과 같다.

 

 

사건 A가 사건 B에 영향을 미치지 않는 것을 독립(Independent)이라고 하는데, 위에서는 서로 독립이라는 가정이 들어간 것이다. 서로 독립이 아닌 경우는 나중에 조건부 확률에서 상세히 다루게 될 것이다.

 

3. The Inclusion-Exclusion Principle (포함 배제의 원리)

위의 합 및 곱의 원리를 보면 벤 다이어그램 을 그려서 배웠던 집합의 연산과 유사하다는 것을 알 수 있다. A와 B의 교집합이 없는 경우 합의 법칙(Sum Rule)과 동일하다.

 

 

4. The Pigeonhole Principle (비둘기집 원리)

n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다.

 

당연한 소리를 하는 것 같은데, 위의 원리를 일반화해서 표현하면 아래와 같다.

 

양의 정수 m, n에 대해서, m개의 물건을 n개의 바구니에 넣을 때, 적어도 1개의 바구니에는 m/n보다 작지 않은 최소 정수(천장함수) 개수 만큼의 물건을 가지고 있다.

 

여기서 천장함수(Ceiling Function)는 실수 x에 대해 x보다 크거나 같은 최소 정수를 반환하는 함수이다. 바닥함수(Floor Function)는 x보다 작거나 같은 최대 정수를 반환하는 함수이다.