[이산수학#12] 조합이론

1. 기본 계수 법칙

두 사건 A, B가 일어날 경우의 수가 각각 N(A) = m, N(B) = n일 때,

 

곱의 법칙 : A, B가 동시에 일어날 경우의 수는 m x n

합의 법칙 : 𝑨 ∩ 𝑩 = ∅일때,  A 또는 B가 일어날 경우의 수는 m + n

 

합집합의 크기

- 유한집합

|𝑨 ∪ 𝑩| = |𝑨| + |𝑩| − |𝑨 ∩ 𝑩|

|𝑨 ∪ 𝑩 ∪ 𝑪| = |𝑨| + |𝑩| + |𝑪| − |𝑨 ∩ 𝑩| − |𝑨 ∩ 𝑪| − |𝑩 ∩ 𝑪| + |𝑨 ∩ 𝑩 ∩ 𝑪|

 

- 유한집합 + 서로소

|𝑨 ∪ 𝑩| = |𝑨| + |𝑩|

 

 

2. 순열

순열, 중복순열, 원순열

순열 : 순서를 고려	중복순열 : 중복된 원소를 허용하는 순열
𝟎 ≤ 𝒓 ≤ 𝒏을 만족하는 정수 n, r에 대하여, n개의 원소를 갖는 집합에서 순서를 고려해서 r개의 원소를 뽑는 경우의 수	중복된 원소를 허용하는 중복집합의 크기가 n이고 그 중에서 중복된 원소의 개수가 각각 p개, q개, ⋯ , r개가 있 을 때, n개 모두를 일렬로 배열하는 경우의 수
원순열 : 원형으로 나열	중복순열
n개의 원소를 갖는 집합의 모든 원소들을 원형으로 나열하는 경우의 수	n개의 원소를 갖는 집합에서 중복을 허용하고 순서를 고려해서 r개 원소를 뽑는 경우의 수

 

3. 조합

조합 :

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

 

 

 

이항 정리 :

임의의 실수 𝒙, 𝒚와 음이 아닌 정수 𝒏이 주어졌을 때,

 

4. 이산확률

표본공간: 실험의 모든 결과의 집합

사건: 표본공간의 부분집합

수학적 확률 :

표본공간 𝑺가 유한하며 각 사건이 발생할 가능성이 모두 동일 하다고 가정할 때 사건 𝑬(⊂ 𝑺) 가 발생할 확률

 

조건부 확률 :

표본공간 𝑺에 두 사건 𝑨, 𝑩가 있고, 𝑷 𝑩 > 𝟎이라고 하자. 사건 𝑩가 발생했다는 가정하에 사건 𝑨가 발생할 확률

 

5. 점화식

점화식 : 수열의 항 사이에서 성립하는 관계식

 

6. 비둘기집 원리