순열 (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$을 나누어주면 된다.
[참고]
[수학] 순열, 조합 공식 총정리
팩토리얼 ( ! ) 팩토리얼이란 서로 다른 n개를 나열하는 경우의 수를 의미합니다. 기호로는 n! 이렇게 쓰고 계산은 n부터 1씩 줄여나가면서 1이 될때까지의 모든 수를 곱합니다. 순열 ( nPr ) 순열이
coding-factory.tistory.com
'CS > 알고리즘' 카테고리의 다른 글
최단 경로 알고리즘 (0) | 2023.04.03 |
---|---|
피보나치 수열 (0) | 2023.02.10 |
에라토스테네스의 체 (소수 판별 알고리즘) (0) | 2023.02.05 |
효율적으로 약수 구하기 (0) | 2023.02.04 |
유클리드 호제법 (최대공약수 구하는 알고리즘) (0) | 2023.02.04 |