확률 세기(Counting), 순열(Permutation)과 조합(Combination)

확률 세기(Counting)

결과들(Outcomes)을 세는 것만으로 확률을 구할 수 있다.

1. 표본 공간의 모든 결과가 동일한 확률일 때(All outcomes in $\Omega$ are equally likely)
   $\displaystyle P(A) = \frac{|A|}{|\Omega|}$ (기호: | . | = number(#) of elements in a set(사건 속 원소의 개수))
2. 모든 결과의 확률이 p로 일어난다.
   event A: 유한 개의 모든 사건이 동일하게 일어난다. (finite number of outcomes that are equally likely)

세는 것의 원리(Counting Principle)

• 분할 정복 접근(Divide-and-Conquer approach)
  각 회차 별로 나누어 생각한다. (Counting is broken down into stages)
  

  

  
  일반화(Generalize):
• r stages
• stage i has $n_i$ possible result(=number of outcomes)
  => Total #(number) of outcomes : $n_1n_2...n_r$

그래서 n번의 코인 토스가 $|\Omega| = 2^n$개의 사건인 것.

순열(Permutations)

k-permutations(k개의 순열)

: n개의 것들 중에서 k개 뽑아 '나열'하기. (pick k objects out of n and arrange them in a sequence)

k=n 이면 당연히 n!

Example 1)

클래식 음악 CD : a개
락 음악 CD : b개
컨트리 뮤직 음악 : c개

• 모든 CD를 순서대로 나열한다고 했을 때, 같은 종류의 CD끼리 연속해 있을 경우의 수는?

1. 3종류가 따로 연속해 있으니 클래식, 락, 컨트리를 순서대로 놓는 것과 같다. (3!)
2. 각 종류마다 순서대로 나열할 수 있으니 a! b! c!이 가능하다.
3. 따라서 3! x a! x b! x c! 이다.

조합(Combinations)

: n개 중에서 k를 '순서 없이'(=나열 없이) 뽑기. (Choose k objects out of n "without ordering")

Example 1)

n개 중에서 k개를 뽑는 예시이다.
A, B, C, D(n=4) 중에서 3개 뽑기(k=3)
{A, B, C} = {ABC, ACB, BAC, BCA, CAB, CBA}
{A, B, D} = {ABD, ADB, BAD, BDA, DAB, DBA}
{A, C, D} = {ACD, ADC, CAD, CDA, DAC, DCA}
{B, C, D} = {BCD, BDC, CBD, CDB, DBC, DCB}

왼쪽은 순서가 없이 뽑기만 경우의 수(4개) = Combination
오른쪽은 순서가 있는(나열된) 뽑혀진 경우의 수(16개) = Permutation

쉽게 생각하면, $\frac{4!}{1!}$ 이거까지는 Permutation인데, 뽑은 3개가 순서가 없는게 조합이기에
순서를 지워준다(나누기) 순서는, 3!으로 정할 수 있다.
따라서 식으로는 $\frac{4!}{3!1!}$이 된다.

다항 계수(Multinomial Coefficient)

주어진 개수의 원소들을 주어진 크기에 상자에 넣는 방법의 가짓수.

($n_i$는 $x_i$를 몇개 뽑았는지의 갯수이다)