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