같은 것이 있는 순열의 원리

같은 것이 있는 순열의 원리

본문은 도서 내용의 일부임.

다음으로 이야기할 개념은 ‘같은 것이 있는 순열’이다.

지금까지 이야기한 개념은 ‘같은 것이 없는 순열’이라면 일부 같은 것이 섞여 있는 경우도 있다.

보통 알파벳의 순서를 나열하는 문제가 대표적이다.

 

APPLE이라는 단어가 있다고 하자.

 

같은 것이 있는가? PP가 2개가 있으니 같은 것이 있다. 그렇다면 A,P,P,L,E을 순서대로 나열하는 경우는 몇 가지일까?

아무거나 써보자.

PPALE APLPE LEPAP ELAPP

꽤 많은 경우가 나올 것 같다. 하나도 빠짐없이 찾기가 쉽지가 않은 상황이다. 좋은 방법이 없을까?

 

우리는 앞에서 ‘같은 것이 없는 순열’을 배웠다.

이걸 최대한 이용해보는 건 어떨까?

같은 것이 없는 영어 단어 하나를 가지고 와보자.

서로 다른 4개(CAKE) 중 4개를 택하여 순서대로 나열하는 방법이라고 할 수 있다.

₄P₄를 계산법대로 풀면 4부터 숫자 하나씩 내려가며 4번 곱한다. 즉,

₄P₄=4×3×2×1=24(가지)

이때, ₄P₄처럼 _nP_n꼴은 !(팩토리얼이라고 읽는다)를 사용하여 나타낼 수 있다.

₄P₄=4!=4×3×2×1=24

일반적으로

_nP_n=n!=n×(n-1)×(n-2)…×2×1

이 성립한다.

같은 것이 없는 순열(ex CAKE)의 개념을 통해 같은 것이 있는 순열(ex APPLE)을 풀 수 있는 방법을 찾아보자.

 

우리는 한 가지 가정을 해보기로 한다.

APPLE 이란 단어에 들어있는 모든 알파벳이 모두 다르다고 가정하는 것이다.(실제로 PP가 2개임에도) 즉 PP를 다르다고 가정하고 순서대로 나열해보는 것이다.

편의상 PP를 P1P2라고 임시로 표시하기로 한다.

 

은 5개의 알파벳으로 이루어졌으므로

AP1P2LE을 일렬로 나열하는 방법은 120가지가 된다.

그러나 이것은 PP가 서로 다르다고 가정했을 경우이다. 실제로 PP는 서로 같은 문자이다. 따라서 PP의 자리를 바꾸어도 PP이므로 경우의 수가 실제로 120가지보다 작아야 한다.

자리를 바꿔보면 왼쪽은 다른 경우처럼 보이지만 ‘실제로’는 같은 경우이다.

즉 경우의 수가 2배가 되지 않는다.

 

이것보다 더 쉬운 AAA를 예를 들어보자. 이 3개의 알파벳은 서로 같다. 따라서 제 아무리 자기들끼리 자리를 바꿔도 같은 경우이다

아까와 마찬가지로 AAA가 서로 다른 문자라고 가정해보자. 편의를 위해 A1A2A3처럼 숫자에 태그를 붙여서 마치 다른 문자처럼 보이도록 하자.

그렇다면 같은 문자를 나열하는 방법의 수인 3! 로 나누어 주면 그 문자들끼리 서로 자리를 바꾸는 경우의 수를 1가지로 만들 수 있게 된다.

 

 

 

다시, APPLE과 같이 PP라는 같은 것이 섞여 있는 단어를 나열하는 경우의 수를 보자.

 

P1AP2LE의 경우와

P2AP1LE는 실제로 같은 경우이다.

 

즉 위의 숫자를 빼고 보면

PAPLE

PAPLE

인 것이다.

결국, P1AP2LE을 나열하는 120가지 경우에서 P1와 P2가 서로 자리를 바꾸는 경우가 2가지씩 있는 것이다.

