순열

수학에서 순열(順列, , ) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다. 개의 원소에 대한 순열의 수는 의 계승

과 같다.

주어진 집합의 순열은 함수의 합성에 따라 대칭군이라고 불리는 군을 이룬다. 이와 같이 주어진 집합의 전부 또는 일부 순열들로 구성된 군(즉, 대칭군의 부분군)을 순열군(順列群, )이라고 일컫기도 한다. 예를 들어, 모든 짝순열의 집합은 대칭군의 부분군이며, 이를 교대군이라고 한다.

조합론에서는 더 많은 순열의 개념들이 사용된다. 예컨대 개의 원소에서 개의 원소를 골라 배열하는 방법들의 가짓수는 하강 계승

과 같다.

정의 
집합 의 순열은 전단사 함수 이다. 유한 집합 의 순열 은 다음과 같이 표를 통해 표기할 수 있다.

모든 의 순열은 함수의 합성에 따라 군을 이루며, 이를 의 대칭군  또는 이라고 한다. 유한 집합 의 순열의 대칭군은  또는 으로 표기한다.

순환 
양의 정수 가 주어졌을 때, 집합 의 길이 의 순환(-循環, ) 은 다음과 같은 꼴의 순열이다. (여기서 는 서로 다른 원소이다.)

또한, 길이 의 순환(-循環, ) 또는 무한 순환(無限循環, ) 은 다음과 같은 꼴의 순열이다. (여기서 는 서로 다른 원소이다.)

특히, 호환(互換, ) 은 2-순환 이다. 특히, 유한 집합 의 인접 호환(隣接互換, ) 은 인접한 두 수에 대한 호환 이다.

반전 
순열 에 대하여, 튜플 이 다음 두 조건을 만족시키면, 의 반전(反轉 )이라고 한다.
 
 
또한, 의 반전 벡터(反轉-, ) 는 번째 성분이 로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.

또한, 의 반전수(反轉數, )  또는 는 의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.

궤도 
순열 의 순환군 은 의 왼쪽에서 자연스럽게 작용한다. 즉, 가 에 작용한 결과는 이다. 이 작용의 각 궤도  ()를 의 궤도(軌道, )라고 한다.

순열 의 감소량(減少量, ) 는 에서 의 궤도의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 를 몇 차 대칭군의 원소로 여기는지와 무관하다.)

부호 
순열의 부호(符號, ) 은 다음 조건을 만족시키는 유일한 군 준동형이다.

구체적으로, 의 부호 는 다음의 두 값과 같다.

홀짝성 
반전수·감소량·부호를 통해 유한 집합의 순열의 홀짝성(-性, )을 정의할 수 있다. 순열 에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 를 홀순열(-順列, )이라고 한다.
 는 홀수이다.
 는 홀수이다.
 
홀순열이 아닌 순열을 짝순열(-順列, )이라고 한다. 즉, 순열 에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 를 짝순열이라고 한다.
 는 짝수이다.
 는 짝수이다.

순열의 수 
유한 집합 의 모든 순열의 수는 의 계승 이다. 이들 가운데 홀순열의 수는 다음과 같다.

또한, 짝순열의 수는 다음과 같다.

순열이 고정점을 갖지 않는다면, 이 순열을 완전 순열이라고 한다. 유한 집합 의 완전 순열의 수는 준계승 으로 주어진다.

유한 집합 의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 교대 순열(交代順列, )이라고 한다. 교대 순열의 수 은 점화식을 통해 주어진다.

조합론에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.

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

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

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

중복 순열 
음이 아닌 정수 가 주어졌을 때, 집합 의 -중복 순열(重複順列, )은 의 -튜플을 뜻한다. 특히, 유한 집합 의 -튜플을 생각할 수 있으며, 이는 풀어 말해 개의 원소 가운데 중복이 가능한 개를 골라서 순서 있게 나열한 것이다. 그 수는 이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 이다.

중복집합 순열 

크기 의 중복집합 의 중복집합 순열(重複集合順列, ) 또는 같은 것이 있는 순열(-順列)은 다음 조건을 만족시키는 함수 이다.

풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수로 주어진다.

예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철의 수는 다음과 같다.

원순열 
유한 집합 의 원순열(圓順列, )은 의  위의 오른쪽 작용의 궤도를 뜻한다. 이는 의 -순환(즉, 의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.

이는 원래의 에서 겹치는 배수인 을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 이다.

염주 순열 
유한 집합 의 염주 순열(念珠順列) 또는 목걸이 순열()은 의  위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.

이는 원래의 에서 겹치는 배수인 을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 이다. 처음 몇 염주 순열의 수는 다음과 같다. ()
1, 1, 1, 3, 12, 60, 360, 2520, ...

성질

연산에 대한 닫힘 
집합 의 순열의 집합 는 군을 이룬다. 즉, 다음이 성립한다.
 항등 함수 는 의 순열이다. (이는 군의 항등원이다.)
 임의의 의 순열 에 대하여, 그 합성  역시 의 순열이다. (이는 군의 곱셈이며, 결합 법칙을 만족한다.)
 임의의 의 순열 에 대하여, 그 역  역시 의 순열이다. (이는 군의 역원 연산이다.)

반전수 
유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.

또한, 다음과 같은 점화식이 성립한다.

또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.

순환 분해 
순열 의 궤도  ()들은 의 분할을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.

만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, 는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, 의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 의 순환 분해(循環分解, )라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수

와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 의 순환 분해는 구체적으로 다음과 같다.

호환 분해 
유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.

홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.

유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 에 대하여, 다음이 성립한다.

인접 호환 분해 
유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.

유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 에 대하여, 다음이 성립한다.

군론적 성질 
순열 의 위수는 다음과 같다.

특히, 순환의 위수는 그 길이와 같다.

대칭군 의 켤레류는 를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 에 대하여, 다음 두 조건이 서로 동치이다.
 는 서로 켤레이다.
 의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다.
대칭군 의 켤레류는 의 분할과 자연스럽게 일대일 대응한다. 즉, 순열 에 대하여, 다음 두 조건이 서로 동치이다.
 는 서로 켤레이다.
 의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다.
유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.
 항등 함수는 짝순열이다.
 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다.
 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다.
달리 말해, 순열의 부호 함수 는 군 준동형이다. 즉, 다음이 성립한다.

이에 따라, 짝순열들은 대칭군의 부분군 을 이루며, 이를 교대군이라고 한다. 사실, 교대군은 이 부호 함수의 핵이므로, 대칭군의 정규 부분군이다.

홀순열의 집합은 부분군이 아니다. 또한, 의 경우 홀순열이 존재하지 않는다. 그러나, 의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류이다.

예 
순열의 합성의 한 가지 예는 다음과 같다.

순열의 역의 한 가지 예는 다음과 같다.

순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.

순열의 홀짝성의 몇 가지 예는 다음과 같다.
 항등 함수는 짝순열이다.
 호환은 홀순열이다.
 짝수 길이의 순환은 홀순열이다.
 홀수 길이의 순환은 항상 짝순열이다.
크기 3의 대칭군 의 켤레류는 다음과 같다.

이들에 대응하는 3의 분할은 각각 다음과 같다.

순열의 반전수의 몇 가지 예는 다음과 같다.

관련 개념

순열 행렬 

유한 집합 의 순열은  순열 행렬과 자연스럽게 일대일 대응한다.

같이 보기 
 스테인하우스-존슨-트로터 알고리즘

외부 링크