순열에서는 서로 다른 것 중에 일부 또는 전부를 일렬로 줄 세우는 것을 다루었습니다.
한편, \(n\)개의 문자 중에 일부 또는 전부가 같을 때, 일렬로 배열하는 방법의 수에 대해 알아보겠습니다.
예를 들어, \(a, a, b\)를 일렬로 세우는 방법의 수는 몇 개일까요? 우선 이 문제를 일반 순열로 바꾸기 위해, \(a_1, a_2, b\)를 일렬로 세우는 방법의 수를 생각해 보십시오. 물론 이 방법은 수는 모두가 서로 다르기 때문에 일반 순열로써 3!=6가지입니다. 즉,
\(\quad\)\(a_1, a_2, b\) 그리고 \(a_2, a_1, b\)
\(\quad\)\(a_1, b, a_2\) 그리고 \(a_2, b, a_1\)
\(\quad\)\(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\)개를 일렬로 배열하는 순열의 수는 다음과 같습니다:
\(\quad\)\(\displaystyle \frac{n!}{p!q!\cdots r!}\) (단, \(p+q+\cdots+r \le n\))
예를 들어, 위의 경우는 \(\frac{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\)로 매핑하면, 다음과 같은 순열로 매핑할 수 있습니다.
\(\quad\)\(a, a, a, a, b, b, b\)
즉, 최단 경로로 가는 경우의 수는
\(\quad\)\(\displaystyle \frac{7!}{4!\cdot3!}=\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\)까지 경우의 수의 곱이 최단 경로의 경우의 수입니다.
\(\quad\)구하는 방법은 같은 것이 있는 순열로 해석하거나, 각 경로의 합의 법칙으로 구할 수도 있습니다.
\(\quad\)\(\displaystyle \frac{3!}{2!} \times \frac{4!}{3!}=12\)
반면에, \(P\)에서 \(E\)를 거치지 않고 \(Q\)까지 가는 최단 경로의 경우의 수는 전체 경우의 수에서 \(E\)를 거쳐 가는 경우의 수를 빼서 해결합니다.
\(\quad\)35–12=23
만약 특정 지역을 거쳐가지 못하는, 즉, 여러 개의 점을 거쳐가지 않는, 또는, 불규칙적인 경로는, 위에서 소개한 합의 법칙의 방법이 일반적으로 적용하기 쉽습니다.
그림과 같이 경로의 일부가 지워지거나, 또는 불규칙하게 연결되어 있을 때에, \(P\)에서 \(Q\)까지 가는 최단 경로의 경우의 수는 합의 법칙을 적용해서 구하는 것이 편합니다.
