Combination   조합, 조합 (Combination)

(2020-03-22)

중복 조합

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} #}은 일명 `이항계수`라고도 함 - 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개를 뽑는 경우의 수와 같음 ㅇ (그룹 조합) (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 #}


[조합론/셈법(Counting)] 1. 조합론 2. 셈법 3. 치환 4. 순열 5. 조합 6. 경우의 수 계산 (요약) 7. 이항/다항 정리 8. 비둘기집 원리

 
        최근수정     요약목록     참고문헌