순열
수학에서, 순열(順列, , ) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역과 공역이 같은 일대일 대응이다. formula_1개의 원소의 순서를 뒤섞는 순열의 개수는 formula_1의 계승 formula_3와 같다. 즉, formula_1 이하의 양의 정수들을 곱한 값이다.
임의의 집합을 어떤 순열에 따라 뒤섞은 뒤 다른 어떤 순열에 따라 뒤섞은 결과는 새로운 어떤 순열에 따라 뒤섞은 결과와 같다. 즉, 임의의 두 순열에 대하여, 그 합성 역시 순열이며, 임의의 집합의 순열들은 이러한 합성 연산 아래 대칭군이라는 군을 이룬다. 모든 원소가 순열인 군, 다시 말해 대칭군의 부분군을 순열군(順列群, ) 또는 치환군(置換群)이라고 한다. 순열군은 여러 가지 집합 위에 자연스러운 군의 작용을 주며, 이는 그 집합의 구조를 뒤섞는다.
조합론에선 이와 다른 순열의 여러 가지 정의가 사용된다. 가장 자주 쓰이는 하나는 임의의 집합에서 일정 개수의 원소를 골라 순서를 뒤섞는 연산이다. formula_1개의 원소에서 formula_6개의 원소를 골라 순서를 뒤섞는 연산을 formula_1의 formula_6-순열(-順列, )이라고 하며, 그 개수는 하강 계승 formula_9와 같다. 즉, formula_1 이하의 정수들 가운데 가장 큰 formula_6개를 곱한 값이다.
집합 formula_12의 순열은 전단사 함수 formula_13이다. 특히, 유한 집합 formula_14의 순열 formula_15를 다음과 같이 표기한다.
모든 formula_12의 순열이 함수의 합성에 따라 이루는 군 formula_18 또는 formula_19를 formula_12의 대칭군이라고 한다. 이는 집합의 크기에 따라 완전히 분류되며, 특히 기수 formula_21에 대응하는 대칭군 formula_22 또는 formula_23를 formula_21차 대칭군이라고 한다. 임의의 집합의 순열은 그 밖의 모든 원소를 고정점으로 여길 경우 자연스럽게 더 큰 집합의 순열이 된다. 즉, 임의의 formula_25에 대하여, 자연스러운 동형에 따라 formula_26이다. 특히, formula_27이다.
양의 정수 formula_6가 주어졌을 때, 집합 formula_12의 길이 formula_6의 순환(-循環, ) formula_31은 다음과 같은 꼴의 순열이다. (여기서 formula_32는 서로 다른 원소이다.)
또한, 길이 formula_35의 순환(-循環, ) 또는 무한 순환(無限循環, ) formula_36은 다음과 같은 꼴의 순열이다. (여기서 formula_32는 서로 다른 원소이다.)
특히, 호환(互換, ) formula_40은 2-순환 formula_41이다. 특히, 유한 집합 formula_14의 인접 호환(隣接互換, ) formula_43은 인접한 두 수에 대한 호환 formula_44이다.
순열 formula_45에 대하여, 튜플 formula_46이 다음 두 조건을 만족시키면, formula_15의 반전(反轉 )이라고 한다.
또한, formula_15의 반전 벡터(反轉-, ) formula_51는 formula_52번째 성분이 formula_52로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.
또한, formula_15의 반전수(反轉數, ) formula_56 또는 formula_57는 formula_15의 모든 반전의 개수이다. 즉, 반전 벡터의 모든 성분의 합이다.
순열 formula_59의 순환군 formula_60은 formula_12의 왼쪽에서 자연스럽게 작용한다. 즉, formula_15가 formula_63에 작용한 결과는 formula_64이다. 이 작용의 각 궤도 formula_65 (formula_63)를 formula_15의 궤도(軌道, )라고 한다.
순열 formula_45의 감소량(減少量, ) formula_69는 formula_1에서 formula_15의 궤도의 개수를 뺀 것이다. 즉, 이는 다음과 같다. (이는 formula_15를 몇 차 대칭군의 원소로 여기는지와 무관하다.)
순열의 부호(符號, ) formula_74은 다음 조건을 만족시키는 유일한 군 준동형이다.
구체적으로, formula_15의 부호 formula_77는 다음의 두 값과 같다.
반전수·감소량·부호를 통해 유한 집합의 순열의 홀짝성(-性, )을 정의할 수 있다. 순열 formula_45에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 formula_15를 홀순열(-順列, )이라고 한다.
홀순열이 아닌 순열을 짝순열(-順列, )이라고 한다. 즉, 순열 formula_45에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 formula_15를 짝순열이라고 한다.
유한 집합 formula_14의 모든 순열의 수는 formula_1의 계승 formula_3이다. 이들 가운데 홀순열의 수는 다음과 같다.
또한, 짝순열의 수는 다음과 같다.
순열이 고정점을 갖지 않는다면, 이 순열을 완전 순열이라고 한다. 유한 집합 formula_14의 완전 순열의 수는 준계승 formula_95으로 주어진다.
유한 집합 formula_14의 순열의 항이 번갈아 가면서 커졌다 작아졌다 (또는 작아졌다 커졌다) 하면, 이 순열을 교대 순열(交代順列, )이라고 한다. 교대 순열의 수 formula_97은 점화식을 통해 주어진다.
조합론에서는 조금 더 일반화된 순열의 수가 연구되며, 이는 다음과 같다.
음이 아닌 정수 formula_6가 주어졌을 때, 집합 formula_12의 formula_6-순열(-順列, )은 단사 함수 formula_102이다. 특히, 유한 집합 formula_103의 경우 이를 formula_1의 formula_6-순열이라고 한다. 이 경우, 원래의 유한 순열은 formula_1의 formula_1-순열이다. 풀어 말해, formula_1의 formula_6-순열은 서로 다른 formula_1개의 원소 가운데 중복 없이 formula_6개를 골라서 순서 있게 나열한 것이다. formula_1의 formula_6-순열의 수는 formula_114와 같이 표기하며, 다음과 같이 하강 계승으로 주어진다.
예를 들어, 6곡의 노래 가운데 3곡을 골라 재생 목록을 만드는 방법의 수는 다음과 같다.
formula_1의 formula_6-순열의 수와 formula_1의 formula_6-조합의 수(이항 계수)의 관계는 다음과 같다.
음이 아닌 정수 formula_6가 주어졌을 때, 집합 formula_12의 formula_6-중복 순열(重複順列, )은 formula_12의 formula_6-튜플을 뜻한다. 특히, 유한 집합 formula_14의 formula_6-튜플을 생각할 수 있으며, 이는 풀어 말해 formula_1개의 원소 가운데 중복이 가능한 formula_6개를 골라서 순서 있게 나열한 것이다. 그 수는 formula_131이다. 예를 들어, 26개의 알파벳으로 구성된 3글자 단어의 수는 formula_132이다.
크기 formula_1의 중복집합 formula_134의 중복집합 순열(重複集合順列, ) 또는 같은 것이 있는 순열(-順列)은 다음 조건을 만족시키는 함수 formula_135이다.
풀어 말해, 중복집합 순열은 중복집합의 각 원소를 그 중복도만큼씩 순서 있게 나열한 것이다. 다시 말해, 원래의 순열의 정의에서, 주어진 방식대로 짝지어진 원소들을 같다고 여겨 얻는 개념이다. 그 수는 다음과 같이 다항 계수로 주어진다.
예를 들어, 영어 단어 "MISSISSIPPI"의 어구전철의 수는 다음과 같다.
유한 집합 formula_14의 원순열(圓順列, )은 formula_140의 formula_141 위의 오른쪽 작용의 궤도를 뜻한다. 이는 formula_14의 formula_1-순환(즉, formula_144의 켤레 원소)과 일대일 대응한다. 풀어 말해, 이는 formula_1개의 원소를 원형 탁자에 둘러앉힌 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 원순열의 수는 다음과 같다.
이는 원래의 formula_3에서 겹치는 배수인 formula_1을 나눈 것이다. 예를 들어, 중심 대칭 시계 속의 1~12를 다시 배열하였을 때 얻을 수 있는 서로 다른 기능의 시계의 수는 formula_149이다.
유한 집합 formula_14의 염주 순열(念珠順列) 또는 목걸이 순열은 formula_151의 formula_14 위의 오른쪽 작용의 궤도를 뜻한다. 풀어 말해, 이는 formula_1개의 원소를 염주에 꿴 것이다. 다시 말해, 원래의 순열의 정의에서, 서로 회전 및 뒤집기만의 차이가 있는 순열을 같다고 여겨 얻는 개념이다. 염주 순열의 수는 다음과 같다.
이는 원래의 formula_3에서 겹치는 배수인 formula_156을 나눈 것이다. 예를 들어, 팔찌에 7개의 무지개색 구슬을 꿰었을 때 얻을 수 있는 서로 다른 모양의 팔찌의 수는 formula_157이다. 처음 몇 염주 순열의 수는 다음과 같다. (formula_158)
집합 formula_12의 순열의 집합 formula_18는 군을 이룬다. 즉, 다음이 성립한다.
유한 집합의 순열의 반전수·감소량에 대하여, 다음과 같은 부등식이 성립한다.
또한, 다음과 같은 점화식이 성립한다.
또한, 서로 역순열의 반전수·감소량는 서로 같다. 즉, 다음과 같은 항등식이 성립한다.
순열 formula_59의 궤도 formula_65 (formula_63)들은 formula_12의 분할을 이루며, 각 궤도에서의 제한은 다음과 같이 어떤 순환이다.
만약 비자명 궤도(=크기가 1이 아닌 궤도)의 개수가 유한하다면, formula_15는 이러한 서로소 비자명 순환들의 곱으로 분해할 수 있다. 서로소 순환들은 항상 가환한데, formula_15의 서로소 비자명 순환 분해는 곱하는 순서를 따지지 않으면 유일하다. 이러한 분해를 formula_15의 순환 분해(循環分解, )라고 한다. 순환 분해의 길이(=곱해지는 비자명 순환의 개수)는 비자명 궤도의 개수
와 같다. 특히, 쌍대 유한 고정점 집합을 갖는 순열은 항상 서로소 비자명 유한 순환들의 곱으로 유일하게 분해할 수 있다. 특히, 유한 집합의 순열 formula_45의 순환 분해는 구체적으로 다음과 같다.
유한 순환은 항상 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없다. 예를 들어, 어떤 호환의 짝수 제곱을 인수로 추가하면 새로운 호환 분해를 얻는다. 또한, 구체적으로 다음과 같은 분해식들이 성립한다.
홀순열의 호환 분해의 길이는 항상 홀수이며, 짝순열의 호환 분해의 길이는 항상 짝수이다. 이를 순열의 홀짝성을 정의하는 데 쓸 수 있다.
유한 집합의 순열의 호환 분해의 최소 길이는 감소량과 같다. 즉, 순열 formula_45에 대하여, 다음이 성립한다.
유한 집합의 호환은 항상 인접 호환들의 곱으로 분해할 수 있다. 이러한 분해는 유일할 필요가 없으며, 구체적으로 다음과 같은 분해식이 성립한다.
유한 집합의 순열의 인접 호환 분해의 최소 길이는 반전수와 같다. 즉, 순열 formula_45에 대하여, 다음이 성립한다.
순열 formula_59의 위수는 다음과 같다.
특히, 순환의 위수는 그 길이와 같다.
대칭군 formula_18의 켤레류는 formula_198를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 formula_199에 대하여, 다음 두 조건이 서로 동치이다.
대칭군 formula_141의 켤레류는 formula_1의 분할과 자연스럽게 일대일 대응한다. 즉, 순열 formula_204에 대하여, 다음 두 조건이 서로 동치이다.
유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.
달리 말해, 순열의 부호 함수 formula_74는 군 준동형이다. 즉, 다음이 성립한다.
이에 따라, 짝순열들은 대칭군의 부분군 formula_211을 이루며, 이를 교대군이라고 한다. 사실, 교대군은 이 부호 함수의 핵이므로, 대칭군의 정규 부분군이다.
홀순열의 집합은 부분군이 아니다. 또한, formula_213의 경우 홀순열이 존재하지 않는다. 그러나, formula_214의 경우 홀순열의 집합은 크기가 교대군과 같으며, 교대군의 (자기 자신을 제외하면 유일한) 잉여류이다.
순열의 합성의 한 가지 예는 다음과 같다.
순열의 역의 한 가지 예는 다음과 같다.
순열의 서로소 순환 분해의 한 가지 예는 다음과 같다.
순열의 홀짝성의 몇 가지 예는 다음과 같다.
크기 3의 대칭군 formula_218의 켤레류는 다음과 같다.
이들에 대응하는 3의 분할은 각각 다음과 같다.
순열의 반전수의 몇 가지 예는 다음과 같다.
유한 집합 formula_14의 순열은 formula_229 순열 행렬과 자연스럽게 일대일 대응한다.