Permutation   치환 (Permutation)

(2022-06-30)

치환


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) - 어떤 집합합성함수 연산에 의해, 이되는 치환들의 모임

군(Group)
   1. 군(Group)   2. 군의 종류   3. 가환군   4. 부분군   5. 대칭성   6. 대칭 조작   7. 치환   8. 군 용어  
조합론/셈법(Counting)
   1. 조합론   2. 셈법   3. 치환   4. 순열   5. 조합   6. 경우의 수 계산 (요약)   7. 이항/다항 정리   8. 비둘기집 원리  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"