여러가지 순열

순열

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

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

$_{n} C_{n} = 1,_{n} C_{0} = 1$
$_{n} C_{r} = \frac{_{n} P _{r}}{r !} = \frac{n !}{r ! ( n - r )!} (단, 0 \leq r \leq n)$
$_{n} C_{r} =_{n} C_{n - r} (단, 0 \leq r \leq n)$
$_{n} C_{r} =_{n - 1} C_{r - 1} +_{n - 1} C_{r} (단, 1 \leq r < n)$

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

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

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

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

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

_{n} Π_{r} = n^{r}

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

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

\frac{n !}{p ! q ! ... r !} (단, 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의 첫 글자를 딴 것입니다.