따라서 120가지 경우에서 2개의 문자끼리 나열하는 경우의 수인 2! = 2 × 1 = 2를 나누어서 P끼리 배열하는 경우만 제거해주면 APPLE을 일렬로 나열하는 경우의 수가 된다.

120÷2=60(가지)

APPLE과 같이 같은 것이 있는 순열은 같은 것끼리 나열하는 경우를 전체 경우의 수에서 나누어 주면 된다.

정리하면, APPLE과 같이 같은 것(P,P)가 있는 순열은 마치 모든 문자가 서로 다른 것으로 취급하여 전체 경우의 수를 구한 다음, 실제로 같은 문자끼리 자리를 바꾸는 경우를 되돌리기 위해 같은 문자끼리 배열하는 경우를 나누어 주는 것이다.

 

이제 aabbb를 일렬로 나열하는 경우의 수를 구해보자.

aa와 bbb는 같은 문자이므로 ‘같은 것이 있는 순열’ 문제이다. 마찬가지로 모두 다른 문자로 취급하여 전체 경우의 수를 구한다음, 같은 문자끼리 배열하는 경우를 나누어 주면 된다.

aa는 2P2 = 2! = 2 × 1 = 2(가지)

bbb는 3P3 = 3! = 3 × 2 × 1 = 6(가지)

이므로 전체 경우의 수인 5P5 = 5! = 5 × 4 × 3 × 2 × 1 = 120(가지)

에서 나누어 주면 된다.

‘같은 것이 있는 순열’ 문제는 알파벳 문제 말고 다른 유형이 있다.

최단 경로 찾기 문제를 보자.

A에서 출발하여 B까지 이르는 모든 경로는 몇 가지인가.

단, 가장 빠른 길이어야 한다. 그렇다면 ‘오른쪽’과 ‘위쪽’으로만 갈 수 있고 ‘왼쪽’과 ‘아래쪽’은 갈 수 없다.

편의상 ‘오른쪽’ 대신 → , ‘위쪽’ 대신 ↑ 라는 기호로 표시해보자.

위 그림처럼 일일이 그려보며 경로의 가짓수를 찾을 수 있을 것이다.

하지만 매번 똑같은 경로판을 그리는 것보다 더 간단하게 나타내는 방법이 있다. 위 그림처럼 이동경로를 그림으로 나타내는 대신 화살표로 표현할 수도 있다.

①의 경우는  ↑  ↑  ↑  →  →  →  → →

②의 경우는  →  →  →  ↑  ↑  →  → ↑

③의 경우는  →  ↑  →  ↑  ↑  →  → →

로 나타내어도 된다. 굳이 표를 그리지 않아도 같은 표시가 되는 것이다.

여기서 경로의 모든 가짓수를 찾는 방법을 발견할 수 있다.

첫째, ①②③의 공통점은 →이 5개, ↑이 3개라는 것이다.

둘째, →와 ↑를 각각 5번, 3번만 사용하여 나열하면 그것이 바로 최단경로의 방법의 수가 된다는 것이다.

 

가령  ↑  →  ↑  →  →  ↑  → → 라고 하면,

경로판에 왼쪽부터 순서대로 나타내보면,

이렇게 하나의 경로가 완성된다.

따라서 ↑ 5개, → 3개를 일렬로 나열하는 방법을 찾으면 되는 것이다.

여기에서 다시 편의를 위해 → 대신 a, ↑ 대신 b로 나타내보면

 →  →  →  →  →  ↑  ↑ ↑ ⇔ aaaaabbb

총 8개의 문자이고, a가 5개, b가 3개인 ‘같은 것이 있는 순열’ 문제가 된다.

먼저 8개 모두 마치 다른 문자처럼 일렬로 배열하고, 같은 문자끼리 배열하는 것을 되돌리기 위해 a끼리 나열하는 방법과 b끼리 나열하는 방법을 나누는 것이다.

총 56가지이다. 이렇게 최단경로를 일일이 그리지 않고서 ‘같은 것이 있는 순열’로 해석하여 해결할 수 있는 것이다.

본문은 도서 내용의 일부임.