•  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
더 보기
0 역링크 토론 편집 역사 ACL

조합

분류
조합(組合, Combination)
1. 개요2. 특징

1. 개요[편집]

서로 다른 n개에서 순서를 생각하지 않고 r개를 선택하는 것을 조합이라고 한다. (단, 0≤r≤n0\leq r\leq n) Combination의 앞글자 C를 따 조합을 nCr{}_n{\rm C}_r 로 쓴다.

쉽게 예시를 들자면 5명의 사람 중 무작위로 2명을 선택하는 경우의 수는 5C2=5×42×1=10{}_5{\rm C}_2= \frac{5\times 4}{2\times 1}= 10 이는 순열인 5C2{}_5{\rm C}_2 에서 순서를 생각하지 않으므로 2!로 나눈 것이다.

2. 특징[편집]

  • nCr=nPrr!=n!r!(n−r)!{}_n{\rm C}_r= \frac{{}_n{\rm P}_r}{r!}= \frac{n!}{r!(n-r)!}
  • nC0=1{}_n{\rm C}_0= 1[1], nCn=1{}_n{\rm C}_n= 1
  • nCr=nCn−r{}_n{\rm C}_r= {}_n{\rm C}_{n-r}[2]
  • nCr=n−1Cr+n−1Cr−1{}_n{\rm C}_r= {}_{n-1}{\rm C}_r+{}_{n-1}{\rm C}_{r-1}
    • =(n−1)!r!{(n−1)−r}!+(n−1)!r−1!{(n−1)−(r−1)}!=(n−1)!r!(n−1−r)!+(n−1)!(r−1)!(n−r)!=(n−r)(n−1)!r!(n−r)!+r(n−1)!r!(n−r)!={(n−r)+r}(n−1)!r!(n−r)!=n!r!(n−r)!=nCr= \frac{\left ( n-1 \right )!}{r!\left\{ \left ( n-1 \right )-r\right\}!} + \frac{\left ( n-1 \right )!}{r-1!\left\{ \left ( n-1 \right )-(r-1)\right\}!} \\ = \frac{(n-1)!}{r!(n-1-r)!} +\frac{(n-1)!}{(r-1)!(n-r)!} \\ = \frac{(n-r)(n-1)!}{r!(n-r)!} + \frac{r(n-1)!}{r!(n-r)!} \\ =\frac{\left\{ (n-r)+r\right\}(n-1)!}{r!(n-r)!} \\ =\frac{n!}{r!(n-r)!}= {}_n{\rm C}_r
[1] 0개를 선택하는 경우의 수는 한가지이기 때문[2] n개가 있을 때 r개를 뽑는 방법의 수인 nCr{}_n{\rm C}_r과, 선택되지 않은 n-r개를 뽑는 방법의 수는 같기 때문이다.