1. 조합(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} #}은 일명 `이항계수 (Binomial Coefficient)`라고도 함
- k가 작을 경우에는, 위 식에서 n!와 (n-k)!을 약분시켜 표기하면 표현이 간단해짐
[# {n \choose 1} = \frac{n}{1!} \quad {n \choose 2} = \frac{n(n-1)}{2!} \quad {n \choose 3} = \frac{n(n-1)(n-2)}{3!} #]
- 주요 관계식
. {# {_nC_r} = {_{n-1}C_{r-1}} + {_{n-1}C_r} #}
. {# {_nC_r} = {_nC_{n-r}} #}
.. n개 중 r개를 뽑는 경우의 수는, n개 중 남은 n-r개를 뽑는 경우의 수와 같음
. {# {_nC_r} = {_nP_r}/r! \quad {_nC_r} \times r! = {_nP_r} #}
.. 각 조합별로 {#{_rP_r}=r!#}개의 순열 가능
ㅇ (그룹 조합) (grouping)
- 서로다른 n개를 p개,q개,r개로 3개의 그룹으로 조합하는 경우
. {# {_nC_p} \times {_{n-p}C_{q}} \times {_{r}C_{r}} #}
ㅇ (중복 조합) (combination with repetition)
- 서로다른 n개에서 중복을 허용하여 r개를 선택하는 경우의 수
. {# {_nH_r} = H(n,r) = {_{n+r-1}C_r} #}
- 例) {x,y,z}에서 중복을 허용하여 4개를 뽑는 경우의 수는?
. 1|3 => (xyyy),(xzzz),(yxxx),(yzzz),(zxxx),(zyyy) : 6개
. 2|1|1 => (xxyz),(yyxz),(zzxy) : 3개
. 2|2 => (xxyy),(xxzz),(yyzz) : 3개
. 4|0 => (xxxx),(yyyy),(zzzz) : 3개
. {# {_3H_4} = H(3,4) = {_{3+4-1}C_4} = {_6C_4} = \frac{6!}{2!4!} = 15 #}