순열(Permutation)

서로 다른 물건 n개 가운데 k개를 골라 한 줄로 세웁니다. 첫 자리에는 n개 중 아무거나 올 수 있고, 둘째 자리에는 남은 n−1개 중 하나, 셋째 자리에는 n−2개 중 하나가 옵니다. 단계마다 선택지의 수가 앞에서 무엇을 골랐는지와 상관없이 정해져 있으면, 전체 경우의 수⁠(number of cases)⁠는 단계별 수를 곱한 것입니다(곱의 법칙). 그래서 방법의 수는 $n(n-1)\cdots(n-k+1)$입니다.

물건 개 중 개를 늘어놓는 방법을 모두 그렸습니다. 점 한 줄이 배열 하나이고, 색이 물건입니다.

첫 자리 색으로 나눈 덩어리가 n개이고 덩어리마다 크기가 ${}_{n-1}P_{k-1}$로 같다는 것이 곱의 법칙을 그대로 보여 줍니다. k = n이면 전부를 늘어놓는 경우로, 방법의 수는 계승⁠(factorial)⁠ $n! = 1\cdot2\cdots n$입니다. 지금 $n!$ = . 늘어놓기 하나는 n개의 자리에서 n개의 물건으로 가는 일대일대응 하나이므로, n!은 원소⁠(element)⁠가 n개인 집합⁠(set)⁠에서 자기 자신으로 가는 전단사 함수⁠(bijective function)⁠의 개수이기도 합니다. 아무것도 늘어놓지 않는 방법도 한 가지로 쳐서 $0! = 1$입니다.

계승은 무섭게 빨리 자랍니다. 10! = 3,628,800이고, 카드 52장을 섞는 방법은 $52! \approx 8.07\times10^{67}$가지라서 잘 섞은 카드의 순서는 거의 틀림없이 지금까지 한 번도 나온 적이 없는 순서입니다. 이 크기를 어림하는 식이 스털링 공식⁠(Stirling's formula)⁠ $n! \approx \sqrt{2\pi n}\,(n/e)^n$입니다. n이 커질수록 두 변의 비가 1로 다가가며, n = 10에서 이미 1% 안쪽입니다. 외판원이 도시 n곳을 한 번씩 돌고 돌아오는 경로는 출발점과 방향을 무시해도 $(n-1)!/2$가지라서, 모두 따져 보는 방법은 금세 불가능해집니다. 더 영리한 방법들이 있지만, 도시 수 n의 다항식($n^2, n^3$ 같은) 정도로만 늘어나는 시간에 언제나 가장 짧은 경로를 찾는 방법이 있는지는 아직 아무도 모릅니다. '길이가 L 이하인 경로가 있는가'라는 외판원 문제⁠(traveling salesman problem)⁠는 NP-완전⁠(NP-complete)⁠, 곧 답이 주어지면 확인하기는 쉬운 문제들 가운데 가장 어려운 축에 들기 때문에, 이 물음의 답은 P 대 NP 문제⁠(P versus NP problem)⁠의 답과 같습니다.

순서를 잊으면. 고른 k개의 순서를 무시하면 같은 k개로 만든 배열 k!개가 한 묶음이 되므로, 묶음의 수는 이항계수⁠(binomial coefficient)⁠ $\binom nk = \frac{n!}{k!\,(n-k)!}$입니다. 같은 것이 섞여 있어도 같은 방식으로 나눕니다. MISSISSIPPI의 글자를 늘어놓는 방법은 $\frac{11!}{1!\,4!\,4!\,2!} = 34650$가지입니다. 원탁에 둘러앉는 경우처럼 돌려서 같아지는 배열을 하나로 치면(원순열⁠, circular permutation⁠) n으로 나누어 $(n-1)!$가지입니다.

이어지는 곳. 무작위로 섞은 순열에서 아무것도 제자리에 있지 않을 확률⁠(probability)⁠은 교란순열⁠(derangement)⁠에서, 같은 생일이 나올 확률은 생일 문제⁠(birthday problem)⁠에서 순열의 비로 계산합니다. 두 개씩 비교만 하는 정렬이 최악의 경우 적어도 $\log_2 n!$번 비교해야 하는 까닭은 n!가지 순서를 가려내야 하기 때문입니다(비교 정렬의 하한⁠, comparison sorting lower bound⁠). 순열을 '어느 자리의 것을 어느 자리로 옮기는가'라는 자리 바꾸기로 보면 두 순열을 잇달아 하는 합성이 또 하나의 순열이 되고, n개의 순열 전체는 합성에 대해 군을 이룹니다(대칭군⁠, symmetric group⁠). 순열 하나를 따라가면 몇 개의 고리, 곧 순환으로 쪼개집니다. 예를 들어 1→3, 3→2, 2→1, 4→4인 순열은 길이 3인 순환 (1 3 2)와 길이 1인 순환 (4)로 쪼개지고, 그 길이들 3 + 1은 4의 분할입니다. 같은 섞기를 되풀이해 처음 순서로 돌아오기까지의 횟수는 순환 길이들의 최소공배수입니다. 길이 3과 2인 순환으로 된 섞기는 여섯 번 만에 처음으로 돌아옵니다. 최소공배수⁠(least common multiple)⁠는 최대공약수⁠(greatest common divisor)⁠로 구하고, 순환 하나를 k번 돌린 결과는 k를 순환 길이로 나눈 나머지⁠(remainder)⁠로 정해지니 모듈러 연산⁠(modular arithmetic)⁠의 문제가 됩니다.