1. [용어 비교]
ㅇ 전치 : 단지 두 원소 쌍 단위로 만 바꾸는(위치바꿈) 치환의 일종
ㅇ 치환 : 전체(n)를 모두(n) 순서적으로 나열/재배열 (nPn = n! ☞ 팩토리얼 참조)
ㅇ 순열 : 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 (nPr)
ㅇ 조합 : 전체(n) 중 일부(r)를 선택 (nCr)
ㅇ 이항계수 : 서로다른 물건 중 몇 개를 뽑는 경우의 수
ㅇ 다항계수 : 서로다른 물건들을 몇 개로 그룹짓는 경우의 수
2. 순열(Ordered Sequence)에서, 셈하는 종류 (경우의 수)
ㅇ 비 중복 순열 (sampling without replacement)
- (전체 순열) => 때론, 치환(Permutation) 이라고도 함
. 서로다른 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)!
- (그룹 순열) (같은 것이 있는 순열) (다중 집합의 순열)
. 일부 같은 것이 있는 n개를 k개의 다중 집합(k개 그룹)으로 순서있게 나열
[# \frac{n!}{n_1! n_2! \cdots n_k!} #]
. 만일, n개 중 p개가 같다면, 이때 순서있게 늘여놓는 경우의 수 : n!/p!
ㅇ 중복 순열 (sampling with replacement)
- 중복을 허용하여 나열하는 경우의 수
. m개 중 중복을 허용하며 n개를 뽑아 나열하는 경우의 수 : mn
3. 분할(Partition)에서, 셈하는 종류 (경우의 수)
ㅇ 서로다른 n개 집합을 r개의 부분집합으로 분할하는 경우의 수
[# \begin{pmatrix} n \\ n_1,n_2,\cdots,n_r \end{pmatrix} =
\frac{n!}{n_1! n_2! \cdots n_r!} \qquad (n_1 + n_2 + \cdots + n_r = n)#]
4. 조합(Combination)에서, 셈하는 종류 (경우의 수)
ㅇ (비 중복 조합)
- 유한개의 서로다른 원소를 갖는 집합으로부터 부분집합을 만드는 것
. 원소가 n개인 집합에서 원소가 k개인 부분집합을 선택하는 방법의 수
. (k-조합, k-combination)
[# {_nC_k} = C(n,k) = {n \choose k} = \frac{P(n.k)}{P(k,k)} = \frac{n!}{(n-k)!k!}#]
. 한편, 기호 {# {n \choose k} #}은 일명 `이항계수`라고도 함
- 주요 관계식
. {# {_nC_r} = {_{n-1}C_{r-1}} + {_{n-1}C_r} #}
ㅇ (중복 조합) (combination with repetition)
- 서로다른 n개에서 중복을 허용하여 r개를 선택하는 경우의 수
. {# {_nH_r} = H(n,r) = {_{n+r-1}C_r} #}
ㅇ (그룹 조합) (grouping)
- 서로다른 n개를 p개,q개,r개로 3개의 그룹으로 조합하는 경우
. {# {_nC_p} \times {_{n-p}C_{q}} \times {_{r}C_{r}} #}
5. 기타
ㅇ 쌍으로 취할 수 있는 경우의 수
- N개,M개 요소를 갖는 두 집합에서, 각 1개씩 취하는 경우의 수 : {# N \times M #}
. 例) {1,2},{3,4,5} => {1,3},{1,4},{1,5},{2,3},{2,4},{2,5} => (2 x 3 = 6개)
ㅇ 부분집합으로 만들 수 있는 경우의 수
- N개 요소를 갖는 집합에서 임의로 취할 수 있는 부분집합의 수 : {# 2^N #}
. 例) {1,2}의 부분 집합은, {Φ,{1},{2},{1,2}} => (22 = 4 개)