[02] Permutations, Combinations, and Discrete Probability

Permutation

$$n(n-1)(n-2)...(n-r+1)=\frac{n!}{(n-r)!} = P(n,r)$$

 

#Example

하루에 한과목씩 7일동안 공부하려고 한다. 공부가 필요한 과목은 수학, 화학, 물리, 경제이다. 최소한 7일동안 각 과목을 한번씩 공부할 경우의 수는 얼마인가?

 

A) 한번도 공부하지 않는 경우를 가정해 전체 경우에서 빼주면 된다.

전체의 경우: $4^7$

let $A_1$: 수학 한번도 공부 안하는 경우

$A_2$: 화학 한번도 공부 안하는 경우

$A_3$: 물리 한번도 공부 안하는 경우
$A_4$: 경제 한번도 공부 안하는 경우

그러면 정답은 $4^7 - |A_1 \cup A_2 \cup A_3 \cup A_4|$이다.

 

$|A_1 \cup A_2 \cup A_3 \cup A_4| = |A_1| + |A_2| + |A_3| + |A_4| - |A_1 \cap A_2| -... + |A_1 \cup A_2 \cup A_3|+...-$$|A_1\cap A_2\cap A_3\cap A_4|$ 임으로 각자 계산해서 구하면 된다. 

 

Combinations

$$\frac {P(n,r)} {(q_1!, q_2!, ..., q_t!)}$$

$$\frac {P(n,r)} {r!} = C(n,r)$$

 

#Example

print문은 몇번 실행될까?

 

$C(n+k-1, k)$

 

Catalan Number

$C(2n, n)$이 전체 경우의 수가 된다.

 

대각선 위를 꼭 지나는 경우를 생각해보면, $C(2n, n-1)$과 같다.

 

따라서 $C(2n,n)-C(2n,n-1)$이 된다.

 

Birthday problem

n명의 사람이 있을 때, 최소한 2명의 생일이 같을 확률은?

 

n명이 모두 생일이 다를 확률을 구한다.

$P(\overline{x}) = \frac {P(365,n)}{365!}$

 

따라서 $1-\frac {P(365,n)}{365!}$이 된다.

 

Conditional Probability

$$p(A|B) = \frac {p(A\cap B)} {P(B)}$$

 

Baye's Theorem

Disjoint classes $C_i$가 있고, feature set $F$가 있을 때, 다음의 조건을 만족한다.

$$P(C_j|F) = \frac { P(F|C_j) P(C_j) } { \sum^n_{i=1} P(F|C_i)P(C_i) }$$

 

Monty Hall Problem

#방이 3개인 경우

선택을 바꾸지 않고 승리할 확률 $\frac{1}{3}$

선택을 바꾸고 승리할 확률 $\frac {2}{3}$

 

#방이 4개인 경우

선택을 바꾸지 않고 승리할 확률 $\frac {1} {4}$

선택을 바꾸고 승리할 확률 $\frac{3}{8}$

: $\frac {3}{4}$으로 양을 선택하고 문이 하나 열리면, 남은 두 문중에 한 곳에 차가 있으므로 $\frac{1}{2}$를 곱하면 된다.

 

#방이 5개인 경우

선택을 바꾸지 않고 승리할 확률 $\frac{1}{5}$

선택을 바꾸고 승리할 확률 $\frac{4}{15}$