순열 편집하기

Permutation
== 조합론에서 ==
=== 정의 ===
{{인용문|서로 다른 <math>n</math>개의 원소에서 <math>r</math>개를 '''중복없이''' 골라 '''순서에 상관있게''' 나열하는 것을 <math>n</math>개에서 <math>r</math>개를 택하는 '''순열'''이라고 한다.}}
기호로는 <math>_nP_r, P\left(n,r\right),\left(n\right)_r</math>등 여러 가지가 있지만 한국에서 자주 쓰이는 것은 <math>_nP_r</math>이고, 세계적으로는 어느 기호가 딱히 자주 쓰인다고 말하기 힘들다 (책마다 다르다). 아래에서 다루는 것은 사실 순열이 아닌 '''순열의 개수'''를 구하는 것임을 명심하고 읽자. 순열, 그 자체에 대해서 알고 싶다면 [[순열#군론에서|군론 문단]]으로 가자.

뭔가 거창한 설명이 붙었지만 순열은 초등학교 때부터 알게 모르게 써왔던 수학 개념중 하나다.<ref>초등학교 때 한번쯤은 "(0, 1, 2, 3)중 3개를 골라서 만들 수 있는 3자리 수의 개수를 구하시오"같은 문제는 풀어봤을 것이다.</ref> 계산하는 방법도 초등학교에서 해왔던 방법 그대로이며, 단지 미지수가 추가된 것 뿐. 수식으로 나타내면 <math>_nP_r=n\times\left(n-1\right)\times\left(n-2\right)\times\cdots\times\left(n-r+1\right)</math>이다.<ref>n부터 시작해서 하나씩 작은 수를 r개 곱한 것이다.</ref> 이를 [[팩토리얼]]을 사용하여 좀더 간략화 하면 <math>_nP_r={{n!}\over {\left(n-r\right)!}}</math>이다.

다만, 위 정의에서 몇 가지 문제가 발생하는데 그 중 하나가 바로 0!이다. 상식적으로 생각해 봤을 때, n개중에 n개를 중복없이, 순서에 맞게 고르는 방법은 n!이다. 다만 이를 수식으로 나타내면 <math>_nP_n=n!/\left(n-n\right)!=n!/0!</math>이 되고, 답과 대응시키기 위해서는 <math>0!=1</math>라 정의되어야 한다. 이에 대한 자세한 내용은 [[팩토리얼]] 참조. 다른 하나는 <math>_nP_0</math>. 역시 상식적으로 생각했을 때, n개중에 0개를 고르는 방법은 딱 한 가지 뿐이지만, 수식으로 나타낼 수는 없다 (n부터 시작해서 하나씩 작은수를 '''0'''개 곱한다는 것이 상상이 되는가?). 따라서 <math>_nP_0=1</math>로 정의한다.

=== 중복순열 ===
순열과 마찬가지로 n개 중에 r개를 순서에 상관있이 뽑는데, '''중복을 허락하여'''뽑는 것을 말한다. 역시 거창한 설명이지만 초등학교 때부터 써온 수학적 개념. 계산하는 방법 역시 초등학교에서 해왔던 방법과 동일하다. 지수를 사용해 [[경우의 수]]를 나타내면 <math>n^r</math>이 된다. 한국에서는 <math>_n\Pi_r</math>이라는 표현을 쓰는데, 이는 한국에서만 쓰이는 출처 불명의 기호이다. 세계적으로는 그냥 <math>n^r</math>라 나타낸다.

=== 같은 것이 있는 경우의 순열 ===
n개 중에 r개를 중복없이 순서에 맞게 뽑는데, n개 중에 똑같은 것이 몇개 섞여있을 경우를 말한다. 예를 들어 세 개의 문자 <math>a, a, b</math>를 일렬로 늘어놓는 순열의 수를 찾아보자. 직접 찾아보면 <math>aab, aba, baa</math>의 세 가지 경우밖에 없다. 여기서 좀 더 관찰 해보면 3개를 일렬로 늘어놓는 순열의 수는 <math>_3P_3=3!=6</math>, 중복되는 문자는 2개이고, <math>3=6/2</math>이다. 곧, 같은 것이 있을 때는 전체 순열의 수에서 무언가를 나눠주면 된다는 것을 확인할 수가 있다. 그리고 그 무언가는 중복되는 문자를 나열하는 방법의 수, 즉 이 예시에서는 2!이 된다.

중복되는 것이 다른 종류로 여러 가지 있을 때도 같은 논리가 성립하며, 이를 수식으로 나타내면 아래와 같다.
:<math>i</math>번째 물체가 <math>a_i</math>(<math>i=1,2,\cdots,k</math>)개 있다고 가정하자. 만약 <math>\sum_{i=1}^ka_i=n</math>이라 하면, 이 <math>n</math>개의 물체를 일렬로 나열하는 방법의 수는,
:<math>\frac{n!}{a_1!a_2!\cdots a_k!}</math>
:이며, 기호로는 <math>\binom{n}{a_1\;a_2\;\cdots\;a_k}</math>로 나타낸다.

=== 원순열 ===
n개를 나열하는데, 원형으로 나열하는 경우의 수를 말한다. 예를 들어 a, b, c, d를 원형으로 나열하는 가짓 수를 찾는다 하자. 얼핏 생각하면 <math>4!=24</math>이라 말하기 쉽지만 처음 놓는 문자의 위치는 어디든지 다 '''똑같다'''. 원을 돌려버리면 그만이기 때문. 하지만 두번째 이후로 놓는 문자부터는 위치에 관계 있으며, 결국 구하고자 하는 답은 <math>\left(4-1\right)!=6</math>이 된다. 이를 일반적으로 나타내면 아래와 같다.
:<math>n</math>개의 물체를 원형으로 나열하는 수 <math>=\left(n-1\right)!</math>

비슷한 방법으로 다각형 순열을 정의할 수 있다. 원순열과 비슷하게 다각형을 돌려서 겹치게 할 수 있는 부분은 동일하게 취급한다. 서로 다른 부분이 <math>k</math>개인 다각형 모양으로 <math>n</math>개의 물체를 배열하는 방법의 수는 <math>k\left(n-1\right)!</math>이다. 원의 경우, 서로 다른 부분이 1개이기 때문에 공식이 마찬가지로 성립하는 것을 알 수 있다.

=== 뒤집어 놓을 수 있는 원순열의 수 ===
염주순열, 혹은 목걸이순열이라고도 불린다 (고등학교 교육과정 밖). n개를 나열하는데, 회전할 수도 있고(원), 정면과 후면에서 바라 볼 수도 있을 때의(마치 목걸이를 뒤집듯이) 경우의 수를 말한다. 좌우 대칭을 했을 때 겹칠 수 있다면 한 가지로 취급하므로 일반적인 경우의 수는 <math>\frac{\left(n-1\right)!}{2}</math>이다.

=== 예시 ===
순열
{{인용문2|10명중 3명을 뽑아 일렬로 세우는 경우의 수: <math>_{10}P_3=10!/\left(10-3\right)!=10!/7!=720</math>}}

중복순열
{{인용문2|숫자 0, 1, 2, 3를 써서 세 자리 자연수를 만드는 가짓수: 첫 자리에 올 수 있는 가짓수 = 3, 나머지 자릿수에 올 수 있는 가짓수 = <math>4^2</math>. 따라서, 곱의 법칙에 의해 <math>3\times4^2=48</math>}}

같은 것이 있는 경우의 순열
{{인용문2|wiki의 네 문자를 일렬로 나열할 때의 가짓수: <math>\frac{4!}{2!}=12</math>}}

원순열
{{인용문2|서로 다른 5개의 구슬을 원형으로 나열하는 가짓수: <math>\left(5-1\right)!=4!=24</math>}}

목걸이 순열
{{인용문2|서로 다른 5개의 구슬로 목걸이를 만드는 방법의 가짓수: <math>\frac{1}{2}\left(5-1\right)!=12</math>}}

== 군론에서 ==
=== 정의 ===
고등학교의 순열을 생각하고 추상대수학의 순열을 쉬울거라 생각하면 상당히 곤란하다. 군론에서의 순열은 고등학교에서 배운 것과 달리 상당히 추상적이기 때문. 먼저 순열의 정의부터 다시 하고 넘어가자.
:집합 <math>X</math>에 대해, '''리스트(list)'''를 [[함수]] <math>f:\left\{1,\,2,\,\ldots,\,n\right\}\to X</math>로 정의한다. 만약 <math>f</math>가 [[일대일 대응]]이라면, 우리는 이 함수를 '''재배열(arrangement)'''이라 부른다. 중요한 것은, <math>X</math>가 무한집합일 수도 있다는 것이다.
함수가 들어가서 이해가 어려울 수도 있지만, 사실 이 리스트는 여러 개의 물건(= 집합의 원소)를 순서대로(1부터 n까지) 막 나열한 것에 불과하다. 이래도 이해가 안 된다면 직접 아무 집합에 대해 리스트를 만들어 보면 이해가 될 것이다. 이제 순열을 다음과 같이 정의한다.
:집합 <math>X</math>에 대해, 일대일 대응 함수 <math>\alpha:X\to X</math>를 '''순열(permutation)'''이라 정의한다. 중요한 것은 <math>X</math>가 무한집합일 수도 있다는 것이다.
역시 함수가 들어가 있지만, 뜯어보면 집합의 원소를 중복 없이 나열한 것에 불과하다. 만약 여기에 순서를 부여하고 싶다면, 재배열 함수 <math>\varphi</math>와 <math>f</math>에 대해 <math>f\circ\varphi^{-1}</math>을 계산해주면 된다. 반대로, 재배열 함수를 <math>\alpha\circ\varphi</math>로 나타낼 수도 있다.

이제 <math>X=\left\{1,\,2,\,\ldots,\,n\right\}</math>라 하자. 그럼 우리는 순열을 다음과 같이 나타낼 수 있다.
:<math>\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>\alpha\left(1\right)</math>로, 2는 <math>\alpha\left(2\right)</math>로, 이런식으로 쭉 순서를 바꾸는 것이다. 이러한 순열들의 집합을 <math>S_X</math>로 나타내며, 이는 함수의 합성에 대해 [[군 (수학)|군]]을 이룬다. 보통 '''대칭군(symmetric group)'''이라 부르며, 만약 <math>X=\left\{1,\,2,\,\ldots,\,n\right\}</math>일 경우 <math>S_n</math>으로 간단히 표기한다. 어째서 군을 이루는지는 별로 어렵지 않으므로 직접 확인해보자. {{ㅊ|증명은 독자에게 연습문제로 남긴다.}}

그런데 저 표기법에는 한 가지 문제가 있다. 표기법이 너무 길다는 것. {{ㅊ|고작 이런게 문제점이라니, 수학자들이란...}} 표기법을 간단히 하기 위해 몇 가지 정의를 더 알아보자.
:<math>\alpha\in S_n</math>에 대해, <math>\alpha\left(i\right)=i</math>이면, 우리는 <math>\alpha</math>가 <math>i</math>를 '''고정(fix)'''시킨다 한다. 반대로, <math>\alpha\left(i\right)\neq i</math>이면 <math>\alpha</math>는 <math>i</math>를 '''움직(move)'''인다 한다. 더욱이, 만약 <math>i_1,\,i_2,\,\ldots,\,i_r</math>가 1부터 <math>n</math>까지의 서로 다른 자연수이고, <math>\alpha\left(i_1\right)=i_2,\quad\alpha\left(i_2\right)=i_3,\quad\ldots,\quad\alpha\left(i_{r-1}\right)=i_r,\quad\alpha\left(i_r\right)=i_1</math>이면, 우리는 <math>\alpha</math>를 '''r-사이클(r-cycle)'''이라 부른다. 길이가 r이라 부르기도 한다.
여기까지 정의했으면, 순열 표기법을 다음과 같이 간략화 할 수 있다.
:<math>\alpha=\left(i_1\,i_2\,\ldots\,i_r\right)</math>
이 표기법에서 수학자들은 <math>i_1</math>은 <math>i_2</math>로 옮기고, <math>i_2</math>는 <math>i_3</math>을 옮기고, 이런식으로 쭉 반복한 뒤에, 마지막으로 <math>i_r</math>은 <math>i_1</math>으로 옮기는 것으로 정의하였다. 만약 <math>\alpha</math>가 두 개 이상의 사이클을 포함한다면, 그냥 두 사이클의 곱으로 나타내면 된다. 고정시키는 원소에 대해서는 표기하지 않는 걸로, (혹은 길이가 1인 사이클로 표기하기로) 약속한다.

=== 분해 ===
주어진 순열이 두 개 이상의 사이클의 곱으로 나타내어졌다 가정하자. 이 사이클들은 수의 곱셈과는 달리, 순서를 바꾸는 것이 일반적으로 불가능하다. 좀 더 정확히 말하면, 두 사이클이 공통 원소를 포함하고 있을 때, 곱의 순서에 따라 결과물이 달라진다. 아래 예시를 살펴보자.
:<math>\alpha=(12)(13)</math>과 <math>\beta=(13)(12)</math>를 비교해보자. 순열은 오른쪽에서 왼쪽으로 계산하게 된다. 먼저, <math>\alpha</math>는 1을 3으로 옮긴다. 3은 먼저 1로 옮겨진 뒤에 2로 옮겨지게 된다. 마지막으로 2는 1로 옮겨지게 된다. 즉, <math>\alpha=(132)</math>이다. 같은 방법으로 계산해보면, <math>\beta=(123)</math>이다. 분명히 <math>\alpha\neq\beta</math>이다.
그럼 자연스럽게 어떤 경우에 두 사이클의 순서를 교환할 수 있냐고 물을 수 있는데, 답은 간단하다. 두 사이클에 공통 원소가 없으면 된다. 이런 두 사이클을 우리는 '''disjoint'''라 부른다. disjoint한 두 사이클에 대해 [[교환법칙]]이 성립하는 것 역시 증명이 별로 어렵지 않으므로 생략한다.

또 다른 자연스러운 질문은, 모든 순열이 disjoint한 사이클들의 곱으로 나타낼 수 있냐는 것이다. 이것의 답은 당연히 그렇다이며, 증명은 [[수학적 귀납법]]을 사용한다. 이제, 주어진 임의의 순열을 disjoint한 사이클들의 곱으로 분해했다고 하자. 길이가 1인 사이클까지 표기에 포함시켰을 때, 우리는 이 분해를 '''complete factorization'''이라 부른다. 아래 예시를 살펴보자.
:<math>\alpha=\begin{pmatrix}1&2&3&4&5\\1&3&4&2&5\end{pmatrix}</math>를 분해해보면, <math>\alpha=(1)(234)(5)</math>이다 이 표기는 complete factorization이다. 반면, 길이가 1인 사이클을 생략한 (234), (1)(234), (234)(5)는 complete factorization이 아니게 된다.
수학적 감각이 있는 사람이라면 이 분해가 [[소인수분해]]와 비슷하다는 느낌을 받았을 것이다. 그럼, 자연스럽게 묻게 되는 질문은 이 complete factorization이 유일한지 아닌지에 대한 질문이다. 순서를 바꾼 것을 제외하면 이 분해는 유일하며, 증명은 [[소인수분해]]의 유일성을 증명하는 것과 흡사하다.

=== 군 ===
앞서, 순열의 집합 <math>S_n</math>이 [[군 (수학)|군]]을 이룬다 하였다. 그럼 이 군의 [[항등원]]과 [[역원]]이 무엇인지 당연히 알아봐야 할 것이다. 항등원은 당연히 아무것도 움직이지 않는 순열이다. 그러니까, complete factorization을 했을 때 모든 사이클의 길이가 1이라는 것이다. 이 항등원을 기호로 보통 e나 1로 표기한다. 그런데 1은 숫자 1과 헷갈릴 가능성이 높으므로, 여기에서는 e로 표기하기로 하자. 역원 역시 찾기 쉬운데, 고정시키는 원소는 건드리지 말고, 움직이는 원소는 거꾸로 움직이게 하면 그게 순열의 역원이 된다. 즉, <math>\left(i_1\,i_2\,\ldots\,i_r\right)</math>의 역원은 단순히 <math>\left(i_r\,i_{r-1}\,\ldots\,i_1\right)</math>이다. 믿지 못한다면 직접 계산을 통해 저 두 사이클의 곱이 e가 됨을 직접 확인해보자. 사이클의 항등원과 역원을 구했다면 일반적인 순열의 항등원과 역원 역시 쉽게 구할 수 있다. 순열 <math>\alpha</math>의 complete factorization을 <math>\beta_1\beta_2\cdots\beta_k</math>라 가정하자. 그럼, 항등원은 그대로 e이고, 역원은 <math>{\beta}_k^{-1}{\beta}_{k-1}^{-1}\cdots{\beta}_1^{-1}</math>이다. 증명은 역시 [[수학적 귀납법]]을 사용한다.

=== Conjugation ===
추상대수학에서 빼놓을 수 없는 것이 바로 이 conjugation이다. conjugation을 설명하기에 앞서, 정의를 하나 하고 넘어가자.
:두 순열 <math>\alpha,\,\beta\in S_n</math>에 대해, 이 두 순열의 complete factorization이 모든 <math>r\geq1</math>에 대해 같은 개수의 r-cycle을 가지고 있다면, 우리는 이 두 순열이 '''같은 사이클 구조(same cycle structure)'''를 가지고 있다 부른다.
예를 하나 들면, (123)(45)와 (135)(24)는 같은 사이클 구조를 가지고 있다.

수학에서 conjugation은 많은 의미를 가지지만, 여기서의 conjugation이란, 주어진 한 순열의 전후로 다른 순열과 그 역원을 곱하는 것을 말한다. 즉, <math>\alpha,\,\gamma\in S_n</math>에 대해, <math>\alpha</math>의 <math>\gamma</math>에 의한 conjugation은 <math>\gamma\alpha\gamma^{-1}</math>을 말한다. 눈치가 빠른 사람은 여기서 conjugation과 같은 사이클 구조 사이의 연관성을 의심할 것이다. 적당한 두 순열에 대해 conjugation을 구해보면 알 수 있겠지만, 임의의 순열과 그 conjugation은 항상 같은 사이클 구조를 가진다. 좀 더 자세히 설명하면 다음과 같다.
:<math>\alpha:i\mapsto j</math>일 때, <math>\gamma\alpha\gamma^{-1}:\alpha\left(i\right)\mapsto\alpha\left(j\right)</math>이다.
예를 들어, <math>\alpha=(123)(45),\,\gamma=(135)</math>라 가정하자. 그럼, <math>\gamma\alpha\gamma^{-1}</math>는 <math>(\gamma(1)\,\gamma(2)\,\gamma(3))(\gamma(4)\,\gamma(5))=(325)(41)</math>이고, <math>\alpha</math>와 그 conjugation은 같은 사이클 구조를 가지고 있음을 확인할 수 있다.

conjugation은 같은 사이클 구조를 가지고 있음을 확인하였다. 그럼 역으로, 같은 사이클 구조를 가지고 있으면 두 순열은 conjugation 관계에 있을까? 답은 당연하게도 그렇다이며, 우리는 conjugation 관계와 같은 사이클 구조가 서로 동치인 명제임을 확인할 수 있다. 여기서 자연스럽게 떠오르는 질문은, 어떤 순열에 대해 conjugation을 취해야 다른 순열이 튀어나오는지 찾는 것이다. 예를 들면, (123)(45)에 어떤 원소를 conjugate해야 (325)(41)이 나올까? 답은 간단하다, 그냥 두 순열을 두 줄로 나열한 뒤, 그 순열을 간략화하면 된다. 즉, <math>\gamma=\begin{pmatrix}1&2&3&4&5\\3&2&5&4&1\end{pmatrix}=(135)(2)(4)=(135)</math>이다. 그리고 우리는 전 예시에서 (135)가 답이라는 사실을 알고있다. 물론, 이것말고도 다른 순열이 존재할 수도 있다.

=== 치환 (Transposition) ===
길이가 2인 사이클을 '''치환 (transposition)'''이라 부르고, 기호로는 보통 <math>\tau</math>로 표기한다. 이 transposition을 사용하여 일반적인 순열에 대해 여러 가지 사실을 알 수 있는데, 먼저 임의의 <math>\alpha\in S_n</math>은 transposition의 곱임을 보이겠다.
:<math>\left(1\,2\,\ldots\,r\right)=\left(1\,r\right)\left(1\,r-1\right)\cdots\left(1\,2\right)</math>이다. 만약 길이가 1이라면, 적당한 <math>i\neq j</math>에 대해 <math>\left(i\,j\right)\left(j\,i\right)=e</math>이다. 즉, 모든 길이의 사이클을 transposition의 곱으로 분해할 수 있다.
이 transposition을 어디다가 써먹냐고 물을텐데, transposition은 순열의 '''[[기우성]](parity)'''를 정의하는데 쓰인다. 먼저, 순열의 부호를 다음과 같이 정의하자.
:<math>\alpha\in S_n</math>이고, <math>\alpha</math>의 complete factorization을 <math>\beta_1\beta_2\cdots\beta_t</math>라 하자. 그럼, <math>\alpha</math>의 부호 sgn을 <math>\operatorname{sgn}\left(\alpha\right)=\left(-1\right)^{n-t}</math>로 정의한다.
여기서 sgn은 [[라틴어]]로 부호를 의미하는 signum이며, 현대 영어에선 sign을 의미한다. 이 부호함수는 다음 두 성질을 만족한다.
#<math>\operatorname{sgn}\left(\tau\alpha\right)=-\operatorname{sgn}\left(\alpha\right)</math>
#<math>\operatorname{sgn}\left(\alpha\beta\right)=\operatorname{sgn}\left(\alpha\right)\operatorname{sgn}\left(\beta\right)</math>
첫 번째 성질은 임의의 순열의 부호가 transposition의 개수에 의해 결정된다는 사실을 알려주고, 두 번째 성질은 부호함수가 (조건이 다르지만) 완전 [[곱셈적 함수]]라는 것을 알려준다.

이제, 임의의 순열 <math>\alpha</math>에 대해, <math>\operatorname{sgn}\left(\alpha\right)=1</math>이면 이 순열을 '''짝수(even)''', -1이면 '''홀수(odd)'''의 [[기우성]]을 가지고 있다 정의한다. 왜 짝수랑 홀수냐 하면, <math>\alpha</math>가 짝수개의 transposition을 가지고 있을 때 부호가 +1, 홀수개의 transposition을 가지고 있을 때 부호가 -1이기 때문. 이 중에 주목해야 할 것은 짝수 순열인데, 짝수 순열들의 집합은 함수의 합성에 대해 또 [[군 (수학)|군]]을 이룬다! 이를 '''[[교대군]](Alternating Group)'''이라 부르며, 기호로는 <math>A_n</math>으로 표기한다. 참고로 교대군은 수학적 관점에서 재밌는 성질들을 가지는데, 그 성질 중 하나가 바로 '''5차 이상의 방정식은 근의 공식이 없음'''을 증명하는데 쓰인다.<ref><math>n\geq5</math>일 때, <math>A_n</math>이 simple이라는 사실을 사용한다.</ref> 순열이 [[조합론]]과 [[대수학]]을 잇는 큰 역할을 하게 된 셈. 교대군에 관한 것은 항목을 참조하자.

== 관련 항목 ==
*[[경우의 수]]
*[[조합]]
*[[군 (수학)]]
*[[교대군]]

{{각주}}
[[분류:조합론]][[분류:추상대수학]]