Counting, Counting Technique, Number of Cases   셈 법, 계수 (計數), 경우의 수

(2020-01-22)

Sum Rule, 합 법칙, Multiplication Rule, 곱 법칙, 곱 규칙, Multiplication Principle, 곱셈 원리, 곱 원리

1. 셈(Counting), 셈 법/세는 법(Counting Technique)

  ㅇ 수(경우의 수)를 세는 방법

  ㅇ [응용]  
     - 정해진 시간 내, 발생 횟수의 단순 계수 : 타이머, 카운터 등
     - 확률 실험에서, 경우의 수를 세기  : 확률 계산의 기초가 됨 
     - 컴퓨터 알고리즘에서, 시간복잡도  : 알고리즘에 사용된 연산의 개수를 셈
     - 화학량론에서, 물질입자 수     : 물질량(몰수)

  ※ [참고] ☞ 순열(Permutation), 조합(Combination), 이항계수, 다항계수 참조
     - 치환 : 전체 모두를 재 배열하는 경우의 수
     - 순열 : 전체 중 일부를 선택하여 배열하는 경우의 수
     - 조합 : 전체 중 일부를 선택하는 경우의 수
     - 이항계수 : 서로다른 물건 중 몇 개를 뽑는 경우의 수
     - 다항계수 : 서로다른 물건들을 몇 개로 그룹짓는 경우의 수


2. 경우의 수(Number of Cases,境遇一數) 이란?
  
  ㅇ 시행(trial)을 통해 일어날 수 있는 사건(event)의 가짓수


3. 셈(덧셈,곱셈)의 성질

  ㅇ 덧셈 : 하나씩 세는 것
  ㅇ 곱셈 : 똑같은 덧셈이 몇 번인가를 세는 것 

  ※ 한편, 자연수 집합에 대해 닫혀있음 여부
     - 덧셈 및 곱셈은, 자연수 집합에 대해 닫혀있음(Closure) 
     - 뺄셈 및 나눗셈은, 자연수 집합에 대해 닫혀있지 않음


4. 셈(덧셈,곱셈)의 규칙

  ㅇ 덧셈 원리/덧셈 규칙/합의 법칙 (Addition Principle, Addition Rule)
     - 원소들이 `서로소(Disjoint, X∩Y=0)` 또는 `상호배반적인` 부분집합으로 나누어질 때, 
     - 각 부분집합의 원소의 갯수를 합하면 전체가 됨
        . 즉,   nz = nx + ny
           .. (x,y가 동시에 일어나지 않거나, x 또는 y가 일어나는 경우/방법의 수)

  ㅇ 곱셈 원리/곱셈 규칙/곱의 법칙 (Multiplication Principle, Multiplication Rule)
     - 각 사건에서의 발생 가능한 경우의 수 ni를 모두 곱하면 전체 경우의 수와 같아짐
       . 즉,   n = n1 x n2 x ... x nt
       . 例) n개 비트로 표현 가능한 총 경우의 수 : 2 x 2 x ... x (n번째 2) = 2n

     - 달리말하면, 
        . 어떤 행위가 연속적인 단계들로 구성될 때,
        . 각 단계에서 가능한 방법의 수를 모두 곱하면 전체 경우의 수가 됨


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

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