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