순열과 조합

순열 (Permutation)

서로 다른 n개 중 순서에 상관있게 r개를 선택하는 경우의 수

• 서로 다른 n개에서 r개를 택하는 순열의 수는 다음과 같다.예를 들어, 서로 다른 5개에서 3개를 고르는 순열의 수 $_5P_3$은
  5 X 4 X 3 = 60
  즉, $_nP_r$은 n부터 내림차순으로 r번째 수까지 곱하면 된다.
  팩토리얼을 이용하여 간단하게 나타내보면 다음과 같다.

$$0!=1,,_nP_0=1,,_nP_n=n!$$

$$
_nP_r=n(n-1)(n-2)\cdot \cdot \cdot(n-r+1),(단,0<r\leq n)
$$

$$
_nP_r = \frac{n!}{(n-r)!},(단,0\leq r \leq n)
$$

중복 순열

중복 가능한 n개 중 순서에 상관있게 r개를 선택하는 경우의 수

$$
_n\Pi_r=n^r
$$

조합 (Combination)

서로 다른 n개 중 순서에 상관없이 r개를 뽑는 것

$$
_nC_r = \frac{n!}{r!\times (n-r)!}
$$

 

상황에 따라 다음의 공식을 이용하여 문제를 쉽게 해결할 수도 있다.

 

$$
_nC_r = _nC_{n-r}
$$

 

이를 증명하는 방법은 간단하다.

 

$_nC_r=\frac{n!}{r!(n-r)!}$에서 $r$ 대신 $n-r$을 대입하면

$$
_nC_r=\frac{n!}{(n-r)!{n-(n-r)}!}\\=\frac{n!}{(n-r)!r!}\\=_nC_r
$$

중복조합

중복 가능한 n개 중 순서에 상관없이 r개를 선택하는 경우의 수

$$
_nH_r=_{n+r-1}C_r
$$

 

 

같은 것이 있는 순열

같은 값을 갖는 원소들이 포함되어 있는 배열에서 선택하는 경우의 수는 전체 원소 개수의 팩토리얼에서 중복된 원소들 각각의 개수의 팩토리얼을 나누어 주면 된다.

예를 들어, aaabb가 있다고 하면 a가 3개, b가 2개이므로 5!을 3!, 2!으로 나누어주면 된다.

$$
ex),,aaabb \rightarrow,\frac{5!}{3!2!}
$$

 

 

원 순열

원 모양 테이블에 n개의 원소를 나열하는 경우

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

1에서 시작해서 13524

2에서 시작해서 24135

3에서 시작해서 35241

4에서 시작해서 41325

5에서 시작해서 52413

모두 원을 돌리면 결국은 다 똑같다.

그러므로 n개의 원소를 나열하는 경우의 수인 $n!$에서 $n$을 나누어주면 된다.

 

 

 

[참고]

[수학] 순열, 조합 공식 총정리