The Basic Principle of Counting, Permutation, Combination

The Basic Principle of Counting

The Basic Principle of Counting. If an experiment consisting of two phases is such that there are $n$ possible outcomes of phase 1 and, for each of these $n$ outcomes, there are $m$ possible outcomes of phase 2, then there are $nm$ possible outcomes of the experiment. 

'곱의 법칙'으로 흔히들 배우는 내용이다. 첫 번째에서 $n$개의 케이스가 나오고, 각 케이스에 대해서 두 번째에는 $m$개의 케이스가 존재한다면 총 $nm$개의 케이스가 존재한다는 내용이다. 모든 케이스를 하나씩 카운트해주면 총 $mn$개가 존재하므로 당연히 성립하는 정리다. 일반화도 가능한데, $r$번의 시행에서 각각 $n_i (1 \leq i \leq r)$개의 케이스가 존재한다면 총 경우의 수는 $n_1 \cdots n_r$개이다. 

 

Permutation

Permutation. We define $n!$, for $n > 0$, by $n= n(n-1) \cdot 3 \cdot 2 \cdot 1$ and say that $n!$ (read as "$n$ factorial") represents possible linear orderings of $n$ items. It is convenient to define $0! = 1$.

$n$개의 대상을 일렬로 나열하는 경우의 수는 $n \cdots 2 \cdot 1$개 존재하며, 이를 $n!$로 정의하고 $n$ factorial(팩토리얼)이라고 읽는다. 이때 $n$개의 대상이 모두 다를 필요는 없는데, $n$개 중 중복되는 대상이 존재할 경우 중복되는 대상의 개수만큼 팩토리얼을 취하여 나눠주면 된다. 예컨대 중복되는 대상이 존재하여서 서로 다른 대상이 총 $r$개 존재하면 (즉 $n_1 + \cdots + n_r = n$) 총 경우의 수는 다음과 같다. $$\frac{n!}{n_1! \cdots n_r!}$$ 한국 교육과정에서는 '같은 것이 있는 순열'로 배운다. 

 

Combination

Combination. We define $n \choose r$, for $0 \leq r \leq n$, by $${n \choose r} = \frac{n!}{(n-r)! r!}$$ and say that $n \choose r$ (read as "$n$ choose $r$") represents the number of possible combinations of $n$ objects taken $r$ at a time. It is convenient to define $n \choose r$ equal to $0$ when either $r > n$ or $r < 0$.

$n$개의 대상 중 $r$개를 한 번에 뽑는 경우의 수, 정도로 받아들일 수 있다. 이는 크기가 $n$인 집합에서 크기가 $r$인 부분집합의 개수와도 같다. 

 

Pascal's Identity

Pascal's Identity. $${n \choose r} = {n-1 \choose r-1} + {n-1 \choose r} \text{  where  } 1 \leq r \leq n$$

위 정리가 성립함은 직관적으로도 알 수 있다. $n$개 중 $r$개를 뽑는 경우의 수를 생각할 때, 특정한 원소 하나를 생각하자. 그럼 이 원소를 포함할 때와 포함하지 않을 때로 나눌 수 있고, 이는 각각 $n-1$개에서 $r-1$개를 뽑는 (무조건 특정 원소를 포함하는 경우) 경우의 수와 $n-1$개에서 $r$개를 뽑는 경우의 수에 대응된다. 

 

The Binomial Theorem

The Binomial Theorem. $$(x+y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}$$

위 정리가 성립함은 Combination의 정의상 당연하게 알 수 있다. 형식적인 증명은 induction으로 할 수 있다. 위 정리와 연결지어서 combination을 binomial coefficient (이항 계수) 라고 부르기도 한다.

 

Multinomial Coefficient

Multinomial Coefficient. We define $n \choose n_1, \cdots , n_r$ by $${n \choose n_1, \cdots , n_r} = \frac{n!}{n_1! \cdots n_r!}$$ where $n_1 + \cdots + n_r = n$ and say that $n \choose n_1, \cdots , n_r$ represents the number of possible divisions of $n$ distinct objects into $r$ distinct groups of respective sizes $n_1, \cdots , n_r$.

$n$개 중 $r$개만 뽑는 게 아니라, 다시 말해 크기가 $r$인 1개의 영역으로만 나누는 것이 아니라 각각 크기가 $n_i (1 \leq i \leq r)$인 $r$개의 영역으로 나누는 상황을 생각할 수도 있다. 이 경우의 수의 계산은 combination으로 할 수 있는데, $n$개 중 먼저 $n_1$개를 뽑고 다음으로 $n-n_1$개 중 $n_2$개를 뽑고, 이런 식으로 $n_r$개까지 모두 뽑는 경우의 수를 전부 곱하면 위 정의와 같이 계산됨을 알 수 있다. Binomial coefficient와 같은 방식으로 위 수를 multinomial coefficient (다항 계수) 라고 부르며, 마찬가지로 multinomial theorem이 성립함을 알 수 있다.

 

The Multinomial Theorem

The Multinomial Theorem. $$(x_1 + \cdots + x_r)^n = \sum_{n_1, ..., n_r \\ n_1 + \cdots + n_r = n} {n \choose n_1, \cdots , n_r} {x^{n_1}}_1 \cdots {x^{n_r}}_r$$