Permutation   치환 (Permutation)

(2018-01-16)

치환

1. 치환(Permutation) 또는 순열(Ordered Sequence) 이란?

  ㅇ 순서를 바꿔보는 것
     - 전체 또는 일부의 순서적 배열(arrangement) 또는 재배열(rearrangement)하는 것
     - 어떤 집합 중 일부를 택하여 순서있게 나열하는 것

  ※ 例)  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 )


2. 치환(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 = 

  ㅇ 치환의 수 (경우의 수)
     - n개 원소를 갖는 어떤 집합에서 치환 가능 수 : n!


3. 치환의 특별한 형태 

  ㅇ 순환(Cycle)         : 한 원소로 시작하여 여러 번 치환을 적용하여 다시 처음의 원소로 옴
     - 例) 1 → 2 → 3 → 1 (길이가 4인 순환)

  ㅇ 전치(Transposition) : 단지 두 원소 만을 바꾸는 치환

  ㅇ 치환 (Permutation Group)
     - 어떤 집합합성함수 연산에 의해 이되는 치환들의 모임


[군(Group)] 1. 군(Group) 2. 군의 종류 3. 가환군 4. 대칭성 5. 대칭 조작 6. 치환

 
        최근수정     요약목록(시험중)     참고문헌