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

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.

성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

합의 법칙 곱의 법칙 순열 조합 이항정리, 집합의 분할 등 고교 과정과 겹치는것은 생략

3-Permutation of 3-Set을 예시로 살펴보자.

(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)$ = Number of n-Permutation with k-Cycles = Stirling Number of 1st Kind = 제 1종 스털링 수

위의 예시에서는

처럼 나타낼 수 있다.

제 1종 스털링 수는 다음과 같은 관계가 성립함.

이를 조합론적으로 증명해보면, n번째 원소가 다른 Cycle에 포함되느냐 포함되지 않느냐로 나눠서

$s(n-1,k-1)$은 k-1개의 Cycle이 있는 n-1 Permutation이고,n번째 원소가 독자적으로 Cycle을 이룬다.

$s(n-1,k)$은 k개의 Cycle이 있는 n-1 Permutation인데, 여기서 마지막 n번째 원소를 배치하는 경우의 수가 $(n-1)$가지 만큼 있다.

$n \times n$ 격자에서 오른쪽 혹은 위쪽으로만 이동할때 대각선을 넘지 않는 경로의 갯수

$C_n = {2n \choose n} - {2n \choose n-1}= {2n \choose n}/(n+1)$ (전체 경로의 수에서 넘어가는 경로의 수를 뺀 것)

혹은,

$C_n = \sum_{k=1}^nC_{k-1}C_{n-k}$의 점화식으로도 나타낼 수 있음