순열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
빨강·초록·파랑의 공을 6가지의 순서대로 배열한 것
3개의 서로 다른 공에 대한 총 6가지의 순열
3x3x3 루빅스 큐브
루빅스 큐브의 면에 대한 회전은 그 면의 9개의 색깔에 대한 한 가지 순열이다.

수학에서, 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 즉, 순열은 정의역공역이 같은 일대일 대응이다. 개의 원소의 순서를 뒤섞는 순열의 개수는 계승 와 같다. 즉, 이하의 양의 정수들을 곱한 값이다.

임의의 집합을 어떤 순열에 따라 뒤섞은 뒤 다른 어떤 순열에 따라 뒤섞은 결과는 새로운 어떤 순열에 따라 뒤섞은 결과와 같다. 즉, 임의의 두 순열에 대하여, 그 합성 역시 순열이며, 임의의 집합의 순열들은 이러한 합성 연산 아래 대칭군이라는 을 이룬다. 모든 원소가 순열인 군, 다시 말해 대칭군의 부분군순열군(順列群, 영어: permutation group) 또는 치환군(置換群)이라고 한다. 순열군은 여러 가지 집합 위에 자연스러운 군의 작용을 주며, 이는 그 집합의 구조를 뒤섞는다.

조합론에선 이와 다른 순열의 여러 가지 정의가 사용된다. 가장 자주 쓰이는 하나는 임의의 집합에서 일정 개수의 원소를 골라 순서를 뒤섞는 연산이다. 개의 원소에서 개의 원소를 골라 순서를 뒤섞는 연산을 -순열(-順列, 영어: -permutation of )이라고 하며, 그 개수는 하강 계승 와 같다. 즉, 이하의 정수들 가운데 가장 큰 개를 곱한 값이다.

정의[편집]

집합 순열전단사 함수 이다. 특히, 유한 집합 의 순열 를 다음과 같이 표기한다.

모든 의 순열이 함수의 합성에 따라 이루는 또는 대칭군이라고 한다. 이는 집합의 크기에 따라 완전히 분류되며, 특히 기수 에 대응하는 대칭군 또는 차 대칭군이라고 한다. 임의의 집합의 순열은 그 밖의 모든 원소를 고정점으로 여길 경우 자연스럽게 더 큰 집합의 순열이 된다. 즉, 임의의 에 대하여, 자연스러운 동형에 따라 이다. 특히, 이다.

순환[편집]

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

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

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

반전[편집]

순열 에 대하여, 튜플 이 다음 두 조건을 만족시키면, 반전(反轉 영어: inversion)이라고 한다.

또한, 반전 벡터(反轉-, 영어: inversion vector) 번째 성분이 로 끝나는 반전의 개수인 벡터이다. 즉, 이는 다음과 같다.

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

궤도[편집]

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

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

부호[편집]

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

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

홀짝성[편집]

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

  • 홀수이다.
  • 는 홀수이다.

홀순열이 아닌 순열을 짝순열(-順列, 영어: even permutation)이라고 한다. 즉, 순열 에 대하여, 다음 세 조건이 서로 동치이며, 이를 만족시키는 짝순열이라고 한다.

  • 짝수이다.
  • 는 짝수이다.

순열의 수[편집]

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

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

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

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

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

-순열[편집]

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

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

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

중복 순열[편집]

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

중복집합 순열[편집]

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

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

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

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

원순열[편집]

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

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

염주 순열[편집]

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

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

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

성질[편집]

연산에 대한 닫힘[편집]

집합 의 순열의 집합 을 이룬다. 즉, 다음이 성립한다.

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

반전수[편집]

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

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

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

순환 분해[편집]

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

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

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

호환 분해[편집]

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

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

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

인접 호환 분해[편집]

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

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

군론적 성질[편집]

순열 위수는 다음과 같다.

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

대칭군 켤레류를 양의 기수들의 합으로 나타내는 방법과 자연스럽게 일대일 대응한다. 즉, 순열 에 대하여, 다음 두 조건이 서로 동치이다.

  • 는 서로 켤레이다.
  • 의 궤도의 개수와 각 궤도의 크기는 각각 서로 같다.

대칭군 켤레류분할과 자연스럽게 일대일 대응한다. 즉, 순열 에 대하여, 다음 두 조건이 서로 동치이다.

  • 는 서로 켤레이다.
  • 의 서로소 순환 분해의 길이와 각 순환의 길이는 각각 서로 같다.

유한 집합의 순열의 홀짝성에 대하여, 다음이 성립한다.

  • 항등 함수는 짝순열이다.
  • 두 홀순열의 합성은 짝순열이며, 두 짝순열의 합성 역시 짝순열이다. 홀순열과 짝순열의 합성은 홀순열이다.
  • 홀순열의 역은 홀순열이며, 짝순열의 역은 짝순열이다.

달리 말해, 순열의 부호 함수 군 준동형이다. 즉, 다음이 성립한다.

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

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

[편집]

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

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

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

순열의 홀짝성의 몇 가지 예는 다음과 같다.

  • 항등 함수는 짝순열이다.
  • 호환은 홀순열이다.
  • 짝수 길이의 순환은 홀순열이다.
  • 홀수 길이의 순환은 항상 짝순열이다.

크기 3의 대칭군 켤레류는 다음과 같다.

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

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

관련 개념[편집]

순열 행렬[편집]

순열의 합성과 순열 행렬의 곱셈의 관계에 대한 설명
순열의 합성은 순열 행렬의 곱셈에 대응한다.

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

바깥 고리[편집]