셈 원리(Counting Principle)

Sample space 집합의 수를 세는 방법.

곱의 법칙(Multiplication Rule)

발생 가능한 경우의 수가 $n_{1}, n_{2}, \dots, n_{r} $ 가지인 $1, 2, \dots, r$ 번의 시행에서 발생 가능한 모든 경우의 수는

n_{1} \times n_{2} \times \dots \times n_{r} ​

각 시행은 모두 독립적이며, 그 시행의 순서가 바뀌어도 영향을 미치지 않는다. 이는 곱셈의 교환 법칙과 일맥상통한다.

n개 중의 k를 고르는 것. Combination을 의미한다.

(k n) = {\frac{n !}{( n - k )! k !} 0 otherwise if k > n

순서가 중요하지 않은 k개의 원소를 지닌 부분 집합의 갯수.

곱의 법칙에 의해 $n, n - 1, \dots, n - k + 1$ 명의 순서를 곱하고, 그렇게 나온 부분 집합에서 순서는 중요하지 않으므로 $k!$ (순서를 따지지 않았을 때 중복된 갯수)으로 나눈다.

$(4 10) = (6 10)$ : 10개를 4개 / 6개로 나누는 경우라고 한다면, 10개 중 4개를 택하는 경우와 6개를 택하는 경우는 같을 수 밖에 없다.

다만, $(5 10)$ 라고 한다면, 10개를 5개 / 5개로 나누는 경우라면 그 조합이 중복해서 세어지므로 2로 나누어주어야 경우의 수가 옳게 계산된다.

n개 중에서 k개를 뽑는 표본 추출은, 복원과 순서 여부에 따라 달라진다.

	Ordered	Non-ordered
복원	$n^{k}$	$(k n + k - 1)$
비복원	$_{n} P_{k}$	$(k n)$

$(k n + k - 1)$ : n개의 구분 가능한 상자에 k개의 구분 불가능한 입자를 배열하는 경우의 수와 같다.

$k$ 개의 구분 불가능한 입자의 "위치"와, 그리고 상자는 $n - 1$ 개의 "위치"로 구분되므로 어떤 상자에 놓이는지(상자의 구분선이 어디에 그어지는 지: 어떤 입자를 택하는지), 그리고 몇 번째 위치에 놓이는 지를 합쳐 총 $n + k - 1$ 개의 경우가 생긴다.
이 중 k개의 입자의 위치를 결정하는 것이라 할 수 있다.

$(n - 1 n + k - 1)$ : 이 경우와도 동일하다. 입자의 위치( $k$ )를 고르든, 혹은 상자의 분리선 위치( $n - 1$ )를 고르든 동일하다고 볼 수 있다.

$n \times (k - 1 n - 1) = k \times (k n)$