순열

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

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

순열의 수[편집]

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

n개 원소의 k-순열은 서로 다른 n개 원소 가운데 k(kn)개를 골라 한 줄로 나열하는 것이다. n개의 원소의 k-순열의 수는 , , , 로 표기하며, 다음과 같다.

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

가 된다.

중복 순열[편집]

중복순열(重複順列, 영어: permutation with repetition)은 중복을 허용하는 순열이다. n개의 원소의 r-중복순열의 수는 다음과 같다.

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

이다.

중복집합 순열[편집]

중복집합 순열 또는 같은 것이 있는 순열은 각 원소들을 중복도 만큼씩 나열하는 것이다. n1개의 a1, n2개의 a2, ..., nt개의 at로 이루어진 n개 원소 다중집합에 대하여, 그 순열의 수는 다음과 같다.

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

이다.

원순열[편집]

원순열(圓順列, 영어: circular permutation)은 서로 다른 원소를 "원형 탁자에 앉히는 것"이다. 두 원순열이 같을 필요 충분 조건은, 하나를 회전하여 다른 하나를 얻을 수 있다는 것이다. n개 원소의 원순열의 수는 다음과 같다. 즉, 일반 순열의 수를 중복된 배수 n으로 나눈 것이다.

다각형 순열은 서로 다른 원소를 "다각형 탁자에 앉히는 것"이다. 두 다각형 순열이 같을 필요 충분 조건은 역시 하나를 회전하여 다른 하나를 얻을 수 있다는 것이다. 다각형 순열의 수 역시 일반 순열의 수를 중복된 배수로 나눈 것이다. 염주 순열(念珠順列) 또는 목걸이 순열은 서로 다른 종류의 구슬로 "염주(목걸이)를 만드는 것"이다. 두 염주 순열이 같을 필요 충분 조건은, 하나를 뒤집거나 회전하여 다른 하나를 얻을 수 있다는 것이다. n개 원소의 염주순열의 중복된 배수는 2n이며, 그 수는 이다.

정의[편집]

치환[편집]

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

는 치환

를 뜻한다.

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

순환과 호환[편집]

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

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

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

특히, 2-순환

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

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

반전[편집]

차 치환 반전(反轉 영어: inversion)은 큰 수가 작은 수 앞에 오는 두 수의 쌍이다. 즉, 이며 인 튜플 이다.

에 대하여, 다음과 같은 자연수는 서로 같으며, 이를 반전수(영어: inversion number) 라고 한다.

  • 의 반전의 개수
  • 의 인접 호환 분해의 최소 길이

홀치환과 짝치환[편집]

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

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

  • 반전수가 짝수이다.
  • 호환 분해의 길이가 짝수이다.

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

  • 짝치환이 아니다.
  • 반전수가 홀수이다.
  • 호환 분해의 길이가 홀수이다.

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

성질[편집]

일반적으로 길이 L = mn의 순환치환을 m승 하면 길이 n의 순환치환 m개의 곱이 된다. 예를 들어 m = 2, n = 3일 때,

[편집]

속 순열

의 합성은

이다.

같이 보기[편집]

바깥 고리[편집]