맨위로가기

순열

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

순열은 집합의 원소를 다른 순서로 나열하는 방법으로, 전단사 함수를 사용하여 정의된다. 순열은 함수의 합성에 따라 군을 이루며, 이를 대칭군이라고 한다. 순환, 궤도, 홀짝성과 같은 개념을 통해 순열의 다양한 성질을 설명할 수 있으며, 두 줄 표기법, 한 줄 표기법, 순환 표기법 등 다양한 표기법으로 표현할 수 있다. 순열의 수는 n!로 주어지며, k-순열, 중복 순열, 중복집합 순열, 원순열, 염주 순열 등 다양한 종류의 순열이 존재한다. 순열은 암호 해독, 오류 감지 및 수정 알고리즘, 전산학 등 다양한 분야에 응용되며, 순열을 생성하는 여러 알고리즘이 개발되어 있다.

더 읽어볼만한 페이지

  • 순열 - 레비치비타 기호
    레비치비타 기호는 n차원 공간에서 정의되는 완전 반대칭 텐서로, 순열의 부호에 따라 +1, -1, 0의 값을 가지며 벡터곱, 행렬식 계산 등 다양한 분야에서 활용된다.
  • 순열 - 완전순열
    완전순열은 집합의 순열 중 모든 원소가 원래 위치에 있지 않은 순열, 즉 고정점이 없는 순열을 의미하며, 크기가 n인 집합의 완전순열의 수는 준계승 !n으로 나타내고, 점화식 또는 포함-배제 원리로 계산하며, 몽모르 수라고도 불린다.
  • 계승과 이항식 주제 - 이항 정리
    이항 정리는 이변수 다항식 (x + y)ⁿ을 전개하는 공식으로, 이항 계수를 사용하며, 조합론적 증명과 수학적 귀납법을 통해 증명할 수 있고, 다양한 분야에 응용되며, 이항 급수, 다항 정리 등 일반화된 형태가 존재한다.
  • 계승과 이항식 주제 - 감마 분포
    감마 분포는 형상 모수와 척도 모수로 정의되는 연속 확률 분포로, 확률 밀도 함수가 감마 함수로 표현되며, 베이즈 통계학에서 켤레 사전 분포로 활용되고, 형상 모수가 양의 정수일 때는 얼랑 분포를 나타낸다.
순열
순열
순열의 예시
3개의 구별되는 객체(예: a, b, c)의 순열 6가지. 각 순열은 객체를 특정 순서로 정렬하는 것을 나타낸다.
분야조합론
정의주어진 집합의 원소들을 특정 순서로 배열하는 것
다른 이름차례무이 (문화어)
수학적 정의
표기법P(n, k) 또는ₙPᵣ 또는 Pₖ
nPr
공식n! / (n - k)!
설명n개의 서로 다른 원소에서 k개를 선택하여 나열하는 경우의 수
n-계승n! = n × (n − 1) × (n − 2) × ... × 2 × 1
함수S → S (집합 S에서 S로의 함수)
관련 개념
조합순서를 고려하지 않고 선택하는 경우의 수
대칭군집합의 모든 순열의 집합

2. 정의

집합 X의 '''순열'''은 전단사 함수 X\to X이다. 유한 집합 \{1,2,\dotsc,n\}의 순열 \sigma은 다음과 같이 2행 표기법을 사용하여 나타낼 수 있다.

:\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}

이는 각 원소 i가 \sigma(i)로 대응됨을 의미한다.

모든 집합 X의 순열들은 함수의 합성을 연산으로 하여 군을 이룬다. 이 군을 X의 '''대칭군'''이라고 부르며, \operatorname{Sym}(X) 또는 S_X로 표기한다. 특히, 유한 집합 \{1,2,\dotsc,n\}의 대칭군은 n차 대칭군이라고 하며, \operatorname{Sym}(n) 또는 S_n으로 표기한다. n개의 원소를 가진 집합의 순열의 총 개수는 n!이다.

수학 텍스트에서는 순열을 나타내기 위해 소문자 그리스 문자를 사용하는 것이 일반적이다. 주로 \alpha,\beta,\gamma 또는 \sigma, \tau,\rho,\pi 등이 사용된다.[9]

순열은 집합 S에서 자신으로의 전단사 함수로서, 집합의 원소를 재배열하는 함수(활동적 순열)로 해석될 수 있다. 다른 관점에서는 순열을 S의 원소들이 특정 순서로 배열된 목록(수동적 순열)으로 보기도 한다.

항등 순열은 집합의 모든 원소를 자기 자신으로 보내는 순열로, 즉 모든 x\in S에 대해 \sigma(x) = x를 만족한다. 항등 순열은 보통 1, \text{id}, 또는 \text{id}_S 등으로 표기한다.[10][11] 항등 순열은 대칭군에서 항등원의 역할을 한다.

2. 1. 순환

양의 정수 k가 주어졌을 때, 집합 X의 '''길이 k의 순환'''(-循環, cycle of length k영어) \begin{pmatrix}x_1&x_2&\cdots&x_k\end{pmatrix}은 다음과 같은 꼴의 순열이다. (여기서 x_i\in X는 서로 다른 원소이다.)

:x_1\mapsto x_2\mapsto\cdots\mapsto x_k\mapsto x_1

:x\mapsto x\qquad\forall x\in X\setminus\{x_1,x_2,\dotsc,x_k\}

즉, x_1은 x_2로, x_2는 x_3으로, ..., x_k는 다시 x_1으로 이동시키고, 이 외의 다른 모든 원소는 자기 자신으로 이동시키는 순열을 의미한다.

또한, '''길이 \aleph_0의 순환'''(-循環, cycle of length \aleph_0영어) 또는 '''무한 순환'''(無限循環, infinite cycle영어) \begin{pmatrix}\cdots&x_{-1}&x_0&x_1&\cdots\end{pmatrix}은 다음과 같은 꼴의 순열이다. (여기서 x_i\in X는 서로 다른 원소이다.)

:\cdots\mapsto x_{-1}\mapsto x_0\mapsto x_1\mapsto\cdots

:x\mapsto x\qquad\forall x\in X\setminus\{\dots,x_{-1},x_0,x_1,\dots\}

이는 무한히 많은 원소들이 연쇄적으로 다음 원소로 이동하는 순열을 나타낸다.

특히, '''호환'''(互換, transposition영어) \begin{pmatrix}x&y\end{pmatrix}은 길이가 2인 순환, 즉 2-순환 x\mapsto y\mapsto x이다. 이는 단순히 두 원소 x와 y의 위치를 서로 바꾸는 순열을 의미한다.

유한 집합 \{1,2,\dotsc,n\}의 '''인접 호환'''(隣接互換, adjecent transposition영어) \begin{pmatrix}x&x+1\end{pmatrix}은 인접한 두 수, 즉 x와 x+1의 위치를 서로 바꾸는 호환 x\mapsto x+1\mapsto x이다.

2. 2. 궤도

순열 \sigma\in\operatorname{Sym}(X)의 순환군 \langle\sigma\rangle은 X의 왼쪽에서 자연스럽게 작용한다. 즉, \sigma가 x\in X에 작용한 결과는 \sigma(x)이다. 이 작용의 각 궤도 \langle\sigma\rangle(x) (x\in X)를 \sigma의 '''궤도'''(軌道, orbiteng)라고 한다.

2. 3. 홀짝성

순열 \sigma에서 두 원소의 순서가 원래의 순서와 반대로 나타나는 경우를 반전(inversion영어) 또는 전도라고 한다. 더 정확히는, 순열 \sigma = (\sigma_1, \sigma_2, \dots, \sigma_n) 에서 i < j 이지만 \sigma_i > \sigma_j 를 만족하는 위치의 쌍 (i, j) 를 반전이라고 한다. 예를 들어, 순열 \sigma = (2, 3, 1, 5, 4) 에서는 (1, 3) (값 2, 1), (2, 3) (값 3, 1), (4, 5) (값 5, 4) 세 개의 반전이 존재한다.

순열 \sigma의 반전수(inversion number영어) \operatorname{inv\,num}(\sigma) 또는 N(\sigma)는 순열에 포함된 모든 반전의 총 개수를 의미한다. 위의 예시 \sigma = (2, 3, 1, 5, 4)의 반전수는 3이다.

순열의 부호(sign영어)는 반전수를 이용하여 정의할 수 있다. 순열 \sigma의 부호 \sgn(\sigma)는 다음과 같이 계산된다.

