여러 가지 순열

바둑판처럼 도로가 난 도시에서, 집에서 학교까지 가려면 동쪽으로 5블록, 북쪽으로 3블록을 가야 한다. 가장 짧은 길로만 가기로 하면 어느 교차로에서든 동쪽이나 북쪽으로만 꺾는다. 매일 다른 길로 가 보고 싶은데, 가장 짧은 길은 모두 몇 가지일까? 길 하나하나를 그려서 세기는 어렵다. 그런데 길을 "동동북동동북동북"처럼 글자로 적으면, 같은 글자가 여러 개 있는 배열을 세는 문제로 바뀐다고 한다. 어떻게 셀까?

1.1.1같은 것을 바꾸면 같은 배열

서로 다른 \(n\)개를 일렬로 늘어놓는 방법은 \(n!\)가지이다. 그런데 늘어놓을 것 가운데 같은 것이 있으면, 같은 것끼리 자리를 바꾸어도 배열이 달라지지 않는다. 예를 들어 "동"이 5개 있으면, 이 5개를 서로 구별된다고 보고 센 배열들 가운데 \(5!\)개씩이 실제로는 같은 배열이다. 그래서 전체를 구별된다고 보고 센 수를 같은 것들의 자리 바꿈 수로 나누어야 한다. 원탁에 앉는 방법을 셀 때 돌려서 같은 배열의 수로 나눈 것과 같은 생각이다.

가장 짧은 길은 동쪽 5번과 북쪽 3번, 모두 8번의 이동을 어떤 순서로 하느냐로 정해진다. 그래서 가장 짧은 길의 수는 "동" 5개와 "북" 3개를 늘어놓는 방법의 수 \(\dfrac{8!}{5!\,3!}\)이다. 이것은 8번의 이동 가운데 북쪽으로 갈 3번을 고르는 조합 \({}_8\mathrm{C}_3\)과 같다. 길을 그리는 문제가 글자를 늘어놓는 문제로, 다시 자리를 고르는 문제로 바뀐 것이다.¹

1.1.2지나야 하거나 피해야 하는 곳

특정한 교차로를 꼭 지나야 하면, 집에서 그 교차로까지의 길의 수와 그 교차로에서 학교까지의 길의 수를 곱한다. 두 구간의 길을 각각 고르면 전체 길이 하나 정해지므로 곱의 법칙을 쓴다. 공사 중인 교차로를 피해야 하면, 전체 길의 수에서 그 교차로를 지나는 길의 수를 뺀다. 이렇게 큰 문제를 작은 구간으로 나누어 곱하고 빼면 복잡한 길도 셀 수 있다.

1.1.3예제 풀이

가장 짧은 길은 \(\dfrac{8!}{5!\,3!} = \dfrac{40320}{120\times6} = 56\)가지이다. 공사 중인 교차로를 지나는 길은 집에서 그곳까지 \(\dfrac{3!}{2!\,1!} = 3\)가지, 그곳에서 학교까지 동쪽 3블록과 북쪽 2블록이므로 \(\dfrac{5!}{3!\,2!} = 10\)가지여서 \(3\times10 = 30\)가지이다. 그래서 피해 가는 길은 \(56 - 30 = 26\)가지이다.

TOMATO에는 T가 2개, O가 2개, M과 A가 하나씩 있으므로 늘어놓는 방법은 \(\dfrac{6!}{2!\,2!} = \dfrac{720}{4} = 180\)가지이다. 즉 같은 것이 있는 배열은 모두 구별된다고 보고 센 뒤 같은 것들끼리의 자리 바꿈 수로 나누어 세며, 바둑판 길처럼 겉보기에 다른 문제도 글자의 배열로 바꾸면 같은 방법으로 셀 수 있다.

아래 탐구 카드에서 원탁에 앉는 방법이 \(n!\)보다 적은 까닭을 확인하고, 바둑판 도시의 가장 짧은 길을 조건을 바꾸어 가며 세어 보자.

1. 바둑판 길을 세는 방법은 파스칼의 삼각형과 같다. 각 교차로까지의 길의 수는 왼쪽 교차로와 아래쪽 교차로까지의 길의 수의 합이어서, 교차로마다 수를 적어 나가면 파스칼의 삼각형이 비스듬히 나타난다.