Combination   조합 , 조합 (Combination)

(2023-11-11)

중복 조합, 그룹 조합


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 #}

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


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"