Permutation
고등학교에서
정의
“ 서로 다른 [math]\displaystyle{ n }[/math]개의 원소에서 [math]\displaystyle{ r }[/math]개를 중복없이 골라 순서에 상관있게 나열하는 것을 [math]\displaystyle{ n }[/math]개에서 [math]\displaystyle{ r }[/math]개를 택하는 순열이라고 한다. “
기호로는 [math]\displaystyle{ _nP_r, P\left(n,r\right) }[/math]등 여러 가지가 있지만 자주 쓰이는 것은 [math]\displaystyle{ _nP_r }[/math]이다.
뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념중 하나다.[1] 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 수식으로 나타내면 [math]\displaystyle{ _nP_r=n\times\left(n-1\right)\times\left(n-2\right)\times\cdots\times\left(n-r+1\right) }[/math]이다.[2] 이를 팩토리얼을 사용하여 좀더 간략화 하면 [math]\displaystyle{ _nP_r=n!/\left(n-r\right)! }[/math]이다.
다만, 위 정의에서 몇 가지 문제가 발생하는데 그 중 하나가 바로 0!이다. 상식적으로 생각해 봤을 때, n개중에 n개를 중복없이, 순서에 맞게 고르는 방법은 n!이다. 다만 이를 수식으로 나타내면 [math]\displaystyle{ _nP_n=n!/\left(n-n\right)!=n!/0! }[/math]이 되고, 답과 대응시키기 위해서는 [math]\displaystyle{ 0!=1 }[/math]라 정의되어야 한다. 이에 대한 자세한 내용은 팩토리얼 참조. 다른 하나는 [math]\displaystyle{ _nP_0 }[/math]. 역시 상식적으로 생각했을 때, n개중에 0개를 고르는 방법은 딱 한가지 뿐이지만, 수식으로 나타낼 수는 없다 (n부터 시작해서 하나씩 작은수를 0개 곱한다는 것이 상상이 되는가?). 따라서 [math]\displaystyle{ _nP_0=1 }[/math]로 정의한다.
중복순열
순열과 마찬가지로 n개 중에 r개를 순서에 상관있이 뽑는데, 중복을 허락하여뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 경우의 수를 나타내면 [math]\displaystyle{ n^r }[/math]이 된다.[3]
같은 것이 있는 경우의 순열
n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를들어 세 개의 문자 [math]\displaystyle{ a, a, b }[/math]를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 [math]\displaystyle{ aab, aba, baa }[/math]의 3가지 경우 밖에 없다. 여기서 좀더 관찰 해보면 3개를 일렬로 늘어놓는 순열의 수는 [math]\displaystyle{ _3P_3=3!=6 }[/math], 중복되는 문자는 2개이고, [math]\displaystyle{ 3=6/2 }[/math]이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 2!이 된다.
중복되는 것이 다른 종류로 여러 가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
[math]\displaystyle{ a, a, a, \cdots, a, b, b, b, \cdots, b, c, d }[/math](a가 p개, b가 q개, 전체 n개)의 순열의 수 [math]\displaystyle{ =\frac{n!}{p!\times q!} }[/math]
원순열
n개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를들어 a, b, c, d를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 [math]\displaystyle{ 4!=24 }[/math]이라 말하기 쉽지만 처음 놓는 문자의 위치는 어디든지 다 똑같다. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 [math]\displaystyle{ \left(4-1\right)!=6 }[/math]이 된다. 이를 일반적으로 나타내면 아래와 같다.
[math]\displaystyle{ n }[/math]개의 물체를 원형으로 나열하는 수 [math]\displaystyle{ =\left(n-1\right)! }[/math]
뒤집어 놓을 수 있는 원순열의 수
염주순열, 혹은 목걸이순열이라고도 불린다.[4] n개를 나열하는데, 회전할 수도 있고(원), 정면과 후면에서 바라 볼 수도 있을 때의(마치 목걸이를 뒤집듯이) 경우의 수를 말한다. 좌우 대칭을 했을 때 겹칠 수 있다면 한가지로 취급하므로 일반적인 경우의 수는 [math]\displaystyle{ \frac{\left(n-1\right)!}{2} }[/math]이다.
예시
순열
10명중 3명을 뽑아 일렬로 세우는 경우의 수: [math]\displaystyle{ _{10}P_3=10!/\left(10-3\right)!=10!/7!=720 }[/math]
중복순열
네 개의 숫자 0, 1, 2, 3을 써서 (중복 허락) 세 자리 자연수를 만드는 가짓수: 첫 자리에 올 수 있는 가짓수 = 3, 나머지 자리에 올 수 있는 가짓수 [math]\displaystyle{ =4^2 }[/math]. 곱의 법칙에 의해 [math]\displaystyle{ 3\times4^2=48 }[/math].
같은 것이 있는 경우의 순열
wiki의 네 문자를 일렬로 나열할 때의 가짓수: [math]\displaystyle{ \frac{4!}{2!}=12 }[/math]
원순열
서로 다른 5개의 구슬을 원형으로 나열하는 가짓수: [math]\displaystyle{ \left(5-1\right)!=4!=24 }[/math]
목걸이 순열
서로 다른 5개의 구슬로 목걸이를 만드는 방법의 가짓수: [math]\displaystyle{ \frac{1}{2}\left(5-1\right)!=12 }[/math]
군론에서
정의
고등학교의 순열을 생각하고 추상대수학의 순열을 쉬울거라 생각하면 상당히 곤란하다. 군론에서의 순열은 고등학교에서 배운 것과 달리 상당히 추상적이기 때문. 먼저 순열의 정의부터 다시 하고 넘어가자.
- 집합 [math]\displaystyle{ X }[/math]에 대해, 리스트(list)를 함수 [math]\displaystyle{ f:\left\{1,\,2,\,\ldots,\,n\right\}\to X }[/math]로 정의한다. 만약 [math]\displaystyle{ f }[/math]가 일대일 대응이라면, 우리는 이 함수를 재배열(arrangement)이라 부른다. 중요한 것은, [math]\displaystyle{ X }[/math]가 무한집합일 수도 있다는 것이다.
함수가 들어가서 이해가 어려울 수도 있지만, 사실 이 리스트는 여러개의 물건(= 집합의 원소)를 순서대로(1부터 n까지) 막 나열한 것에 불과하다. 이래도 이해가 안 된다면 직접 아무 집합에 대해 리스트를 만들어 보면 이해가 될 것이다. 이제 순열을 다음과 같이 정의한다.
- 집합 [math]\displaystyle{ X }[/math]에 대해, 일대일 대응 함수 [math]\displaystyle{ \alpha:X\to X }[/math]를 순열(permutation)이라 정의한다. 중요한 것은 [math]\displaystyle{ X }[/math]가 무한집합일 수도 있다는 것이다.
역시 함수가 들어가 있지만, 뜯어보면 집합의 원소를 중복 없이 나열한 것에 불과하다. 만약 여기에 순서를 부여하고 싶다면, 재배열 함수 [math]\displaystyle{ \varphi }[/math]와 [math]\displaystyle{ f }[/math]에 대해 [math]\displaystyle{ f\circ\varphi^{-1} }[/math]을 계산해주면 된다. 반대로, 재배열 함수를 [math]\displaystyle{ \alpha\circ\varphi }[/math]로 나타낼 수도 있다.
이제 [math]\displaystyle{ X=\left\{1,\,2,\,\ldots,\,n\right\} }[/math]라 하자. 그럼 우리는 순열을 다음과 같이 나타낼 수 있다.
- [math]\displaystyle{ \alpha=\begin{pmatrix}1&2&\ldots&i&\ldots&n\\\alpha\left(1\right)&\alpha\left(2\right)&\ldots&\alpha\left(i\right)&\ldots&\alpha\left(n\right)\end{pmatrix} }[/math]
즉, 1은 [math]\displaystyle{ \alpha\left(1\right) }[/math]로, 2는 [math]\displaystyle{ \alpha\left(2\right) }[/math]로, 이런식으로 쭉 순서를 바꾸는 것이다. 이러한 순열들의 집합을 [math]\displaystyle{ S_X }[/math]로 나타내며, 이는 함수의 합성에 대해 군을 이룬다. 보통 대칭군(symmetric group)이라 부르며, 만약 [math]\displaystyle{ X=\left\{1,\,2,\,\ldots,\,n\right\} }[/math]일 경우 [math]\displaystyle{ S_n }[/math]으로 간단히 표기한다. 어째서 군을 이루는지는 별로 어렵지 않으므로 직접 확인해보자. 증명은 독자에게 연습문제로 남긴다.