순열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학에서, 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 조합론에서는 용어 "순열"을 많이 사용하며, 주어진 집합의 원소 또는 그 일부에 대한 배열을 뜻한다. 대수학에서는 용어 "치환"을 많이 사용하며, 주어진 집합 위의 일대일 대응을 뜻한다. 이들은 함수의 합성에 따라 대칭군이라는 을 이룬다.

순열의 수[편집]

n개 원소의 k-순열[편집]

n개 원소의 k-순열(영어: k-permutations of n)은 서로 다른 n개 원소 가운데 k(kn)개를 골라 순서 있게 나열하는 순열이다. 다만 고르는 원소의 중복은 허용하지 않는다. n개 원소의 k-순열의 수는 , , , 와 같이 표기하며, 다음과 같다.

예를 들어, 여섯 곡 노래 가운데 세 곡을 골라 공연에 순서대로 배정하는 방법의 수는

가 된다.

중복 순열[편집]

중복 순열(重複順列, 영어: permutation with repetition)은 바로 위 정의에서 고르는 원소의 중복을 허용하는 경우이다. n개의 원소의 r-중복 순열의 수는 다음과 같다.

예를 들어, 26개의 알파벳으로 구성할 수 있는 세 문자 단어의 개수는

이다.

다중집합 순열[편집]

서로 다른 원소와 각자 중복도가 주어졌을 때, 원소를 중복도 만큼 나열하는 순열을 다중집합 순열 또는 같은 것이 있는 순열이라고 한다. n1a1, n2a2, ..., ntat, 총 n개 원소의 다중집합에 대하여, 그 다중집합 순열의 수는 다음과 같다.

예를 들어, 영어 단어 "MISSISSIPPI"에 대한 재배열의 개수는

이다.

원순열[편집]

원순열(圓順列, 영어: circular permutation)은 서로 다른 원소를 "원형 탁자에 앉히는" 순열이다. 다각형 순열은 서로 다른 원소를 "다각형 탁자에 앉히는" 순열이다. 염주 순열(念珠順列) 또는 목걸이 순열은 서로 다른 원소를 "염주에 꿰는" 순열이다. 이들은 일반 순열에서 주어진 대칭이 존재하는 두 순열을 같다고 보아 얻는 순열이다. 즉, 이들은 일반 순열의, 주어진 대칭 관계에 대한 동치류이다.

원순열의 대칭은 방향 있는 정n각형의 대칭이다. 즉 회전 대칭이다. 따라서 두 원순열이 하나를 회전하여 다른 하나를 얻을 수 있을 경우 같다고 본다. n개 원소의 원순열의 수는 이다. 즉, 일반 순열의 수를 중복된 배수 n으로 나눈 것이다.

다각형 순열의 대칭은 방향 있는 n각형의 대칭이며 다각형의 모양에 따라 다르다. 따라서 두 다각형 순열이 차이가 방향 있는 다각형의 대칭 변환일 경우 같다고 본다. 다각형 순열의 수 역시 일반 순열의 수를 중복된 배수로 나눈 것이다.

두 염주 순열의 대칭은 (방향 없는) 정n각형의 대칭이다. 즉 회전 및 반사 대칭이다. 따라서 두 염주 순열이 하나를 회전하거나 뒤집어 다른 하나를 얻을 수 있을 경우 같다고 본다. n개 원소의 염주순열의 중복된 배수는 2n이며, 그 수는 이다.

정의[편집]

치환[편집]

집합 에 대하여, 전단사 함수 위의 치환이라고 한다. 특히, 유한 집합 의 경우, 이라고 볼 수 있으며, 예를 들어 표기

는 치환

를 뜻한다.

모든 치환 의 집합은 로 표기하며, 특히 원소 집합의 경우 이나 으로 표기한다. 함수의 합성에 따라 이루는 대칭군이라고 한다.

순환과 호환[편집]

유한 집합 위의 -순환(循環, 영어: -cycle)은 조건

를 만족시키는 원소 부분 집합 가 존재하는 치환이며, 이를

로 표기한다. 즉, 순환은 일부 원소를 "순환"시키며, 다른 원소들을 그대로 두는 치환이다. 이 경우 를 그 순환의 길이(영어: length)라고 한다.

특히, 2-순환

호환(互換, 영어: transposition)이라고 하며, 인접하는 두 수에 대한 호환

인접 호환(영어: adjecent transposition)이라고 한다.

반전[편집]

차 치환 반전(反轉 영어: inversion)은 이며 인 튜플 이다.

반전수(영어: inversion number) 의 반전의 개수이다.

이는 의 인접 호환 분해의 최소 길이와 같다.

홀치환과 짝치환[편집]

유한 집합 위의 치환은 홀치환(영어: odd permutation)과 짝치환(영어: even permutation)으로 분류된다.

차 치환 에 대하여, 다음 두 조건이 서로 동치이며, 이를 만족시키는 치환을 짝치환이라고 한다.

  • 반전수가 짝수이다.
  • 모든 호환 분해의 길이가 짝수이다.
  • 어떤 호환 분해의 길이가 짝수이다.

마찬가지로, 에 대하여, 다음 두 조건이 서로 동치이며, 이를 만족시키는 치환을 홀치환이라고 한다.

  • 반전수가 홀수이다.
  • 모든 호환 분해의 길이가 홀수이다.
  • 어떤 호환 분해의 길이가 홀수이다.

치환의 부호(영어: sign) 는 짝치환에게 1, 홀치환에게 -1을 대응시키는 함수이다. 즉,

성질[편집]

두 서로소 순환(즉, 순환되는 원소들이 서로소 집합을 이루는 순환)은 가환하다.

분해[편집]

모든 치환은 서로소 순환의 합성으로 (순서를 생각하지 않을 때) 유일하게 분해할 수 있다.

여기서

모든 순환은 더 작은 순환의 합성으로 분해할 수 있으며, 특히 호환의 합성으로 분해할 수 있다.

모든 호환은 인접 호환의 합성으로 분해할 수 있다. ()

-순환의 제곱은 -순환으로 분해할 수 있다. 예를 들어 , 일 때,

[편집]

속 순열

의 합성은

이다. (합성 표기 순서는 점별 대입 시와 동일한 순서를 따랐다.)

참고[편집]

위의 예에서 치환 합성 계산의 순서는 오른쪽에서 왼쪽 방향으로 적용하였다. 이 순서는 FRALEIGH 의 현대대수학(A First Course in Abstract Algebra) 에서 치환의 연산순서가 함수의 합성과 동일해야 함을 근거로 제안한 내용과 같다. 위키피디아, 위키백과 등에서도 이 순서를 따르고 있다. 반면, 왼쪽에서 오른쪽 방향으로 적용하여 계산하는 경우도 있다. "열세살 딸에게 가르치는 갈루아 이론" (김중명 지음, 승산) 등의 일부 서적에서는 왼쪽에서 오른쪽으로 계산하고 있으며, 일부 수학 계산 관련 웹사이트(예: http://www.bananattack.com/permutations/) 에서도 왼쪽에서 오른쪽 방향으로 계산하는 방법을 따르고 있다. 울프람 알파도 같은 방법을 따르는 것으로 보아(https://www.wolframalpha.com/input/?i=perm+(12)(13)), 수학계에서도 이 부분이 명확하게 통일되지 않은 듯 하다.

같이 보기[편집]

바깥 고리[편집]