경우의 수 계산 (요약)

(2022-06-06)

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} #} ㅇ (중복 조합) (combination with repetition) - 서로다른 n개에서 중복을 허용하여 r개를 선택하는 경우의 수 . {# {_nH_r} = H(n,r) = {_{n+r-1}C_r} #} ㅇ (그룹 조합) (grouping) - 서로다른 n개를 p개,q개,r개로 3개의 그룹으로 조합하는 경우 . {# {_nC_p} \times {_{n-p}C_{q}} \times {_{r}C_{r}} #} 5. 기타 ㅇ 쌍으로 취할 수 있는 경우의 수 - N개,M개 요소를 갖는 두 집합에서, 각 1개씩 취하는 경우의 수 : {# N \times M #} . 例) {1,2},{3,4,5} => {1,3},{1,4},{1,5},{2,3},{2,4},{2,5} => (2 x 3 = 6개) ㅇ 부분집합으로 만들 수 있는 경우의 수 - N개 요소를 갖는 집합에서 임의로 취할 수 있는 부분집합의 수 : {# 2^N #} . 例) {1,2}의 부분 집합은, {Φ,{1},{2},{1,2}} => (22 = 4 개)

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


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