같은 것이 있는 순열

순열에서는 서로 다른 것중에 일부 또는 전부를 일렬로 줄 세우는 것을 다루었습니다.

한편, n개의 문자 중에 일부 또는 전부가 동일할 때, 일렬로 배열하는 방법의 수에 대해 알아 보겠습니다.

예를 들어, $a, a, b$ 를 일렬로 세우는 방법의 수는 몇 개일까요? 우선 이 문제를 일반 순열로 바꾸기 위해, $a 1, a 2, b$ 를 구하는 문제로 생각해 보겠습니다. 물론 이 방법은 수는 3!=6가지입니다.

a_{1},a_{2},b

그리고

a_{2},a_{1},b

a_{1},b,a_{2}

그리고

a_{2},b,a_{1}

b,a_{1},a_{2}

그리고

b,a_{2},a_{1}

위의 6가지에서 각줄에 2개로 쓰인 것은 $a 1, a 2$ 가 순서를 바꿈으로 인해서 다른 경우로 세어집니다. 그러나, 만약 아래첨자를 제외하면, 서로 같은 경우가 됩니다. 즉 전체 방법의 숫자는 전체를 다르다고 생각해서 경우의 수를 구한 후에, 같은 것을 1개로 세기 때문에, 같은 것의 개수로 나눗셈을 취해 줍니다.

이 방법은 이미 원순열에서 사용했던 방법입니다. 원순열에서도 서로 다른 n개를 원탁에 앉힐 때, n 개의 같은 것이 발생하고, 이것을 1개로 세기 위해서, 순열의 개수 n!을 n으로 나누어 (n–1)!의 경우의 수가 생깁니다.

따라서, n개 중에 서로 같은 것이 각각 p개, q개, ..., r개씩 있을 때, n개를 모두 일렬로 배열하는 순열의 수는 다음과 같습니다:

{\frac {n!}{p!q!\cdots r!}}

(단,

p+q+\cdots +r\leq n

)

예를 들어, 위의 경우는 3!/2!입니다.

순서가 정해져 있는 순열

한편, $a, b, c, d, e, f$ 를 일렬로 세울 때, $a, b, c$ 는 반드시 이 순서를 지켜야 하는 경우의 수는 몇 개일까요?

이 경우도 같은 것이 있는 순열과 수학적으로 동등합니다. 왜냐하면, $a, a, a, d, e, f$ 를 일렬로 세운 후에, 두 번째 $a$ 를 $b$ 로 바꾸고, 세 번째 $a$ 를 $c$ 로 바꿈으로써 순서가 정해져 있는 순열로 바꿀 수 있기 때문입니다.

최단 경로의 수

같은 것이 있는 순열에서 많이 다루어지는 응용 중 하나는 최단 경로의 경우의 수입니다. 예를 들어, 그림과 같은 도로망에서 $P$ 에서 $Q$ 까지 가는 최단 경로로 가는 경우의 수는 몇 가지일까요?

$P$ 에서 $Q$ 까지 가는 최단 경로는 오른쪽으로 4번 위로 3번을 움직여야 합니다. 만약 오른쪽으로 움직이는 것을 $a$ 로 매핑하고 위쪽으로 움직이는 것을 $b$ 로 매핑하면, 다음과 같은 순열로 매핑할 수 있습니다.

a, a, a, a, b, b, b

즉, 최단 경로로 가는 경우의 수는

{\frac {7!}{4!\cdot 3!}}={\frac {7\cdot 6\cdot 5}{3\cdot 2\cdot 1}}=35

.

최단 경로는 합의 법칙을 사용하여 경우의 수를 구할 수 있습니다. 각 경로의 분기점마다 경우의 수는 이전 경우의 수의 합으로 쉽게 구해집니다. 예를 들어, $P$ 에서 $C$ 까지 가는 경로의 수는 $P$ 에서 $A$ 또는 $B$ 를 거쳐 $C$ 까지 가는 경로의 경우의 수이기 때문에, 그림에서처럼, 1+1=2가지입니다. 다른 예제로 $P$ 에서 $E$ 까지 가는 경로의 수는 $P$ 에서 $C$ 또는 $D$ 를 거쳐 $E$ 까지 가는 경로의 경우의 수이므로, 2+1=3가지입니다.

한편, $P$ 에서 $E$ 를 반드시 거쳐 $Q$ 까지 가는 최단 경로의 경우의 수는 곱의 법칙을 이용합니다. 거쳐 가는 최단 경로는 연이어서 발생하므로, $P$ 에서 $E$ 까지 경로의 수와 $E$ 에서 $Q$ 까지 경우의 수의 곱이 최단 경로의 경우의 수입니다.

구하는 방법은 같은 것이 있는 순열로 해석하거나, 또는 각 경로의 합의 법칙으로 구할 수도 있습니다.

{\frac {3!}{2!}}\times {\frac {4!}{3!}}=12

반면에, $P$ 에서 $E$ 를 거치지 않고 $Q$ 까지 가는 최단 경로의 경우의 수는 전체 경우의 수에서 $E$ 를 거쳐 가는 경우의 수를 빼서 해결합니다.

35–12=23

만약 특정 지역을 거쳐가지 못하는, 즉, 복소의 점을 거쳐가지 않는, 또는, 불규칙적인 경로는, 위에서 소개한 합의 법칙의 방법이 일반적으로 적용하기 쉽습니다.

그림과 같이 경로의 일부가 지워지거나, 또는 불규칙하게 연결되어 있을 때에, $P$ 에서 $Q$ 까지 가는 최단 경로의 경우의 수는 합의 법칙을 적용해서 구하는 것이 편합니다.