고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 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
여기서 다음을 정의하자.
= Number of n-Permutation with k-Cycles = Stirling Number of 1st Kind = 제 1종 스털링 수
위의 예시에서는
처럼 나타낼 수 있다.
제 1종 스털링 수는 다음과 같은 관계가 성립함.
이를 조합론적으로 증명해보면, n번째 원소가 다른 Cycle에 포함되느냐 포함되지 않느냐로 나눠서
1) 포함되지 않는 경우
은 k-1개의 Cycle이 있는 n-1 Permutation이고,n번째 원소가 독자적으로 Cycle을 이룬다.
2) 포함되는 경우
은 k개의 Cycle이 있는 n-1 Permutation인데, 여기서 마지막 n번째 원소를 배치하는 경우의 수가 가지 만큼 있다.
Catalan Number
격자에서 오른쪽 혹은 위쪽으로만 이동할때 대각선을 넘지 않는 경로의 갯수
(전체 경로의 수에서 넘어가는 경로의 수를 뺀 것)
혹은,
의 점화식으로도 나타낼 수 있음
Pigeonhole Principle
•
비둘기가 n마리 있고, 비둘기 집이 k개 있고 k<n이라면 어떤 비둘기 집은 적어도 2개의 비둘기가 있다.
•
⇒ for some
•
, 라 하면 적어도 개의 인 서로 다른 가 존재한다.