[확률과 통계] 2.2 Counting Methods : Part II

- 본 내용은 "Introduction to Probability, Statistics, and Random Processes" 책 내용을 통해 작성 되었고 [인프런] 확률과 통계 기초(조범희) 강의를 참고해서 작성 되었습니다.

---

Unordered 하고 without Replacement (비복원 추출) 인 Sampling 을 우리는 Combination(조합) 이라고한다

Combination의 경우 순서가 없기에 (1,2,3) = (3,2,1) 로 생각한다.

위의 예 처럼 4개의 element 중에 3개의 sample을 draw 할때 아래와 같이 4개의 경우만 나오는걸 알 수 있다.

 

 

Combination을 Permutation을 통해 나타내보면 4P3을 3!로 나눈걸로 생각 할 수있다.

 

 

K- Combinations of n-element set 을 (n, k) 로 나타낼 수 있다.

또한 이는 n! / k!(n-k)! 으로 나타낼 수 도 있다.

 

special한 케이스로 nC0 = 1 이고 permutation과 마찬가지고 k > n 이면 0이다.

 

 

예로 7개의 상자에 3개의 검은 바둑돌을 배치하는 경우 7C3을 통해서 35가지 경우의 수가 있다는 것을 알 수 있다.

이는 잘 생각해보면 4개의 흰색돌을 나머지 공간에 배치하는것과 같다고 생각할 수 있다.

nCk = nCn-k 인데 이는 combinatorial interpretation 이라고 불린다.

 

 

또 다른 예로 2개의 버스가 있고 이를 5명 7명으로 나눠서 타게할 가지수는 12C5 혹은 12C7로 구할 수 있다.

 

이처럼 그룹을 나눌때 Combination을 사용한다.

 

 

위에서 언급했던 Combinatorial Interpretation의 유용한 예이다.

A라는 n개의 원소를 가진 set에서 Subset의 갯수를 구하려고 하면 2^n개가 나오게 된다.

이는 nC0 + nC1 + ... + nCn 이 된다. 

또한 n명 중 대표 한명을 정하고 그를 제외하고 K-1 명을 선택하는 경우의수 n(n-1, k-1) 은 n명중 k명을 뽑ㅂ느데 그 중 대표 한명을 정하는 경우의수 인 k(n,k)와 같음을 알 수 있다.

 

 

이건 조금 어려운 개념인데 n+1개의 set에서 k+1개를 뽑는 경우에 수는 n개에서 k+1을 뽑는것과 n개에서 k개를 뽑는것과 경우의 수 가 같다. 위의 예시를 보면 이해할 수 있다.

 

Vandermonde's idntity는 m+n 개의 set에서 k개를 뽑는 것을

아래의 식으로 바꿔서 쓸수 있다는 방법이다. m개중에 i개를 뽑고 n개중에 k-i개를 뽑은 경우를 i가 0부터 k가 될때까지의 경우를 모두 더해준 것과 같다.

 

binomial theorem 은 (a+b)^n을 전개할때 각 항의 차수를 알 수 있는 정리이다. 여기서 nCk를 binomial coefficient라고 한다.

 

---

이 예제는 Matching Problem이라는 유명한 문제이다. N 명의 사람이 모자를 쓰고 있을때  모든 모자를 모은다음에 다시 분배했을때 적어도 한명이 자신의 모자를 다시 받을 확률에 대해서 묻는 문제이다.

 

이 문제는 inclusion-exclusion principle을 통해서 이해할 수 있다.

위의 식을 따라 계산을 해보면

이러한 결과가 나옴을 알 수 있다. n이 충분히 커지면 1-e-1에 수렴함을 알 수 있다.

 

그룹을 나눠서 3개의 버스에 타야될때도 먼저 2명 8명으로 나누고 8명을 다시 5명 3명으로 나눠서 구하면

10C8 x 8C5로 계산하면 구할 수 있다. 이는 결국 10 C 2,5,3 으로 표현 할 수 있다.

 

이 같은 경우를 muiltimial theorem 이라고 하고 combination한 값은 multimial coefficient 라고 한다.

 

위의 예로 18 명이 주사위를 던질때 각면이 3번씩 동일하게 나올 확률을 볼 수 있다.

sample space는 6^18 이고 주사위의 각 면이 모두 동일하게 3번 나올 확률은 위의 multinomial theorem을 통해 구하면

18 C 3,3,3,3,3,3 이 되어 계산하여 구할 수 있다.

---

 

마지막으로 unordered 하면서 with replacement 인 sampling에 대해서 알아보겟다.

예를 보면 A = {6,7,8} 일때를 2개의 sample을 draw 해야한다.

이는 x1 + x2 + x3 = 2 로 볼 수 있다.

 

 

이 경우에는 n개중 k개를 뽑을때 (k+n-1, k) 로 계산을 하면 나오게 된다.

 

 

n+k-1 C k 는 n+k-1 C n-1 과 같음을 알 수 있고 계산 결과와 직접 5개중에 3개를 뽑앗을때의 수를 비교해보면 일치함을 볼 수 있다.

 

아래의 예제를 풀어보자

5개의 방에 20명이 들어가야된다고 할 때

위와같이 풀수 있다.

event A를 정의해서 각 방에 들어갈 사람의 수를 정해주면 위에서 공부했던 multinomial theorem으로도 풀 수 있다.

 

 

2장 내용 전체를 요약하면 아래와 같다.