순열과 조합

순열

서로 다른 $n$개에서 $r$ ($0 < r \leq n$)개를 택하여 일렬로 나열하는 것을 $n$개에서 $r$개를 택하는 순열이라고 하며, 이 순열의 수를 기호로 ${}_n P_r$와 같이 나타냅니다.

1. ${}_n P_n = n!$, ${}_n P_0 = 1$, $0! = 1$
2. 일반적으로 ${}_n P_r = \dfrac{n!}{(n-r)!}$ (단, $0 \leq r \leq n$)

조합

서로 다른 $n$개에서 순서를 생각하지 않고 $r$ ($0 < r \leq n$)개를 택하는 것을 조합이라고 합니다. 조합의 수는 기호로 ${}_n C_r$로 나타냅니다.

1. ${}_n C_n = 1, \quad {}_n C_0 = 1$
2. ${}_n C_r = \frac{{}_n P_r}{r!} = \frac{n!}{r!(n-r)!} \quad (\text{단, } 0 \leq r \leq n)$
3. ${}n C_r = {}_n C{n-r} \quad (\text{단, } 0 \leq r \leq n)$
4. ${}n C_r = {}{n-1} C_{r-1} + {}_{n-1} C_r \quad (\text{단, } 1 \leq r < n)$

원순열

서로 다른 것을 원형으로 배열하는 순열을 원순열이라고 합니다. 서로 다른 $n$개를 원형으로 배열하는 원순열의 수는 다음과 같습니다.

$$
\frac{n!}{n} = (n-1)!
$$

원순열에서 회전하여 일치하는 것은 모두 같은 것으로 봅니다.

다각형으로 배열하는 경우의 수

$$(n-1)! \times \text{(회전시켰을 때 겹치지 않는 자리의 수)}$$

중복순열

중복을 허용하여 만든 순열을 중복순열이라 합니다. 서로 다른 $n$개에서 중복을 허용하여 $r$개를 택하는 중복순열의 수를 기호로 ${}_n \Pi_r$로 나타냅니다.

$$
{}_n \Pi_r = n^r
$$

일반 순열에서 $0 \leq r \leq n$이지만, 중복순열에서는 중복이 가능하므로 $r > n$일 수 있습니다. ${}_n \Pi_r$의 $\Pi$는 Product의 첫 글자를 딴 것입니다.

같은 것이 있는 순열

$n$개 중에서 같은 것이 각각 $p$개, $q$개, $\cdots$, $r$개 있을 때, $n$개를 일렬로 나열하는 경우의 수는 다음과 같습니다.

$$
\frac{n!}{p!q!...r!} \quad (\text{단, } p + q + ... + r = n)
$$

중복조합

중복을 허용하여 만든 조합을 중복조합이라 하며, 서로 다른 $n$개에서 중복을 허용하여 $r$개를 택하는 경우의 수를 기호로 ${}_n H_r$로 나타냅니다.

$$
{}_n H_r = {}{n+r-1} C_r
$$

조합에서는 $0 \leq r \leq n$이지만, 중복조합에서는 $r > n$일 수 있습니다. ${}_n H_r$의 $H$는 Homogeneous의 첫 글자를 딴 것입니다.