:\sgn(\sigma) = (-1)^{\operatorname{inv\,num}(\sigma)}

즉, 반전수가 짝수이면 부호는 +1이고, 반전수가 홀수이면 부호는 -1이다.

순열의 부호에 따라 순열을 다음과 같이 분류할 수 있다.

  • 짝순열(even permutation영어): 부호가 +1인 순열. 즉, 반전수가 짝수인 순열이다.
  • 홀순열(odd permutation영어): 부호가 -1인 순열. 즉, 반전수가 홀수인 순열이다.

3. 표기법

유한 집합의 순열을 나타내는 데에는 여러 가지 편리한 표기법이 사용된다. 주요 표기법으로는 두 줄 표기법, 한 줄 표기법, 순환 표기법 등이 있다.

'''두 줄 표기법'''은 코시가 1815년에 도입한 방식으로[14][15], 집합의 원소와 그 원소가 순열에 의해 옮겨지는 상(image)을 두 줄로 대응시켜 나타낸다. 예를 들어, 유한 집합 \{1, 2, \dots, n\}의 순열 \sigma는 다음과 같이 표기할 수 있다.

:\sigma=\begin{pmatrix}1&2&\cdots&n\\\sigma(1)&\sigma(2)&\cdots&\sigma(n)\end{pmatrix}

'''한 줄 표기법'''은 집합의 원소에 자연스러운 순서가 있다고 가정할 때, 각 원소의 상(image)만을 순서대로 나열하는 방식이다.[16][17] 즉, 순열 \sigma를 \sigma(1) \; \sigma(2) \; \cdots \; \sigma(n)과 같이 나타낸다. 이 표기법은 ''단어 표현''이라고도 한다.[21]

'''순환 표기법'''은 순열의 작용을 궤도별로 분해하여 순환들의 곱으로 나타내는 방식이다. 각 순환은 원소들이 순열에 의해 어떻게 이동하는지를 보여준다. 예를 들어, (1\, 2\, 5)(3\, 4)는 1이 2로, 2가 5로, 5가 1로 가고, 3이 4로, 4가 3으로 가는 순열을 나타낸다. 이 표기법은 순열의 구조를 명확하게 보여주기 때문에 널리 사용된다.[18]

수학 텍스트에서는 순열을 나타낼 때 소문자 그리스 문자인 \alpha, \beta, \gamma 또는 \sigma, \tau, \rho, \pi 등을 사용하는 것이 일반적이다.[9]

3. 1. 두 줄 표기법

코시가 1815년에 도입한[14][15] '''두 줄 표기법'''은 순열을 나타내는 한 방법이다. 이 표기법은 첫 번째 행에 집합 ''S''의 원소를 나열하고, 두 번째 행에는 첫 번째 행의 각 원소가 순열에 의해 대응되는 상(image)을 그 아래에 표시한다.

예를 들어, 집합 ''S'' = {1, 2, 3, 4, 5, 6}에서 정의된 순열 \sigma가 다음과 같다고 하자.

: \sigma(1) = 2, \ \ \sigma(2) = 6, \ \ \sigma(3) = 5, \ \ \sigma(4) = 4, \ \ \sigma(5) = 3, \ \ \sigma(6) = 1

이 순열 \sigma는 두 줄 표기법으로 다음과 같이 나타낼 수 있다.

: \sigma = \begin{pmatrix}

1 & 2 & 3 & 4 & 5 & 6 \\

2 & 6 & 5 & 4 & 3 & 1

\end{pmatrix}.

두 줄 표기법에서 첫 번째 행의 원소들은 어떤 순서로 나열해도 상관없다. 중요한 것은 각 원소와 그 아래에 있는 상 사이의 대응 관계이다. 따라서 위의 순열 \sigma는 다음과 같이 다르게 표현될 수도 있다.

: \sigma = \begin{pmatrix}

2 & 3 & 4 & 5 & 6 & 1 \\

6 & 5 & 4 & 3 & 1 & 2

\end{pmatrix}

= \begin{pmatrix}

6 & 5 & 4 & 3 & 2 & 1 \\

1 & 3 & 4 & 5 & 6 & 2

\end{pmatrix}.

다른 예로, 집합 {1, 2, 3, 4, 5}의 순열은 다음과 같이 쓸 수 있다.

: \sigma=\begin{bmatrix}

1 & 2 & 3 & 4 & 5 \\

2 & 5 & 4 & 3 & 1\end{bmatrix}

이 역시 첫 번째 행의 순서를 바꾸어 다음과 같이 표현할 수 있다.

: \sigma=\begin{bmatrix}

1 & 2 & 3 & 4 & 5 \\

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

2 & 4 & 5 & 1 & 3 \\

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

5 & 4 & 3 & 2 & 1 \\

1 & 3 & 4 & 5 & 2\end{bmatrix}

3. 2. 한 줄 표기법

집합 ''S''의 원소에 "자연스러운" 순서가 있다고 가정할 때 (예를 들어, 정수는 오름차순, 문자는 사전순 등), 가령 x_1, x_2, \ldots, x_n 순서가 있다고 하면, 두 줄 표기법은 다음과 같다.

: \sigma = \begin{pmatrix}

x_1 & x_2 & x_3 & \cdots & x_n \\

\sigma(x_1) & \sigma(x_2) & \sigma(x_3) & \cdots & \sigma(x_n)

\end{pmatrix}.

이러한 자연스러운 순서를 전제로, 첫 번째 줄(x_1, x_2, \ldots, x_n)을 생략하고 순열을 한 줄 표기법(one-line notation)으로 나타낼 수 있다. 이는 ''S''의 원소들을 순열에 의해 옮겨진 순서대로 나열하는 방식이다.[16][17]

: \sigma = \sigma(x_1) \; \sigma(x_2) \; \sigma(x_3) \; \cdots \; \sigma(x_n)

예를 들어, 집합 {1, 2, 3, 4, 5, 6}에 대한 두 줄 표기법

: \sigma = \begin{pmatrix}

1 & 2 & 3 & 4 & 5 & 6 \\

2 & 6 & 5 & 4 & 3 & 1

\end{pmatrix}

은 한 줄 표기법으로 다음과 같이 간단히 나타낸다.

: \sigma = 2 \; 6 \; 5 \; 4 \; 3 \; 1

다른 예시로,

: \sigma=\begin{bmatrix}

1 & 2 & 3 & 4 & 5 \\

2 & 5 & 4 & 3 & 1\end{bmatrix}

은 한 줄 표기법으로 2 \; 5 \; 4 \; 3 \; 1과 같이 쓴다.

한 줄 표기법은 보통 괄호 없이 숫자를 나열하며, 괄호를 사용하는 순환 표기법(예: (1 2 6)(3 5))과는 구분해야 한다. 한 줄 표기법은 단어 표현(word representation)이라고도 불린다.[21] 만약 원소가 두 자리 이상의 숫자처럼 여러 문자로 구성된 경우, 혼동을 피하기 위해 쉼표나 공백으로 구분하는 것이 일반적이다.

이 표기법은 기본적인 조합론이나 컴퓨터 과학 분야에서 자주 사용되며, 특히 여러 순열을 사전식 순서에 따라 비교해야 할 때 유용하다.

3. 3. 순환 표기법

순환 표기법은 집합 ''S''의 원소에 순열을 반복적으로 적용했을 때 나타나는 결과를 설명하는 방법이다. 이때 원소들이 순열에 의해 이동하는 경로를 궤도(orbit)라고 하며, 각 궤도를 나타내는 것을 순환(cycle)이라고 부른다.[9] 순열은 이러한 순환들의 목록으로 표현될 수 있으며, 서로 다른 순환은 서로소(겹치지 않는) 원소 집합을 포함하므로, 이를 "서로소 순환으로의 분해"라고 한다. 순환 표기법은 간결하고 순열의 구조를 명확하게 보여주기 때문에 널리 사용된다.

순환 표기법으로 순열 \sigma를 작성하는 과정은 다음과 같다.

