1. [요약 비교]
ㅇ 전치 : 두 원소의 위치만 바꾸는 치환의 일종
ㅇ 순환 : 여러 원소가 순서대로 교체되어 원 위치로 복귀하는 치환의 일종
ㅇ 치환 : 전체(n)를 모두(n) 순서적으로 나열/재배열 (nPn = n! ☞ 팩토리얼 참조)
- 전치 ⊂ 순환 ⊂ 치환 : 전치는 치환의 특수한 경우로, 두 원소만 교환함
- "전체 재배열" 의미의 순열
ㅇ 순열 : 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 (nPr)
- 치환은 전체를 재배열하는 것이고, 순열은 부분만 선택해 나열
- "부분 재배열" 의미로써, 치환의 부분적 형태
ㅇ 조합 : 전체(n) 중 일부(r)를 뽑음/선택 (nCr)
- 순열의 비순서형 (순서 없는 선택)
ㅇ 분할 : 전체 n개를 여러 부분집합(서로 겹치지 않게)으로 나누는 것 (n!/(n1!…nr!)
- 조합 개념의 일반화
- 한편, 분할은 "집합의 분해(구분,나눔)"를 의미하며, 그 방법의 수는 다양함
ㅇ 이항계수 : 서로 다른 n개 중 r개를 뽑는 조합의 수 (C(n,r))
- 이항계수,다항계수 : 조합의 수를 수치적으로 계산 가능한 계수 형태로 나타낸 것
ㅇ 다항계수 : 서로 다른 n개를 여러 그룹(n1,…,nk)으로 나누는 경우의 수 (n!/(n1!…nk!)
- "분할"의 특수한 경우로, 분할된 각 그룹의 크기(원소 수)가 미리 정해져 있고,
. 분할 크기가 정해진 경우의 수를 다항계수로 표현하여 수치적으로 계산하기 위한 것
- 즉, "분할"은 집합론적 구분이고,
. "다항계수"는 그 중 순서 없는 분할의 경우의 수에 대한 산술적 표현임
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. 조합(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}} #}
4. 분할(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)#]
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 개)