1. 치환 (Permutation) 또는 순열 (Ordered Sequence) 이란?
ㅇ 순서를 바꿔보는 것
- 순서 있는 집합을 다른 순서로 섞어보는 것
- 전체 또는 일부의 순서적 배열(arrangement) 또는 재배열(rearrangement)하는 것
- 어떤 집합 중 일부를 택하여 순서있게 나열하는 것
2. [용어 비교]
ㅇ 전치 : 단지 두 원소 쌍 단위로 만 바꾸는(위치바꿈) 치환의 일종
ㅇ 치환 : 전체(n)를 모두(n) 순서적으로 나열/재배열 (nPn = n! ☞ 팩토리얼 참조)
ㅇ 순열 : 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 (nPr)
ㅇ 조합 : 전체(n) 중 일부(r)를 선택 (nCr)
3. 치환(Permutation)의 例)
ㅇ S = {1,2,3}에서 3개를 뽑아 나열(재배열)하는 모든 경우의 수는?
- 123을 기준으로 보면, 경우의 수는 총 6번 = 3P3
. ① 123 : 자리바꿈 0번 (우순열)
. ② 132 → 123 : 자리바꿈 1번 (기순열)
. ③ 213 → 123 : 자리바꿈 1번 (기순열)
. ④ 231 → 213 → 123 : 자리바꿈 2번 (우순열)
. ⑤ 312 → 132 → 123 : 자리바꿈 2번 (우순열)
. ⑥ 321 → 231 → 213 → 123 : 자리바꿈 3번 (기순열)
* nPr ( = n!/(n-r)! = 3! = 3x2x1 = 6 )
ㅇ [참고] ☞ 치환행렬 참조
4. 치환(Permutation)의 다른 표현 : 함수 또는 매핑 (대응)
ㅇ 치환의 정의
- 한 집합 A에서 자기자신으로 가는 `일대일 대응` (즉, 집합 A 위에서의 `전단사함수`)
. f : A → A
* 정의역 A의 원소들은, 이같은 함수 f에 의해, 치역 A에서 어떤 새로운 순서로 재배열됨
ㅇ 치환의 표시법
- 例) 집합 A = {1,2,3,4} 에 대한 어떤 치환 f를,
. 다음과 같이 함수의 배열 형태로 표시 가능
. f(1) = 2, f(2) = 3, f(3) = 1, f(4) = 4
[# f = \begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{pmatrix} #]
ㅇ 치환의 수 (경우의 수)
- n개 원소를 갖는 어떤 집합에서 치환 가능 수 : n!
5. 치환(Permutation)의 특별한 형태
ㅇ 순환 (Cycle)
- 한 원소로 시작하여 여러 치환을 겪고 다시 처음의 원소로 되돌아옴
- 例) 1 → 2 → 3 → 1 (길이가 4인 순환)
ㅇ 전치 (Transposition)
- 단지 두 원소 쌍 단위로 만 바꾸는 치환
ㅇ 치환 군 (Permutation Group)
- 어떤 집합이 합성함수 연산에 의해, 군이되는 치환들의 모임