1. 괄호를 열고, 아직 순환에 포함되지 않은 집합 ''S''의 임의의 원소 ''x''를 적는다: (\,x

2. 순열 \sigma를 ''x''에 반복적으로 적용하여 그 결과를 순서대로 적는다: (\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots

3. 결과가 다시 처음 원소 ''x''가 될 때까지 반복하고, 마지막에 ''x''는 다시 적지 않고 괄호를 닫는다: (\,x\,\sigma(x)\,\sigma(\sigma(x))\,\ldots\,\sigma^{k-1}(x)\,) (여기서 \sigma^k(x)=x이다.)

4. 아직 순환에 포함되지 않은 ''S''의 다른 원소 ''y''가 있다면, 그 원소로 새로운 순환을 시작하여 위 과정을 반복한다: (\,x\,\ldots\,)(\,y\,\ldots\,)

5. ''S''의 모든 원소가 어떤 순환에 포함될 때까지 이 과정을 반복한다.

일반적으로 길이가 1인 순환, 즉 순열을 적용해도 자기 자신으로 가는 원소 ''x'' (\sigma(x)=x인 경우, 고정점)는 순환 표기법에서 생략하는 것이 관례이다. 어떤 순환에도 나타나지 않는 원소는 순열에 의해 위치가 변하지 않는 것으로 간주한다.[18]

예를 들어, 한 줄 표기법으로 \sigma = 2 6 5 4 3 1로 주어진 순열(집합 {1, 2, 3, 4, 5, 6} 위에서 정의됨)을 순환 표기법으로 나타내 보자.

  • 먼저 1에서 시작하면, \sigma(1)=2, \sigma(2)=6, \sigma(6)=1이므로 첫 번째 순환은 (1\,2\,6)이다.
  • 다음으로 아직 사용되지 않은 원소 3에서 시작하면, \sigma(3)=5, \sigma(5)=3이므로 두 번째 순환은 (3\,5)이다.
  • 남은 원소 4는 \sigma(4)=4이므로 고정점이다. 이는 길이가 1인 순환 (4)에 해당하지만, 관례에 따라 생략한다.
  • 따라서 순열 \sigma의 순환 표기법은 \sigma = (1\,2\,6)(3\,5)이다.


순열 (1 7 5)(2 4 8)(3 6)의 그래프. 각 궤도와 순환 순열이 같은 색으로 표시되어 있다.


순환 표기법 (1\,2\,6)(3\,5)는 각 순환 (1\,2\,6)과 (3\,5)를 독립적인 순환 순열로 보고, 이들의 합성으로 해석할 수 있다. 즉, (1\,2\,6)은 1을 2로, 2를 6으로, 6을 1로 보내고 나머지(3, 4, 5)는 고정시키는 순열이며, (3\,5)는 3을 5로, 5를 3으로 보내고 나머지(1, 2, 4, 6)는 고정시키는 순열이다. 이 두 순환 순열을 합성하면 원래 순열 \sigma가 된다.

서로소 순환들은 서로 영향을 주지 않기 때문에, 곱하는 순서를 바꿔도 결과가 같다. 즉, 교환 법칙이 성립한다. 예를 들어, (1\,2\,6)(3\,5) = (3\,5)(1\,2\,6)이다. 또한, 각 순환은 시작하는 원소를 다르게 하여 표기할 수도 있다. 예를 들어, (1\,2\,6)은 (2\,6\,1) 또는 (6\,1\,2)와 같은 순열을 나타낸다. 따라서 하나의 순열에 대한 순환 표기법은 여러 가지 방식으로 쓰일 수 있다.

순환 표기법의 편리한 특징 중 하나는 순열의 역순열을 쉽게 구할 수 있다는 점이다. 각 순환의 원소 순서를 거꾸로 뒤집으면 역순열이 된다. 예를 들어, \sigma = (1\,2\,6)(3\,5)의 역순열은 \sigma^{-1} = (6\,2\,1)(5\,3)이다.

4. 성질

중복집합을 우선 집합으로 여겨 순열을 취한 뒤, 다시 중복집합으로 여겨 겹치는 순열들을 제외하는 방법으로 중복집합 순열의 수를 계산한 것
집합의 순열과 달리, 중복집합 순열에서는 같은 색깔의 원소들을 구별이 불가능하다고 여기며, 이에 따라 순열의 수가 줄어들게 된다.

  • '''순열의 개수''': ''n''개의 서로 다른 원소로 이루어진 집합의 순열의 총 개수는 ''n''!이다.

  • '''순환의 개수''': ''n''개의 원소로 이루어진 순열 중에서 정확히 ''k''개의 서로소 순환으로 분해되는 순열의 개수는 부호 없는 제1종 스털링 수 c(n,k) 또는 [\begin{smallmatrix}n \\ k\end{smallmatrix}]로 주어진다.

  • '''상승점과 하강점''': 전순서가 주어진 집합 {1, 2, ..., ''n''} 위의 순열 \sigma = \sigma_1\sigma_2\dots\sigma_n에서, \sigma_i < \sigma_{i+1}을 만족하는 위치 ''i'' (1 \le i < n)를 '''상승점'''(ascent)이라고 한다. 반대로 \sigma_i > \sigma_{i+1}을 만족하는 위치 ''i''를 '''하강점'''(descent)이라고 한다. 모든 위치 ''i'' (1 \le i < n)는 상승점이거나 하강점이다.
  • 예를 들어, 순열 3452167은 위치 1(3<4), 2(4<5), 5(1<6), 6(6<7)에서 상승점을 가진다. 위치 3(5>2), 4(2>1)는 하강점이다.
  • ''n''개의 원소로 이루어진 순열 중에서 정확히 ''k''개의 상승점을 갖는 순열의 개수는 오일러리안 수 \textstyle\left\langle{n\atop k}\right\rangle이다. 이 수는 정확히 ''k''개의 하강점을 갖는 순열의 개수와도 같다.

  • '''상승 런''': 순열의 '''상승 런'''(ascending run)은 순열에서 연속적으로 증가하는 극대 부분 수열을 의미한다. 즉, 양쪽 끝에서 더 이상 확장할 수 없는 연속 증가 구간이다. 예를 들어, 순열 2453167의 상승 런은 245, 3, 167이다. 순열이 ''k'' − 1개의 하강점을 가지면, 정확히 ''k''개의 상승 런으로 나뉜다. 따라서 ''k''개의 상승 런을 갖는 ''n''-순열의 개수는 ''k'' − 1개의 하강점을 갖는 순열의 개수와 같으므로 \textstyle\left\langle{n\atop k-1}\right\rangle이다.

  • '''같은 것이 있는 순열'''(multiset permutation영어): 원소의 중복을 허용하는 경우, 이를 '''중복순열''' 또는 '''같은 것이 있는 순열'''이라고 한다. 크기 n의 중복집합 M = n_1\{a_1\} + n_2\{a_2\} + \dots + n_k\{a_k\} (여기서 n = n_1 + n_2 + \dots + n_k이고, a_i는 서로 다른 원소, n_i는 각 원소의 개수)의 순열은 중복집합의 원소를 각각의 중복도만큼 사용하여 순서대로 나열한 것이다. 그 개수는 다항 계수로 주어진다:

:\binom{n}{n_1, n_2, \dots, n_k} = \frac{n!}{n_1! n_2! \dots n_k!}

예를 들어, 영어 단어 "MISSISSIPPI"는 총 11개의 문자로 이루어져 있으며, M 1개, I 4개, S 4개, P 2개로 구성된다. 이 문자들을 배열하는 경우의 수는 다음과 같이 계산된다:

:\binom{11}{1, 4, 4, 2} = \frac{11!}{1! \times 4! \times 4! \times 2!} = 34650

4. 1. 연산

집합 X의 순열들의 집합 \operatorname{Sym}(X)는 함수의 합성을 연산으로 하여 군을 이룬다. 이를 대칭군이라고 부른다.[11] 군의 공리는 다음과 같이 만족된다.

  • 닫힘: 임의의 두 순열 \sigma, \tau \in \operatorname{Sym}(X)에 대하여, 그 합성 \pi = \sigma\tau 역시 X에서 X로 가는 전단사 함수이므로 순열이다. 즉, \pi(x) = \sigma(\tau(x)) 로 정의된다. 합성 연산은 일반적으로 교환법칙이 성립하지 않는다. 즉, \tau\sigma \neq \sigma\tau 인 경우가 많다.[11] 합성 연산은 보통 곱셈 기호(·)나 점 없이 표기한다.
  • 결합 법칙: 함수의 합성은 결합 법칙을 만족하므로, 임의의 순열 \sigma, \tau, \rho에 대해 (\sigma\tau)\rho = \sigma(\tau\rho)가 성립한다.
  • 항등원: 모든 원소 x \in X를 자기 자신으로 보내는 항등 함수 \operatorname{id}_X\colon x\mapsto x는 순열이며, 군의 항등원 역할을 한다. 즉, 모든 순열 \sigma에 대해 \sigma \operatorname{id}_X = \operatorname{id}_X \sigma = \sigma 이다. 항등 순열은 1, \text{id}, 또는 단일 1-순환 (x) 등으로 표기하기도 한다.[10][11]
  • 역원: 모든 순열 \sigma는 전단사 함수이므로 역함수 \sigma^{-1}를 가지며, 이 역함수 역시 X의 순열이다. 즉, \sigma(\sigma^{-1}(x)) = \sigma^{-1}(\sigma(x)) = x 를 만족한다. 이는 군의 역원이다. 명시적으로 \sigma(x) = y 이면 \sigma^{-1}(y) = x 이다.
  • 두 줄 표기법에서는 두 줄의 내용을 서로 바꾸어 역순열을 얻는다. 예를 들어,

\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 2 & 5 & 4 & 3 & 1\end{pmatrix}^{-1}

=\begin{pmatrix}2 & 5 & 4 & 3 & 1\\ 1 & 2 & 3 & 4 & 5 \end{pmatrix}

=\begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 4 & 3 & 2\end{pmatrix}

  • 순환 표기법에서는 각 순환 내 원소들의 순서를 거꾸로 하여 역순열을 얻는다. 예를 들어, \sigma = (126)(35) 이면, 그 역순열은 \sigma^{-1} = (621)(53) 이다.


순열의 합성은, 치환 행렬의 곱에 대응한다


순열 \sigma와 다른 순열 \pi에 의한 공액 변환 \pi\sigma\pi^{-1}을 취하면, 그 결과 역시 순열이며, 순환 구조는 보존된다. 즉, 공액 변환된 순열의 순환 표기법은 원래 순열 \sigma의 순환 표기법에서 각 원소에 \pi를 적용하여 얻는다.

집합 {1, 2, …, ''n''} 위의 순열은 ''n'' × ''n'' 치환 행렬로도 나타낼 수 있다. 순열 \sigma에 대응하는 치환 행렬 M = [m_{ij}]는 i = \sigma(j) 일 때 m_{ij} = 1이고, 그 외의 경우에는 m_{ij} = 0인 행렬이다. 이 표현 방식에서 순열의 합성은 해당하는 치환 행렬의 곱셈과 같다.

4. 2. 반전

순열 \sigma\in\operatorname{Sym}(n)에 대하여, 튜플 (x,y)\in\{1,2,\dotsc,n\}^2이 다음 두 조건을 만족시키면, \sigma의 '''반전'''(反轉, inversion|인버전영어)이라고 한다.

  • \sigma^{-1}(x)<\sigma^{-1}(y)
  • x>y

이는 어떤 두 원소의 순서가 원래의 순서와 반대로 나타나는 것을 의미한다.

다른 관점에서, 순열 \sigma = \sigma_1\sigma_2\dots\sigma_n 에서 ''i'' < ''j'' 이고 \sigma_i > \sigma_j를 만족하는 위치의 쌍 (''i'', ''j'')를 '''전도'''(轉倒)라고 부르기도 한다. 이는 반전과 밀접하게 관련된 개념이다. 예를 들어, 순열 \sigma = 23154는 세 개의 전도 (1, 3), (2, 3), (4, 5)를 가지며, 이는 각각 원소 쌍 (2, 1), (3, 1), (5, 4)에 해당한다. 전도는 두 인접한 위치에서 발생할 때 하강점(descent)이라고 한다 (\sigma_i > \sigma_{i+1}).

순열 \sigma의 모든 반전(또는 전도)의 개수를 '''반전수'''(反轉數, inversion number|인버전 넘버영어)라고 하며, \operatorname{inv\,num}(\sigma) 또는 N(\sigma)로 표기한다. 반전수는 순열의 원소들이 얼마나 뒤섞여 있는지를 나타내는 척도이며, 순열 \sigma와 그 역순열 \sigma^{-1}의 반전수는 같다.

:\operatorname{inv\,num}(\sigma) = \operatorname{inv\,num}(\sigma^{-1})

반전수는 정렬 알고리즘과 관련이 있다. ''k''개의 반전을 가진 순열은 ''k''번의 인접 원소 교환(기본 호환)을 통해 정렬된 순열(항등 순열)로 만들 수 있다. 예를 들어, 버블 정렬이나 삽입 정렬은 각 단계에서 하강점(인접 반전)을 찾아 원소를 교환하여 반전수를 줄여나가는 방식으로 순열을 정렬한다. 반전수가 0이 아니면 항등 순열이 아니므로 적어도 하나의 하강점이 존재한다.

순열 \sigma의 '''반전 벡터'''(反轉-, inversion vector|인버전 벡터영어) \operatorname{inv\,vec}(\sigma)\in\{0,1,\dotsc,n-1\}^{n-1}는 y번째 성분이 값 y보다 크면서 y보다 왼쪽에 나타나는 원소들의 개수인 벡터이다. 즉, 다음과 같다.

:\operatorname{inv\,vec}(\sigma)_y = |\{x\in\{1,2,\dotsc,n\}\colon\sigma^{-1}(x)<\sigma^{-1}(y),\;x>y\}|\qquad y=1,2,\dotsc,n-1

반전수는 반전 벡터의 모든 성분의 합과 같다.

순열의 '''부호'''(符號, sign|사인영어) \sgn\colon\operatorname{Sym}(n)\to\{-1,1\}는 반전수와 다음과 같은 관계를 가진다.

:\sgn(\sigma) = (-1)^{\operatorname{inv\,num}(\sigma)}

부호가 1인 순열을 짝순열, -1인 순열을 홀순열이라고 한다. 부호 함수는 대칭군 \operatorname{Sym}(n)에서 곱셈 군 \{-1, 1\}으로 가는 유일한 군 준동형이며, 인접 원소 교환(기본 호환) \begin{pmatrix} i & i+1 \end{pmatrix}의 부호는 항상 -1이다.

크기 ''n''인 집합의 순열 \sigma의 반전수는 다음 범위를 가진다.

:0 \le \operatorname{inv\,num}(\sigma) \le \binom{n}{2} = \frac{n(n-1)}{2}

반전수는 인접 원소 교환 시 1만큼 변한다. 구체적으로, \sigma에서 ''x''와 ''x''+1 위치의 원소를 교환한 순열 \sigma' = \sigma \begin{pmatrix} x & x+1 \end{pmatrix}에 대해 다음 점화식이 성립한다.

:\operatorname{inv\,num}(\sigma') = \begin{cases} \operatorname{inv\,num}(\sigma)+1 & \sigma(x) < \sigma(x+1) \\ \operatorname{inv\,num}(\sigma)-1 & \sigma(x) > \sigma(x+1) \end{cases}

''n''개의 원소로 이루어진 순열 중 반전수가 정확히 ''k''개인 순열의 개수는 메이혼 수(Mahonian number)로 주어진다. 이 수는 q-계승 [n]_q!의 전개식에서 X^k (또는 q^k)의 계수와 같다.

:[n]_q! = \prod_{m=1}^n \sum_{i=0}^{m-1} X^i = \prod_{m=1}^n (1+X+X^2 + \cdots + X^{m-1})

4. 3. 순환 분해

순열 \sigma\in\operatorname{Sym}(X)가 주어졌을 때, 각 원소 x\in X에 대해 순열 \sigma를 반복적으로 적용하여 얻는 집합 \langle\sigma\rangle(x) = \{\dots, \sigma^{-1}(x), x, \sigma(x), \sigma^2(x), \dots\}를 x의 '''궤도'''(orbit영어)라고 한다. 이러한 궤도들은 전체 집합 X의 분할을 이룬다. 각 궤도에서 순열 \sigma의 작용을 제한하면, 이는 하나의 순환(cycle)이 된다. 구체적으로, 궤도의 크기가 유한하면 유한 순환, 무한하면 무한 순환이 된다.

:\sigma|_{\langle\sigma\rangle(x)}=

\begin{cases}

\begin{pmatrix}\cdots&\sigma^{-1}(x)&x&\sigma(x)&\cdots\end{pmatrix}

&|\langle\sigma\rangle(x)|\ge\aleph_0\\

\begin{pmatrix}x&\sigma(x)&\cdots&\sigma^

4. 4. 호환 분해

유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해 방법은 하나만 있는 것이 아니다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻을 수 있다. 구체적인 분해식의 예는 다음과 같다.

:

\begin{pmatrix}x_1&x_2&\cdots&x_j&\cdots&x_k\end{pmatrix}=

\begin{pmatrix}x_1&x_2&\cdots&x_j\end{pmatrix}

\begin{pmatrix}x_j&x_{j+1}&\cdots&x_k\end{pmatrix}=

\begin{pmatrix}x_1&x_2\end{pmatrix}

\begin{pmatrix}x_2&x_3\end{pmatrix}\cdots

\begin{pmatrix}x_{k-1}&x_k\end{pmatrix}

:\begin{pmatrix}x_1&x_2&\cdots&x_k\end{pmatrix}=

\begin{pmatrix}x_1&x_k\end{pmatrix}

\begin{pmatrix}x_1&x_{k-1}\end{pmatrix}\cdots

\begin{pmatrix}x_1&x_2\end{pmatrix}

유한 집합 위의 임의의 치환은 호환의 곱으로 나타낼 수 있다. 표현 방법은 여러 가지가 존재하지만, 사용된 호환의 개수가 짝수인지 홀수인지는 주어진 치환에 대해 항상 일정하다. 홀순열 분해에 필요한 호환의 개수는 항상 홀수이고, 짝순열 분해에는 항상 짝수이다. 이 불변성은 순열의 홀짝성을 정의하는 데 사용될 수 있으며, 모든 치환을 짝치환 또는 홀치환으로 분류하게 해준다.

유한 집합의 순열을 호환의 곱으로 나타낼 때 필요한 최소 호환의 개수는 그 순열의 감소량과 같다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여 다음 식이 성립한다.

:\operatorname{dec}(\sigma)=\min\{l\in\mathbb N\colon\sigma=

\begin{pmatrix}x_1&y_1\end{pmatrix}\cdots

\begin{pmatrix}x_l&y_l\end{pmatrix},\;x_i,y_i\in\{1,2,\dotsc,n\}\}

또한, 유한 집합의 호환은 항상 인접 호환(adjacent transposition)들의 곱으로 분해할 수 있다. 이 분해 역시 유일하지 않으며, 구체적인 분해식의 예는 다음과 같다.

:

\begin{pmatrix}x&y\end{pmatrix}=

\begin{pmatrix}x&x+1&\cdots&y\end{pmatrix}

\begin{pmatrix}y-1&y-2&\cdots&x\end{pmatrix}=

\begin{pmatrix}x&x+1\end{pmatrix}\cdots

\begin{pmatrix}y-1&y\end{pmatrix}

\begin{pmatrix}y-1&y-2\end{pmatrix}\cdots

\begin{pmatrix}x+1&x\end{pmatrix}

유한 집합의 순열을 인접 호환의 곱으로 나타낼 때 필요한 최소 인접 호환의 개수는 그 순열의 반전수(inversion number)와 같다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여 다음 식이 성립한다.

:\operatorname{inv\,num}(\sigma)=\min\{l\in\mathbb N\colon\sigma=

\begin{pmatrix}x_1&x_1+1\end{pmatrix}\cdots

\begin{pmatrix}x_l&x_l+1\end{pmatrix},\;x_i\in\{1,2,\dotsc,n-1\}\}

''k''개의 전도를 가진 순열을 항등 순열로 만들기 위해서는 최소 ''k''번의 기본 호환(인접 호환)을 적용해야 한다. 버블 정렬이나 삽입 정렬과 같은 정렬 알고리즘은 이러한 원리를 이용하여 원소들을 순서대로 배열한다. 이 과정을 통해 임의의 순열 σ가 기본 호환(인접 호환)들의 곱으로 표현될 수 있음을 알 수 있다.

4. 5. 군론적 성질

군론에서 어떤 집합 ''S'' 위의 '''치환'''은 그 집합에서 자기 자신으로 가는 전단사 함수이다.[10][11] 집합 ''S''의 모든 순열(치환)의 집합은 함수의 합성을 군 연산으로 하여 군을 이루며, 이를 ''S''의 '''대칭군'''이라고 부르고 \operatorname{Sym}(S) 또는 S_n (''S''의 원소 개수가 ''n''일 때)으로 표기한다.[10][11] 대칭군의 군 연산인 순열의 합성은 일반적으로 교환법칙이 성립하지 않는다. 즉, \tau\sigma \neq \sigma\tau인 경우가 많다.

대칭군의 부분군은 '''치환군'''이라고 부른다. 케일리 정리에 따르면, 모든 군은 어떤 집합 위의 치환군과 동형이다. 특히 유한군은 어떤 유한 대칭군의 부분군과 동형이다. 이는 모든 군의 구조가 순열들의 합성으로 표현될 수 있음을 의미한다.

순열 \sigma\in\operatorname{Sym}(X)의 위수는 \sigma를 거듭제곱하여 항등 순열이 되게 하는 최소의 양의 정수이다. 이는 \sigma를 서로소인 순환들의 곱으로 분해했을 때, 각 순환들의 길이의 최소공배수와 같다. 만약 순환 길이들의 집합이 무한하거나, 순환 길이 중 무한한 것이 있다면 위수는 \aleph_0 (무한)이다.[18] 구체적인 공식은 다음과 같다.

:\operatorname{ord}(\sigma)=

\begin{cases}

\operatorname{lcm}_{x\in X}|\langle\sigma\rangle(x)|&\{|\langle\sigma\rangle(x)|\colon x\in X\}\in\mathcal P_{<\aleph_0}(\mathbb Z^+)\\

\aleph_0&\

5. 순열의 수

유한 집합 \{1,2,\dotsc,n\}의 모든 순열의 수는 n의 계승 n!이다.

순열은 '''홀짝성'''(parityeng)에 따라 분류될 수 있다. 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 \sigma를 '''홀순열'''(odd permutationeng)이라고 한다.


  • 반전수 \operatorname{inv\,num}(\sigma)는 홀수이다.
  • 감소량 \operatorname{dec}(\sigma)는 홀수이다.
  • 부호 \sgn(\sigma)=-1


홀순열이 아닌 순열을 '''짝순열'''(even permutationeng)이라고 한다. 즉, 순열 \sigma\in\operatorname{Sym}(n)에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 \sigma를 '''짝순열'''이라고 한다.

  • 반전수 \operatorname{inv\,num}(\sigma)는 짝수이다.
  • 감소량 \operatorname{dec}(\sigma)는 짝수이다.
  • 부호 \sgn(\sigma)=1


n!개의 순열 가운데 홀순열과 짝순열의 수는 다음과 같다.

  • 홀순열의 수:

:\begin{cases}0&n=0,1\\n!/2&n\ge 2\end{cases}

  • 짝순열의 수:

:\begin{cases}1&n=0,1\\n!/2&n\ge 2\end{cases}

5. 1. ''k''-순열

음이 아닌 정수 k가 주어졌을 때, 집합 X의 '''k-순열'''(-順列, k-permutation영어)은 단사 함수 \{1,2,\dotsc,k\}\to X이다. 특히, 유한 집합 X=\{1,2,\dotsc,n\}의 경우 이를 '''n의 k-순열'''이라고 한다. 이 경우, 원래의 유한 순열은 n의 n-순열이다. 풀어 말해, n의 k-순열은 서로 다른 n개의 원소 가운데 중복 없이 k개를 골라서 순서 있게 나열한 것이다. n의 k-순열의 수는 n^{\underline k},{}_nP_k,P_{n,k},P(n,k)와 같이 표기하며, 다음과 같이 하강 계승으로 주어진다.

:n^{\underline k}=n(n-1)(n-2)\cdots(n-k+1)

예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.

:6^{\underline 3}=6\times 5\times 4=120

n의 k-순열의 수와 n의 k-조합의 수(이항 계수)의 관계는 다음과 같다.

:\binom nk=\frac{n^{\underline k}}{k!}

오래된 문헌이나 초급 교과서에서는 '''''n''의 ''k''-순열'''''을 때로는 '''부분 순열''', '''중복 없는 수열''', '''변동''', 또는 '''배열'''이라고 부르기도 한다. 이는 ''n''-집합의 ''k''-원소 부분 집합을 순서대로 배열(목록)한 것을 의미한다. 이러한 ''k''-순열(''k''-배열)의 수는 P^n_k, _nP_k, ^n\!P_k, P_{n,k}, P(n,k), 또는 A^k_n과 같은 다양한 기호로 표시하며,[30] 다음 공식으로 계산한다:

: P(n,k) = \underbrace{n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)}_{k\ \mathrm{factors}}

이 값은 k > n일 때는 0이고, 그 외의 경우에는 다음과 같다.

: \frac{n!}{(n-k)!}.

이 곱셈은 포흐아머 기호 (n)_k 또는 k번째 하강 계승 n^{\underline k}로도 알려져 있다:

P(n,k)={_n} P_k =(n)_k = n^{\underline{k}} .


"순열"이라는 용어의 이러한 사용법은 부분 집합을 의미하는 "조합"이라는 용어와 밀접하게 연관되어 있다. 집합 ''S''의 ''k''-조합은 ''S''에서 원소 ''k''개를 뽑은 부분 집합이며, 조합의 원소는 순서가 없다. ''S''의 ''k''-조합을 가능한 모든 방법으로 순서를 매기면 ''S''의 ''k''-순열이 만들어진다. 따라서 ''n''-집합의 ''k''-조합의 수, ''C''(''n'',''k'')는 ''n''의 ''k''-순열의 수와 다음과 같은 관계를 가진다.

: C(n,k) = \frac{P(n,k)}{P(k,k)}= \frac{n^{\underline{k}}}{k!} = \frac{n!}{(n-k)!\,k!}.

이 수는 일반적으로 \tbinom{n}{k}로 표시되는 이항 계수로도 알려져 있다:

C(n,k)={_n} C_k =\binom{n}{k} .

5. 2. 중복 순열



음이 아닌 정수 k가 주어졌을 때, 집합 X의 k-'''중복 순열'''(重複順列, k-permutation with repetition영어)은 X의 k-튜플을 뜻한다. 특히, 유한 집합 \{1,2,\dotsc,n\}의 k-튜플을 생각할 수 있으며, 이는 풀어 말해 n개의 원소 가운데 중복을 허용하여 k개를 골라서 순서 있게 나열한 것이다. 그 수는 n^k이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 26^3=17576이다.

순서가 지정된 집합 ''S''의 ''k''개의 원소 배열로, 중복이 허용되는 경우, 이를 ''k''-튜플이라고 한다. 이는 때때로 '''중복 순열'''이라고 불리기도 하지만, 일반적인 의미의 순열과는 구별된다. 이는 또한 알파벳 ''S''에 대한 단어 또는 문자열이라고도 불린다. 집합 ''S''가 ''n''개의 원소를 갖는 경우, ''S''에 대한 ''k''-튜플의 개수는 n^k이다.

5. 3. 중복집합 순열

중복집합 순열은 주어진 중복집합의 원소를 모두 사용하여 배열하는 경우이다.


크기 n의 중복집합 ''M''의 '''중복집합 순열'''(multiset permutation영어) 또는 '''같은 것이 있는 순열'''은 중복집합 ''M''의 원소를 순서대로 나열한 것으로, 각 원소는 ''M''에서 해당 원소의 중복도와 정확히 같은 횟수로 나타난다. 예를 들어, 일부 문자가 반복되는 단어의 철자 바꾸기는 중복집합 순열의 한 예시이다.

만약 중복집합 ''M''의 서로 다른 원소들의 중복도가 각각 m_1, m_2, \ldots, m_l이고, 이들의 합(즉, 중복집합 ''M''의 크기)이 ''n'' (n = \sum_{i=1}^l m_i)이라면, ''M''의 중복집합 순열의 수는 다항 계수를 사용하여 다음과 같이 계산할 수 있다.[31]

:

{n \choose m_1, m_2, \ldots, m_l} =

\frac{n!}{m_1!\, m_2!\, \cdots\, m_l!} =

\frac{\left(\sum_{i=1}^l{m_i}\right)!}{\prod_{i=1}^l{m_i!}}.



예를 들어, 단어 MISSISSIPPI는 총 11개의 문자로 이루어져 있으며, 각 문자의 개수는 M 1개, I 4개, S 4개, P 2개이다. 따라서 이 단어의 철자들을 재배열하여 만들 수 있는 서로 다른 순열(철자 바꾸기)의 수는 다음과 같이 계산된다.[32]

:\frac{11!}{1!\, 4!\, 4!\, 2!} = 34650.

5. 4. 원순열

유한 집합 \{1,2,\dotsc,n\}의 '''원순열'''(圓順列, circular permutation영어)은 원소들을 원형으로 배열하는 순열의 한 종류로, 서로 회전하여 같아지는 순열들을 동일한 것으로 간주한다.[33] 일반적인 순열(선형 순열)과 달리 원형 배열에는 특정 시작점이나 끝점이 없으므로, 회전했을 때 겹쳐지는 배열은 하나의 원순열로 취급한다. 이는 n개의 서로 다른 물건을 원형 탁자에 배열하는 경우와 같다. 수학적으로는 선형 순열에서 마지막 요소를 맨 앞으로 옮기는 등의 회전 변환을 통해 동일해지는 순열들을 하나의 동치류로 묶어 정의할 수 있다.

예를 들어, 네 개의 문자 {1, 2, 3, 4}를 원형으로 배열할 때, 다음 네 가지 배열은 회전을 통해 서로 같아지므로 모두 같은 원순열이다.

```

1 4 2 3

4 3 2 1 3 4 1 2

2 3 1 4

```

그러나 단순히 뒤집어서 같아지는 경우(대칭 변환)는 다른 원순열로 본다. 예를 들어 다음 두 배열은 서로 회전해서는 같아질 수 없으므로 다른 원순열이다.

```

1 1

4 3 3 4

2 2

```

서로 다른 n개의 원소로 만들 수 있는 원순열의 개수는 다음과 같다.

:\begin{cases}1&n=0\\(n-1)!&n\ge 1\end{cases}

이는 n개의 원소로 만들 수 있는 전체 선형 순열의 수 n!개를, 각 배열마다 회전하여 중복되는 경우의 수인 n으로 나눈 값이다(n \ge 1). 예를 들어, 시계의 숫자 1부터 12까지를 원형으로 다시 배열하여 만들 수 있는 서로 다른 시계 배열(원순열)의 수는 (12-1)! = 11! = 39,916,800가지이다.

5. 5. 염주 순열

유한 집합 \{1,2,\dotsc,n\}의 '''염주 순열'''(念珠順列) 또는 '''목걸이 순열'''(necklace permutation|넥클리스 퍼뮤테이션영어)은 n개의 원소를 원형으로 배열할 때, 회전하거나 뒤집어서 같아지는 배열을 같은 것으로 취급하는 순열이다. 이는 마치 구슬을 꿰어 만든 목걸이나 염주처럼, 돌리거나 뒤집어도 같은 모양이면 하나로 세는 방식과 같다. 수학적으로는 \{1,2,\dotsc,n\} 위의 오른쪽 작용 \langle\begin{pmatrix}1&2&\cdots&n\end{pmatrix},n+1-\operatorname{id}_n\rangle의 궤도를 의미한다.

염주 순열의 개수는 다음과 같이 계산한다.

:\begin{cases}1&n=0,1,2\\(n-1)!/2&n\ge 3\end{cases}

이 공식은 전체 순열의 수 n!에서, 원형 배열로 인한 중복(n가지 회전)과 뒤집기로 인한 중복(2가지 방향)을 고려하여 총 2n으로 나눈 값 (n-1)!/2과 같다. 단, n=1, 2일 때는 뒤집는 것이 회전과 동일하거나 의미가 없어 예외적으로 1가지 경우만 존재한다.

예를 들어, 서로 다른 7개의 구슬(예: 무지개색 구슬)로 목걸이를 만드는 경우의 수는 (7-1)!/2 = 6!/2 = 720/2 = 360가지이다.

n=1, 2, 3, \dots일 때 염주 순열의 수는 다음과 같다.

:1, 1, 1, 3, 12, 60, 360, 2520, ... (OEIS의 A001710 수열)

6. 역사

오귀스탱 루이 코시 (1789–1857)


''n''개의 요소의 순열의 총 수를 결정하는 규칙은 적어도 1150년경 인도 문화권에서 알려져 있었다. 인도 수학자 바스카라 2세의 저서 ''릴라바티''에는 다음과 같은 구절이 포함되어 있다.



산술 수열의 곱셈은 1부터 시작하여 1씩 증가하고 자릿수까지 계속되며 특정 숫자의 변동이 됩니다.



이는 팩토리얼을 이용한 순열의 수 계산 방법을 설명한 것으로 해석된다.

겉보기에는 관련이 없는 수학적 질문이 순열을 통해 연구된 최초의 사례 중 하나는 1770년경 조제프루이 라그랑주의 연구이다. 라그랑주는 대수 방정식을 연구하면서 방정식의 근들의 순열이 방정식의 풀이 가능성(가해성)과 관련이 있음을 발견했다. 이 방향성은 파올로 루피니가 이어받아 진행하여 5차 이상의 일반적인 대수 방정식에 대한 근의 공식이 존재하지 않는다는 것을 증명하고자 했다.

루피니의 연구는 오귀스탱 루이 코시에게 영향을 주었으며, 코시는 순열에 대한 표기법을 간소화하고 이론을 더욱 발전시켜 『순열론』으로 체계적으로 정리했다. 아벨은 루피니의 논문을 직접 접하지는 못했지만, 코시의 『순열론』을 읽고 루피니의 증명에서 부족했던 대수적 가해성의 원칙을 보완하여 독자적으로 5차 이상의 대수 방정식에는 해의 공식이 없다는 것을 엄밀하게 증명했다(아벨-루피니 정리).

방정식의 근의 순열과 대수적 가해성을 분석한 에바리스트 갈루아는 무엇이 (일변수) 다항식 방정식의 가해와 불가해를 근본적으로 결정하는지를 완전히 기술하는 갈루아 이론에 도달했다. 이 이론은 방정식 근들의 순열 그룹(갈루아 군)의 성질과 방정식의 풀이 가능성을 연결한다. 현대 수학에서도 다양한 문제를 이해하기 위해 관련된 순열을 조사하는 경우가 많이 존재한다.

7. 전산학에서의 응용

순열은 컴퓨터 과학의 여러 분야에서 중요한 역할을 한다. 예를 들어, 3GPP 롱텀 에볼루션(LTE)과 같은 모바일 통신 표준에서 사용되는 터보 코드는 오류 감지 및 수정을 위한 핵심 기술인데, 이 터보 코드 내부의 인터리버라는 구성 요소에 순열이 사용된다. 인터리버는 데이터 비트의 순서를 재배열하여 오류에 대한 저항력을 높이는 역할을 한다.[48]

이러한 응용 분야에서는 특정 조건을 만족하는 순열을 빠르고 효율적으로 생성하는 것이 중요하다. 순열 다항식은 이러한 요구를 충족시키는 한 가지 방법으로 연구되고 있다. 또한, 순열은 데이터베이스나 해시 테이블 등에서 고유한 키 값을 효율적으로 관리하기 위한 고유 순열 해싱에서도 최적의 해싱 방법을 설계하는 기반으로 활용된다.[49]

7. 1. 순열 생성 알고리즘

주어진 값의 시퀀스에 대한 순열을 생성해야 하는 경우가 있다. 이를 위한 알고리즘은 무작위 순열을 생성할지, 아니면 모든 순열을 체계적으로 생성할지에 따라 달라진다.

순열을 나타내는 한 가지 방법은 0 ≤ ''N'' < ''n''!인 정수 ''N''을 이용하는 것이다. 이는 순열을 정렬된 배열(시퀀스)로 표현하고, 숫자와 순열 표현 사이를 변환하는 편리한 방법이 있을 때 가능하다. 이 방식은 임의의 순열을 가장 간결하게 표현할 수 있어 컴퓨터 계산에 유용하다. 변환은 숫자 시퀀스 ''d''''n'', ''d''''n''−1, ..., ''d''2, ''d''1 (여기서 ''d''''i''는 ''i''보다 작은 음이 아닌 정수)를 중간 형태로 사용하여 수행될 수 있다. 첫 번째 단계는 ''N''을 계승 진법으로 표현하는 것이다. 이는 연속하는 자릿수의 기수가 (''n'' − 1)!, (''n'' − 2)!, ..., 2!, 1!인 혼합 진법 표현이다. 두 번째 단계는 이 시퀀스를 레머 코드(Lehmer code) 또는 반전 테이블로 해석하는 것이다.

순열 ''σ''에 대한 '''레머 코드'''에서 숫자 ''d''''n''은 첫 번째 항 ''σ''1에 대한 선택을, 숫자 ''d''''n''−1은 나머지 ''n'' − 1개 요소 중 두 번째 항 ''σ''2에 대한 선택을 나타낸다. 더 정확하게는, 각 ''d''''n''+1−''i''는 항 ''σ''''i''보다 작은 '남은' 요소의 수를 나타낸다. 이 남은 요소들은 나중에 항 ''σ''''j'' (''j'' > ''i'')가 될 것이므로, ''d''''n''+1−''i''는 ''i'' < ''j''이고 ''σ''''i'' > ''σ''''j''인 반전 (''i'', ''j'')의 수를 센다. 순열 ''σ''에 대한 '''반전 테이블'''은 비슷하지만, ''d''''n''+1−''k''는 반전된 순서로 나타나는 두 값 중 더 작은 값으로 ''k'' = ''σ''''j''가 발생하는 반전 (''i'', ''j'')의 수를 센다.

두 인코딩은 ''n'' × ''n'' '''로테 다이어그램'''(하인리히 아우구스트 로테의 이름을 따서 명명됨)으로 시각화할 수 있다. 이 다이어그램에서 (''i'', ''σ''''i'')의 점은 순열의 항목을 표시하고, (''i'', ''σ''''j'')의 교차점은 반전 (''i'', ''j'')을 표시한다. 레머 코드는 행의 교차점 수를, 반전 테이블은 열의 교차점 수를 나열한다.

''σ'' = (6, 3, 8, 1, 4, 9, 7, 2, 5)에 대한 로테 다이어그램
i \ σi123456789레머 코드
1××××וd9 = 5
2×וd8 = 2
3××××וd7 = 5
4•d6 = 0
5וd5 = 1
6××וd4 = 3
7×וd3 = 2
8•d2 = 0
9•d1 = 0
반전 테이블361240200



레머 코드를 순열로 변환하려면, 주어진 집합 ''S''의 요소를 오름차순으로 나열하고, ''i''를 1부터 ''n''까지 증가시키면서 목록에서 ''d''''n''+1−''i''번째 요소를 ''σ''''i''로 선택하고 목록에서 제거한다. 반전 테이블을 순열로 변환하려면, 처음에 비어 있는 시퀀스에 ''S''의 요소를 가장 큰 것부터 가장 작은 것 순서로 삽입하며, 각 단계에서 숫자 ''d''는 해당 요소 앞에 이미 시퀀스에 있는 요소의 수를 나타낸다.

계승 진법 표현의 숫자 합은 순열의 반전 수를 나타내며, 합의 패리티는 순열의 부호를 제공한다.

''n''의 순열을 생성하는 명백한 방법은 레머 코드 값을 생성하고 이를 순열로 변환하는 것이지만, 변환 단계는 효율적으로 구현하기 어렵다. 배열이나 연결 리스트를 사용하면 약 ''n''2/4 연산이 필요하다. 더 효율적인 방법들이 존재한다.

=== 무작위 순열 생성 ===

피셔-예이츠 셔플(Fisher–Yates shuffle)은 주어진 ''n''개 값의 무작위 순열을 생성하는 효율적인 알고리즘이다.[37] 이 알고리즘은 ''n''!개의 가능한 정수 시퀀스 ''d''1, ''d''2, ..., ''d''''n'' (여기서 0 ≤ ''d''''i'' < ''i'') 중 하나를 무작위로 생성하고, 이를 전단사 대응을 통해 순열으로 변환하는 아이디어에 기반한다. 레머 코드를 직접 사용하는 대신, 피셔-예이츠 셔플은 요소를 선택한 후 마지막 남은 요소와 교환하는 방식을 사용한다.

배열 `a[0], a[1], ..., a[n − 1]`의 무작위 순열을 생성하는 피셔-예이츠 셔플 알고리즘은 다음과 같다.

: '''for''' ''i'' '''from''' ''n'' '''downto''' 2 '''do'''

:: ''di'' ← { 0, ..., ''i'' − 1 }에서 무작위 정수 선택

:: '''swap''' ''a''[''di''] and ''a''[''i'' − 1]

이 알고리즘은 배열 `a[i] = i` 초기화와 결합될 수도 있다.

: '''for''' ''i'' '''from''' 0 '''to''' ''n''−1 '''do'''

:: ''d''''i''+1 ← { 0, ..., ''i'' }에서 무작위 정수 선택

:: ''a''[''i''] ← ''a''[''d''''i''+1]

:: ''a''[''d''''i''+1] ← ''i''

피셔-예이츠 셔플은 본질적으로 순차적이지만, 분할 정복 절차를 통해 병렬로 동일한 결과를 얻을 수도 있다.[38]

=== 체계적 순열 생성 ===

주어진 시퀀스의 모든 순열을 체계적으로 생성하는 여러 방법이 있다.[39]

==== 사전식 순서 ====

고전적인 방법 중 하나는 사전식 순서로 다음 순열을 찾는 것이다. 이 방법은 반복되는 값이 있는 경우에도 각 고유한 멀티셋 순열을 한 번만 생성한다. 14세기 인도의 나라야나 판디트가 고안했으며 자주 재발견되었다.

다음 알고리즘은 주어진 순열 다음에 오는 사전식 순서의 순열을 생성한다.

# ''a''[''k''] < ''a''[''k'' + 1]을 만족하는 가장 큰 인덱스 ''k''를 찾는다. 이런 인덱스가 없으면 마지막 순열이다.

# ''a''[''k''] < ''a''[''l'']을 만족하는 ''k''보다 큰 가장 큰 인덱스 ''l''을 찾는다.

# ''a''[''k'']와 ''a''[''l'']의 값을 바꾼다.

# ''a''[''k'' + 1]부터 마지막 요소 ''a''[''n'']까지의 시퀀스를 뒤집는다.

예를 들어, 시퀀스 [1, 2, 3, 4] (0부터 시작하는 인덱스)가 주어지면,

# ''k'' = 2 (''a''[2] = 3 < ''a''[3] = 4)

# ''l'' = 3 (''a''[2] = 3 < ''a''[3] = 4)

# ''a''[2]와 ''a''[3]을 바꿔 [1, 2, 4, 3]을 만든다.

# ''a''[3]부터 마지막 요소까지 뒤집는다 (여기서는 변화 없음).

결과: [1, 2, 4, 3]

이 방법은 평균적으로 순열당 약 3번의 비교와 1.5번의 교환을 사용한다.[40]

==== 최소 변경 순서 (인접 교환) ====

Steinhaus–Johnson–Trotter 알고리즘과 Heap의 알고리즘은 모든 순열을 생성하며, 연속된 두 순열은 인접한 두 값의 교환만으로 서로 달라진다는 특징이 있다. 이를 "plain changes"라고도 부른다. 이 방식의 장점은 한 순열에서 다음 순열로의 변화가 적어 순열당 상수 시간 내에 구현할 수 있다는 점이다.


  • Steinhaus–Johnson–Trotter 알고리즘: 각 단계에서 가장 큰 이동 가능한 정수를 찾아 방향대로 이동시킨다.
  • Heap의 알고리즘: 로버트 세지윅은 1977년에 이 알고리즘이 순열 생성에 가장 빠른 알고리즘 중 하나라고 평가했다.[39] 이 알고리즘은 재귀적으로 또는 반복적으로 구현될 수 있으며, 각 단계에서 어떤 두 요소를 교환할지 제어하는 규칙을 사용한다.[41]


==== 기타 알고리즘 ====



길이 ''n''=4인 순열을 생성하는 다양한 알고리즘의 출력 예시는 위 그림과 같다. 주요 알고리즘은 다음과 같다.

# 사전식 순서

# Steinhaus–Johnson–Trotter 알고리즘

# Heap의 알고리즘

# Ehrlich의 스타-전치 알고리즘: 각 단계에서 첫 번째 항목이 이후 항목과 교환된다.

# Zaks의 접두사 반전 알고리즘[43]: 각 단계에서 현재 순열의 접두사가 반전된다.

# Sawada-Williams 알고리즘[44]: 각 순열은 이전 순열과 한 위치의 순환 왼쪽 이동 또는 처음 두 항목의 교환으로 다르다.

# Corbett의 알고리즘[45]: 각 순열은 이전 순열과 일부 접두사의 한 위치의 순환 왼쪽 이동으로 다르다.

# 단일 트랙 순서[46]: 각 열(순열의 특정 위치)은 다른 열의 순환 이동이다.

# 단일 트랙 그레이 코드[46]: 단일 트랙 순서이면서 연속된 순열은 하나 또는 두 개의 교환만으로 다르다.

# 중첩된 스왑 알고리즘: 중첩된 부분 그룹 ''S''''k'' ⊂ ''S''''k''+1과 관련된 단계에서 생성되며, 각 순열은 이전 순열에 왼쪽 전치 곱셈을 수행하여 얻는다.[47] 이 알고리즘은 인덱스의 계승 진법과 연결되며, 특정 구조(중첩)를 활용하여 효율적인 생성이 가능하다. 교환 연산은 계산 시간이 짧고, 각 순열 생성에 하나의 교환만 필요하므로 효율적이다. 또한, 특정 인덱스의 순열로 직접 이동하는 것이 가능하여 시간을 절약할 수 있다.

참조

[1] 서적 1969
[2] 서적 1968
[3] 서적 1970
[4] 서적 A History of Greek Mathematics https://www.worldcat[...] Dover Publications 1981
[5] 간행물 An Account of Early Statistical Inference in Arab Cryptology 2011-11-01
[6] 간행물 The Roots of Combinatorics
[7] 간행물 An application of the theory of permutations in breaking the Enigma cipher https://eudml.org/do[...] 1980
[8] 웹사이트 CMSC 28400 Introduction to Cryptography Autumn 2019 - Notes #2: Permutations and Enigma https://people.cs.uc[...] 2019
[9] 서적 Mathematics: A Discrete Introduction Cengage Learning 2020-02-05
[10] 서적 2002
[11] 서적 1990
[12] 서적 The Symmetries of Things A K Peters 2008
[13] 웹사이트 Permutation notation - Wikiversity https://en.wikiversi[...] 2024-08-04
[14] 간행물 Mémoire Sur le Nombre des Valeurs qu'une Fonction peut acquérir, lorsqu'on y permute de toutes les manières possibles les quantités qu'elle renferme https://babel.hathit[...] 1815-01
[15] 서적 The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory https://books.google[...] Courier Dover Publications
[16] 서적 1990
[17] 서적 1987
[18] 서적 1959
[19] 서적 2012
[20] 서적 Enumerative Combinatorics: Volume I, Second Edition Cambridge University Press
[21] 서적 A Course in Enumeration https://archive.org/[...] Springer GTM 238
[22] 서적 Patterns in Permutations and Words Springer Science & Business Media
[23] 서적 Permutation groups and combinatorial structures Cambridge University Press
[24] 서적 Permutation Groups https://archive.org/[...] Springer
[25] 서적 Permutation groups https://archive.org/[...] Cambridge University Press
[26] 간행물 A compact representation of permutation groups
[27] 웹사이트 Combinations and Permutations https://www.mathsisf[...] 2020-09-10
[28] 웹사이트 Permutation https://mathworld.wo[...] 2020-09-10
[29] 서적 1937
[30] 서적 Enumerative Combinatorics https://books.google[...] CRC Press
[31] 서적 2010
[32] 서적 2010
[33] 서적 2010
[34] 서적 The Symmetric Group Springer 2001
[35] 서적 1959
[36] 웹사이트 15 – puzzle http://mathworld.wol[...] Wolfram Research, Inc. 2014-10-04
[37] 서적 Statistical tables for biological, agricultural and medical research Oliver & Boyd
[38] 뉴스 Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation.
[39] 간행물 Permutation generation methods http://www.math.uiow[...]
[40] 웹사이트 std::next_permutation http://en.cppreferen[...] 2017-12-04
[41] 간행물 Permutations by Interchanges
[42] 웹사이트 Generate permutations http://combos.org/pe[...] 2019-05-29
[43] 간행물 A new algorithm for generation of permutations
[44] conference A Hamilton path for the sigma-tau problem Society for Industrial and Applied Mathematics 2018
[45] 간행물 Rotator graphs: An efficient topology for point-to-point multiprocessor networks
[46] 서적 Matters Computational. Ideas, Algorithms, Source Code Springer 2011
[47] 서적 Quickly Handling Big Permutations priv. comm.
[48] 웹사이트 3GPP TS 36.212 http://www.3gpp.org/[...]
[49] 간행물 Unique permutation hashing
[50] 문서 The roots of combinatorics


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com