경우의 수 계산 (요약)

(2020-01-29)
1. [용어 비교]치환 : 전체(n)를 모두(n) 순서적으로 나열/재배열 (nPn = n! ☞ 팩토리얼 참조)
  ㅇ 순열 : 전체(n) 중 일부(r)를 선택하여 순서적으로 나열 (nPr)
  ㅇ 조합 : 전체(n) 중 일부(r)를 선택 (nCr)


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. 분할(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)#]
4. 조합(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} #} ㅇ (그룹 조합) - 서로다른 n개를 p개,q개,r개로 3개의 그룹으로 조합하는 경우 . {# {_nC_p} \times {_{n-p}C_{q}} \times {_{r}C_{r}} #}


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

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