Ordered Sequence   순열

(2020-03-22)

중복 순열

1. 순열 (Ordered Sequence) 이란?

  ㅇ 어떤 집합 중 일부를 택하여 순서있게 나열하는 것
     - 서로 다른 것들 중 일부를 뽑아 일렬로 나열하는 것

  ㅇ [용어 유의]
     - 치환 (Permutation) : 전체(n)를 모두(n) 순서적으로 나열 {# {_nP_n} = n! #} 
     - 순열 (Ordered Sequence) : 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 {# {_nP_r} #} 


2. 순열에서, 경우의 수 계산

  ㅇ 비 중복 순열 (sampling without replacement)
    
     - (전체 순열) => (때론, 치환이라고도 함)
        . 서로다른 n개를 순서있게 나열하는 경우의 수 : n!

     - (일부 순열)
        . 서로다른 n개 중 r개를 취하여 순서있게 나열하는 경우의 수 : {# {_nP_r} #}

            
[# {_nP_r} = (n)(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!} \\ \quad \left( \, {_nP_0} = 1, \quad {_nP_n} = n! \, \right) #]
- (원 순열, circular permutation) . 서로다른 n개를 원형으로 순서있게 나열하는 경우의 수 : (n-1)! ㅇ 중복 순열 (sampling with replacement, permutation with repetition) - 중복을 허용하여 나열하는 경우의 수 . n개 중 중복을 허용하며 r개를 뽑아 나열하는 경우의 수 :
[#{_n\Pi_r} = n^r#]
- 例) . 알파벳으로 2개 문자를 만들 수 있는 단어 수는, 262 = 676 . 2개 숫자 0,1로 4 자리를 메꾸는 경우의 수는, 2 x 2 x 2 x 2 = 24 ㅇ (그룹 순열) (같은 것이 있는 순열) (다중 집합의 순열) - 일부 같은 것이 있는 n개를 k개의 다중 집합(k개 그룹)으로 순서있게 나열 . 즉, n1,n2,...,nk 그룹으로 순서있게 나열하는 경우의 수
[# \frac{n!}{n_1! n_2! \cdots n_k!} #]
- 만일, n개 중 p개가 같다면, 이때 순서있게 늘여놓는 경우의 수
[# \frac{n!}{p!} #]
- 例) 11개 문자(a가 5개,b가 2개,c가 2개,d가 1개,f가 1개)로 나열 가능한 방법의 수는? . (11!)/(5! 2! 2! 1! 1!) = 83160


[조합론/셈법(Counting)] 1. 조합론 2. 셈법 3. 치환 4. 순열 5. 조합 6. 경우의 수 계산 (요약) 7. 이항/다항 정리 8. 비둘기집 원리

 
        최근수정     요약목록     참고문헌