이산수학 - 조합이론

1.  기본계수법칙 

(1)  곱의 법칙 

두사건 A,B가 일어날 경우의 수  N(A) = m, N(B) =n 동시발생확률 N(A X B) = m x n 

 

(2)  합의 법칙 

두사건 A,B가 N(A) = m, N(B) =n 이고 A ∩ B = Ø, N(AUB) = m+n

 

2.  Permutation (순열)

(1)순열

0 ≤ r ≤ n을 만족하는 정수 n,r에 대하여 n개의 원소를 갖는 집합에서 순서를 고려해서 r개의 원소를 뽑는 경우의 수 

 

(2)중복집합에서의 순열

중복된 원소를 허용하는 중복집합의 크기가 n이고 중복된 원소가 각각 p, q, r개가 있을때 n개 모두를 일렬로 배열하는 경우의 수

 

(3)중복순열 

n개의 원소를 갖는 집합에서 중복을 허용하고, 순서를 고려해서 r개 원소를 뽑는 경우의 수 

(4)원순열

n개의 원소를 갖는 집합의 모든 원소들을 원형으로 나열하는 경우의 수 

 

3.  Combination (조합)

(1)조합 

0 ≤ r ≤ n을 만족하는 정수 n,r에 대하여 n개의 원소를 갖는 집합에서 순서없이 뽑는 경우의 수 

(2)이항정리 

 

4.  이산확률

(1) 표본공간과 사건

실험을 하였을때 가능한 모든 결과중에서 반드시 하나의 결과만 나타난다고 하면, 실험의 모든 결과의 집합을 표본공간(S), 표본공간의 부분집합이 사건(E)이다. 표본공간 S가 유한하며 각 사건이 발생할 가능성이 모두 동일하다고 하면 사건이 발생할 확률 

(2) 조건부 확률 

표본공간 S에 두 사건 A,B가 있고 P(B)>0 이라고 한다.사건 B가 발생했다는 가정하에 사건 A가 발생할 확률 

 

(3) 점화식 

수열의 항 사이에서 성립하는 관계식, aₙ을 n에 관한 식으로 나타내는 것 

 

(4) 비둘기집 원리  

수열의 항 사이에서 성립