순열

수학에서 순열(順列, , ) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 정의역과 공역이 같은 전단사 함수이다. formula_1개의 원소에 대한 순열의 수는 formula_1의 계승
과 같다.
주어진 집합의 순열은 함수의 합성에 따라 대칭군이라고 불리는 군을 이룬다. 이와 같이 주어진 집합의 전부 또는 일부 순열들로 구성된 군(즉, 대칭군의 부분군)을 순열군(順列群, )이라고 일컫기도 한다. 예를 들어, 모든 짝순열의 집합은 대칭군의 부분군이며, 이를 교대군이라고 한다.
조합론에서는 더 많은 순열의 개념들이 사용된다. 예컨대 formula_1개의 원소에서 formula_5개의 원소를 골라 배열하는 방법들의 가짓수는 하강 계승
과 같다.
정의.
집합 formula_7의 순열은 전단사 함수 formula_8이다. 유한 집합 formula_9의 순열 formula_10은 다음과 같이 표를 통해 표기할 수 있다.
모든 formula_7의 순열은 함수의 합성에 따라 군을 이루며, 이를 formula_7의 대칭군 formula_14 또는 formula_15이라고 한다. 유한 집합 formula_9의 순열의 대칭군은 formula_17 또는 formula_18으로 표기한다.
순환.
양의 정수 formula_5가 주어졌을 때, 집합 formula_7의 길이 formula_5의 순환(-循環, ) formula_22은 다음과 같은 꼴의 순열이다. (여기서 formula_23는 서로 다른 원소이다.)
또한, 길이 formula_26의 순환(-循環, ) 또는 무한 순환(無限循環, ) formula_27은 다음과 같은 꼴의 순열이다. (여기서 formula_23는 서로 다른 원소이다.)
특히, 호환(互換, ) formula_31은 2-순환 formula_32이다. 특히, 유한 집합 formula_9의 인접 호환(隣接互換, ) formula_34은 인접한 두 수에 대한 호환 formula_35이다.
반전.
순열 formula_36에 대하여, 튜플 formula_37이 다음 두 조건을 만족시키면, formula_10의 반전(反轉 )이라고 한다.
또한, formula_10의 반전 벡터(反轉-, ) formula_42는 formula_43번째 성분이 formula_43로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.
또한, formula_10의 반전수(反轉數, ) formula_47 또는 formula_48는 formula_10의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.
궤도.
순열 formula_50의 순환군 formula_51은 formula_7의 왼쪽에서 자연스럽게 작용한다. 즉, formula_10가 formula_54에 작용한 결과는 formula_55이다. 이 작용의 각 궤도 formula_56 (formula_54)를 formula_10의 궤도(軌道, )라고 한다.
순열 formula_36의 감소량(減少量, ) formula_60는 formula_1에서 formula_10의 궤도의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 formula_10를 몇 차 대칭군의 원소로 여기는지와 무관하다.)
부호.
순열의 부호(符號, ) formula_65은 다음 조건을 만족시키는 유일한 군 준동형이다.
구체적으로, formula_10의 부호 formula_68는 다음의 두 값과 같다.
홀짝성.
반전수·감소량·부호를 통해 유한 집합의 순열의 홀짝성(-性, )을 정의할 수 있다. 순열 formula_36에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 formula_10를 홀순열(-順列, )이라고 한다.
홀순열이 아닌 순열을 짝순열(-順列, )이라고 한다. 즉, 순열 formula_36에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 formula_10를 짝순열이라고 한다.
순열의 수.
유한 집합 formula_9의 모든 순열의 수는 formula_1의 계승 formula_82이다. 이들 가운데 홀순열의 수는 다음과 같다.
또한, 짝순열의 수는 다음과 같다.
순열이 고정점을 갖지 않는다면, 이 순열을 완전 순열이라고 한다. 유한 집합 formula_9의 완전 순열의 수는 준계승 formula_86으로 주어진다.
유한 집합 formula_9의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 교대 순열(交代順列, )이라고 한다. 교대 순열의 수 formula_88은 점화식을 통해 주어진다.
조합론에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.
"k"-순열.
음이 아닌 정수 formula_5가 주어졌을 때, 집합 formula_7의 formula_5-순열(-順列, )은 단사 함수 formula_92이다. 특히, 유한 집합 formula_93의 경우 이를 formula_1의 formula_5-순열이라고 한다. 이 경우, 원래의 유한 순열은 formula_1의 formula_1-순열이다. 풀어 말해, formula_1의 formula_5-순열은 서로 다른 formula_1개의 원소 가운데 중복 없이 formula_5개를 골라서 순서 있게 나열한 것이다. formula_1의 formula_5-순열의 수는 formula_104와 같이 표기하며, 다음과 같이 하강 계승으로 주어진다.
예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.
formula_1의 formula_5-순열의 수와 formula_1의 formula_5-조합의 수(이항 계수)의 관계는 다음과 같다.
중복 순열.
음이 아닌 정수 formula_5가 주어졌을 때, 집합 formula_7의 formula_5-중복 순열(重複順列, )은 formula_7의 formula_5-튜플을 뜻한다. 특히, 유한 집합 formula_9의 formula_5-튜플을 생각할 수 있으며, 이는 풀어 말해 formula_1개의 원소 가운데 중복이 가능한 formula_5개를 골라서 순서 있게 나열한 것이다. 그 수는 formula_121이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 formula_122이다.
중복집합 순열.
크기 formula_1의 중복집합 formula_124의 중복집합 순열(重複集合順列, ) 또는 같은 것이 있는 순열(-順列)은 다음 조건을 만족시키는 함수 formula_125이다.
풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수로 주어진다.
예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철의 수는 다음과 같다.
원순열.
유한 집합 formula_9의 원순열(圓順列, )은 formula_130의 formula_17 위의 오른쪽 작용의 궤도를 뜻한다. 이는 formula_9의 formula_1-순환(즉, formula_134의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 formula_1개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.
이는 원래의 formula_82에서 겹치는 배수인 formula_1을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 formula_139이다.
염주 순열.
유한 집합 formula_9의 염주 순열(念珠順列) 또는 목걸이 순열()은 formula_141의 formula_9 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 formula_1개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.
이는 원래의 formula_82에서 겹치는 배수인 formula_146을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 formula_147이다. 처음 몇 염주 순열의 수는 다음과 같다. (formula_148)
성질.
연산에 대한 닫힘.
집합 formula_7의 순열의 집합 formula_14는 군을 이룬다. 즉, 다음이 성립한다.
반전수.
유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.
또한, 다음과 같은 점화식이 성립한다.
또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.
순환 분해.
순열 formula_50의 궤도 formula_56 (formula_54)들은 formula_7의 분할을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.
만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, formula_10는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, formula_10의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 formula_10의 순환 분해(循環分解, )라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수
와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 formula_36의 순환 분해는 구체적으로 다음과 같다.
호환 분해.
유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.
홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.
유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 formula_36에 대하여, 다음이 성립한다.
인접 호환 분해.
유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.
유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 formula_36에 대하여, 다음이 성립한다.
군론적 성질.
순열 formula_50의 위수는 다음과 같다.
특히, 순환의 위수는 그 길이와 같다.
대칭군 formula_14의 켤레류는 formula_188를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 formula_189에 대하여, 다음 두 조건이 서로 동치이다.
대칭군 formula_17의 켤레류는 formula_1의 분할과 자연스럽게 일대일 대응한다. 즉, 순열 formula_194에 대하여, 다음 두 조건이 서로 동치이다.
유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.
달리 말해, 순열의 부호 함수 formula_65는 군 준동형이다. 즉, 다음이 성립한다.
이에 따라, 짝순열들은 대칭군의 부분군 formula_201을 이루며, 이를 교대군이라고 한다. 사실, 교대군은 이 부호 함수의 핵이므로, 대칭군의 정규 부분군이다.
홀순열의 집합은 부분군이 아니다. 또한, formula_203의 경우 홀순열이 존재하지 않는다. 그러나, formula_204의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류이다.
예.
순열의 합성의 한 가지 예는 다음과 같다.
순열의 역의 한 가지 예는 다음과 같다.
순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.
순열의 홀짝성의 몇 가지 예는 다음과 같다.
크기 3의 대칭군 formula_208의 켤레류는 다음과 같다.
이들에 대응하는 3의 분할은 각각 다음과 같다.
순열의 반전수의 몇 가지 예는 다음과 같다.
관련 개념.
순열 행렬.
유한 집합 formula_9의 순열은 formula_219 순열 행렬과 자연스럽게 일대일 대응한다.