Ordered Sequence   순열

(2021-04-16)

중복 순열


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) #]
. 例) 10명 중 회장,부회장을 뽑는 방법의 경우의 수는? : {# {_{10}P_2} = 90 #} - (원 순열, 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. 비둘기집 원리  


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