🤣

[Discrete Mathematics] 6. Counting Methods and The Pigeonhole Principle

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.
합의 법칙 곱의 법칙 순열 조합 이항정리, 집합의 분할 등 고교 과정과 겹치는것은 생략

Stirling Number of 1st Kind

3-Permutation of 3-Set을 예시로 살펴보자.
(1,2,3) → (1)(2)(3) : Graph에서 3개의 Cycle을 갖는 것으로 나타낼 수 있다.
(2,3,1) → (1 2 3) : 1개
(3,1,2) → (1 3 2) : 1개
(1,3,2) → (1)(2 3) : 2개
(3,2,1) → (1 3)(2) : 2개
(2,1,3) → (1 2)(3) : 2개
Function → Cycle
여기서 다음을 정의하자.
s(n,k)s(n,k) = Number of n-Permutation with k-Cycles = Stirling Number of 1st Kind = 제 1종 스털링 수
위의 예시에서는
s(3,3)=1s(3,3) = 1
s(3,2)=3s(3,2) = 3
s(3,1)=2s(3,1) = 2
s(3,3+k)=0s(3,3+k) = 0
처럼 나타낼 수 있다.
제 1종 스털링 수는 다음과 같은 관계가 성립함.
s(n,k)=s(n1,k1)+(n1)s(n1,k)s(n,k) = s(n-1,k-1) + (n-1)s(n-1,k)
이를 조합론적으로 증명해보면, n번째 원소가 다른 Cycle에 포함되느냐 포함되지 않느냐로 나눠서
1) 포함되지 않는 경우
s(n1,k1)s(n-1,k-1)은 k-1개의 Cycle이 있는 n-1 Permutation이고,n번째 원소가 독자적으로 Cycle을 이룬다.
2) 포함되는 경우
s(n1,k)s(n-1,k)은 k개의 Cycle이 있는 n-1 Permutation인데, 여기서 마지막 n번째 원소를 배치하는 경우의 수가 (n1)(n-1)가지 만큼 있다.

Catalan Number

n×nn \times n 격자에서 오른쪽 혹은 위쪽으로만 이동할때 대각선을 넘지 않는 경로의 갯수
Cn=(2nn)(2nn1)=(2nn)/(n+1)C_n = {2n \choose n} - {2n \choose n-1}= {2n \choose n}/(n+1) (전체 경로의 수에서 넘어가는 경로의 수를 뺀 것)
혹은,
Cn=k=1nCk1CnkC_n = \sum_{k=1}^nC_{k-1}C_{n-k}의 점화식으로도 나타낼 수 있음

Pigeonhole Principle

비둘기가 n마리 있고, 비둘기 집이 k개 있고 k<n이라면 어떤 비둘기 집은 적어도 2개의 비둘기가 있다.
f:XY,X>Yf: X\rightarrow Y, |X|>|Y| f(x1)=f(x2)f(x_1) = f(x_2) for some x1,x2X,x1x2x_1, x_2 \in X, x_1 \neq x_2
f:XYf : X \rightarrow Y X=n,Y=m|X|=n,|Y|=m , k=[nm]k = [{n \over m}]라 하면 적어도 kk개의 f(a1)=f(a2)=...=f(ak)f(a_1)=f(a_2)=...=f(a_k)인 서로 다른  a1,a2,...,akXa_1, a_2, ... , a_k \in X가 존재한다.