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

1. 셈 / 계수 (Counting, 計數), 셈 법 / 세는 법 (Counting Technique)

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

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


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

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


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

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