순열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학에서, 순열(順列, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 이들은 함수 합성에 따라 대칭군이라는 을 이룬다.

표현[편집]

집합 {1,2,3,4,5} 상의 순열로서 1을 2로, 2를 5로, 3을 3으로, 4를 1로, 5를 4로 보내는 순열을 다음과 같이 표시한다.

 f =\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 3 & 1 & 4\end{bmatrix}.

만약 집합 {1,2,3,4,5}에 이 치환을 여러 차례 연달아 적용한다면, 1은 2로 간 뒤 5로 갔다가 4을 거쳐 다시 1로 돌아오며, 이 과정에서 1이 거쳐가는 원소들(1,2,5,4)을 제외한 나머지 원소(3)는 전혀 움직이지 않는 것을 알 수 있다. 이와 같이 한 원소에서 출발해 치환에 의해 움직이는 모든 원소를 전부 거쳐올 수 있는 치환을 순환치환(cycle)이라 한다. 위의 순환치환은 간단히 (1 2 5 4)로 표시할 수 있다. 이 순환치환은 총 4개의 원소를 거치므로 이를 '길이 4의 순환치환'이라 한다.

이제 아래의 두 순열을 생각해 보자.

 g = (1\ 3)(4\ 5)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 2 & 1 & 5 & 4\end{bmatrix}
 h = (1\ 2\ 5)(3\ 4)=\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{bmatrix}.

집합 {1,2,3,4,5}에 h를 적용한 뒤 g를 적용하면, 1은 2로 갔다가 2에 도착하고, 2는 5로 갔다가 4로 도착할 것이다. 이와 같은 식으로 나머지도 계산해서 다음의 결과를 얻는다:

 gh = g\circ h = (1\ 2\ 4)(3\ 5)=\begin{bmatrix} 1 & 2 &3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3\end{bmatrix}.

일반적으로 길이 L = mn의 순환치환을 m승 하면 길이 n의 순환치환 m개의 곱이 된다. 예를 들어 m = 2, n = 3일 때,

 (1~2~3~4~5~6)^2 = (1~3~5) (2~4~6).

호환(transposition)은 두 원소를 서로 바꾸고 나머지 원소들은 그대로 놔두는 순열을 말한다. 즉, 호환이란 길이 2의 순환치환이다. 임의의 치환은 호환들의 곱으로 쓸 수 있는데, 예를 들어 (1 3 5 4) = (1 4)(1 5)(1 3)이다. 이 경우와 마찬가지로 홀수개의 호환의 곱으로 표현할 수 있는 치환을 홀치환이라고 하고, 짝수개의 호환의 곱으로 표현할 수 있는 치환을 짝치환이라고 한다. 일반적으로 치환을 호환들의 곱으로 표현하는 방법은 여러 개가 있지만, 홀치환은 언제나 홀수 개, 짝치환은 언제나 짝수 개의 호환의 곱으로 나타난다.

특수한 순열의 수[편집]

n개의 원소의 r-순열[편집]

n개의 원소의 r-순열은 서로 다른 n 개의 원소 중에서 r 개(n \geq r)를 뽑아서 한 줄로 세우는 방법이다. 그 가능한 개수 P(n,r)은 다음과 같다.

P(n,r) = n(n-1)(n-2)\cdots (n-r+1)=P(n,r) = \frac{n!}{(n-r)!}

예를 들어, 네 개의 문자 A,B,C,D 에서 두 개를 뽑아 나열하는 방법은 P(4,2)=\frac{4!}{(4-2)!}=4\times 3 = 12이므로 12가지가 된다. 일일이 나열하면 다음과 같다.

{AB, AC, AD, BA, BC, BD, CA, CB, CD, DA, DB, DC}

같은 것이 있는 순열[편집]

n개 중에 같은 것이 각각 p개, q개, …, r개가 있을 때, n개 모두를 일렬로 배열하는 순열의 수로 다음과 같다.

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

중복순열[편집]

중복순열(重複順列) n\Pirn 개의 서로 다른 원소 중에서 중복을 허용하여 r개를 뽑아서 한 줄로 나열하는 경우의 수이다. r 개를 선택하는 경우, 최초에 n 개를 선택할 수 있고 이후에도 계속 n 개를 선택할 수 있기 때문에 이 순열의 개수는 n^r임을 알 수 있다.

예를 들어, 1부터 4까지의 자연수 4개를 이용하여 만들 수 있는 세자리 수는 모두 43 = 64 가지가 있다.

원순열[편집]

원순열(圓順列, circular permutation)은 n개를 원형으로 나열하는 방법의 경우의 수이다. n개를 일렬로 나열하는 경우의 수는 n!인데, 원은 돌렸을 때 같아지는 것이 생기기 때문에, 여기서 중복되는 것이 n배 있음을 알 수 있다.

따라서 다음과 같이 수를 정의한다.

\frac{n!}{n} = \frac{n(n-1)!}{n} = \frac{(n-1)!}{1}

염주순열[편집]

염주순열(念珠順列)은 n개의 서로 다른 종류의 구슬로 목걸이를 만드는 방법의 수이다. n의 원순열은 \frac{n!}{n}인데, 목걸이는 뒤집어도 같은 것으로 취급하므로, 여기에서 중복되는 것이 2배가 있는 것을 알 수 있다. 따라서 n의 염주순열의 수는 \frac{n!}{2n} = \frac{n(n-1)!}{2n} = \frac{(n-1)!}{2} 이다.

완전순열[편집]

완전순열(영어: complete permutation) 또는 교란(derangement) 또는 서브팩토리얼(subfactorial)은 순열 중, 원래 순열의 모든 요소를 변화시켜서 얻는 순열을 가리킨다. 기호는 !n.

같이 보기[편집]

바깥 고리[편집]