순열과 조합

순열

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

1. ${}_n{P}_n=n!$, ${}_n{P}_0=1$, $0!=1$
2. 일반적으로 ${}_n{P}_r={\displaystyle \frac{n!}{(n-r)!}}$ (단, $0\le r\le n$)

조합

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

1. ${}_n{C}_n=1,{}_n{C}_0=1$
2. ${}_n{C}_r=\frac{{}_n{P}_r}{r!}=\frac{n!}{r!(n-r)!}(\text{단, }0\le r\le n)$
3. $n{C}_r={}_{n}Cn-r(\text{단, }0\le r\le n)$
4. $n{C}_r=n-1C_{r-1}+{}_{n-1}{C}_r(\text{단, }1\le r<n)$

원순열

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

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

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

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

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

중복순열

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

$${}_n{\mathrm{\Pi }}_r=n^r$$

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

같은 것이 있는 순열

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

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

중복조합

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

$${}_n{H}_r=n+r-1C_r$$

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