경우의 수, 순열, 조합

---

💡

<문제 해결을 위한 알고리즘 with 수학> 책을 참고 했습니다.

경우의 수(곱의 법칙)

---

사건1이 일어나는 경우가 N가지, 사건2가 일어나는 경우가 M가지일 때 사건1과 사건2가 일어나는 경우의 조합은 모두 NM가지 이다.

이런 곱의 법칙은 사건이 3개 이상인 경우로도 확장할 수 있다.

예를 들어 “형태”, “색”, “타입”을 선택해서 로고 마크를 만드는 경우를 생각해 보자.

• 형태 : 원, 사각형, 삼각형

• 색 : 붉은색, 파란색

• 타입 : 1, 2, 3, 4

로고 마크를 만드는 방법은 모두 3 x 2 x 4 = 24가지이다.

n개의 대상을 나열하는 방법의 수

---

n개의 대상을 나열하는 방법은 $n!$ = $n \times (n-1) \times (n-2)… \times 2 \times 1$ 로 구할 수 있다.

예를 들어서 3개의 정수 1, 2, 3을 나열하는 방법은 3! = 3 x 2 x 1 = 6가지이다.

나열할 때마다 선택지가 하나씩 줄어들기 때문에 위와 같은 구조를 갖는 것이다.

순열 ($_nP_r$)

---

순열은 서로 다른 n개 중 r개를 골라, 순서를 고려해 나열한 경우의 수이다.

순서를 고려한다는 것은 순서가 달라지면 같은 요소를 가지고 있더라도 서로 다른 것으로 취급한다는 뜻이다.

예) [1, 2, 3] ≠ [3, 2, 1]

$_nP_r = \frac{n!}{ (n-r)!} = n \times (n-1)\times(n-2)\times ... \times(n-r+1)$

→ 모든 수를 나열하지 않고 n개 중에서 r개만 나열하기 때문에 $n - r +1$까지만 나열해보면 모든 경우의 수를 구할 수 있다.

예를 들어 8개의 대상 중에서 3개를 나열하는 방법의 수는 다음과 같이 구할 수 있다.

$_8P_3 = \frac{\cancel{1\times2\times3\times4\times5}\times6\times7\times8}{\cancel{1\times2\times3\times4\times5}} = 6\times7\times8 = 336$

그림으로 보면 직관적으로 이해할 수 있다.

조합 ($_nC_r$)

---

순열과 마찬가지로 서로 다른 n개 중 r개를 고르지만, 순서를 고려하지 않는 경우의 수이다.

예) [1, 2] = [2,1]

https://ko.wikipedia.org/wiki/조합

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

조합의 경우의 수를 구하는 이 식은 $_nP_r$을 통해서 도출할 수 있다.

$r$개의 대상을 정렬하는 방법은 $r!$가지이므로, 나열하는 순서를 구별했을 경우의 패턴 수는 구별하지 않은 경우의 $r!$배가 된다.

예를 들어보자.

조합과 순열이 1, 2, 3이라는 숫자들로 만들어 낼 수 있는 경우의 수는 각각 다음과 같다.

조합 - [1, 2, 3]

순열 - [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

다시말해 순열은 조합의 경우의 수들에 대해서 순서를 고려하기 때문에 다음이 성립한다.

$_nP_r = r! \times_nC_r$

$_nC_r = \frac{_nP_r}{r!}$

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

참고자료

---

「문제 해결을 위한 알고리즘 with 수학」 - 위키북스

Uploaded by N2T