Lindström–Gessel–Viennot lemma는 DAG의 non-intersecting path를 셀 때 사용할 수 있는 공식이다.$G = (V, E)$에서 $2n$개의 정점 $a_{1}, \cdots, a_{n}$, $b_{1}, \cdots, b_{n}$을 생각하자. 어떤 두 path가 intersecting하다는 것은 둘 사이에 공통된 정점이 있다는 것이다. path tuple $P = (P_{1}, \cdots, P_{n})$에 대해 $P_{i}$가 $a_{i}$를 $b_{\sigma(i)}$로 보내고, $\sigma$가 순열이면 이러한 $P$를 path system이라고 하자. $P$가 non-intersecting이면 non-intersecting path system이라고 부르고, ..

조합론에서의 Cayley's theorem은 완전그래프 \(K_{n}\)의 서로 다른 spanning tree가 \(n^{n-2}\)개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : \([n] := \{1,\dots,n\}.\) Proof (By A. Joyal) \(K_{n}\)의 spanning tree의 개수를 \(t_{n}\)이라고 두고, \(n^{2}t_{n} = n^{n}\)임을 보인다. Definition. 정점 \(n \ge 1\)개의 트리 \(T\)에서 정점 \(a, b\)를 골라 \..

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 Stirling number \(S(n,k)\)에는 항상 제 2종 이라는 수식어가 붙는다. 교과서에서 보이지도 않는 제 1종 스털링 수가 뭐기에 더 쓸모가 많은 \(S(n,k)\)를 "제 2종"이라고 이름붙인 걸까? Notations & Preliminaries - \([n]\)은 양의 정수 집합 \(\{1,2,\cdots,n\}\)을 의미한다. - Falling factorial \(\displaystyle (x)_{k} := x(x-1)\cdots(x-k+1) = k! \cdot \begin{pmatrix}x\\k\end{pmatrix}\). - 제 2종 스털링 수의 조합적 의미를 깊게 다루지는 않는다. - 서술을 엄밀하게..

Pentagonal Number Theorem은 분할수 \(p(n)\)을 \(\mathcal{O}(n^{1.5})\)에 구할 수 있게 해주는 멋진 점화식이다. BOJ 문제는 모르고, Project Euler 78번 으로 연습해볼 수 있다. koosaga님이 추천해주신 꿀이 뚝뚝 떨어지는 왕기초 연습문제도 Codeforces에 있다. 생성함수에 대한 기본적인 지식을 전제한다. 이탤릭체로 표기된 용어는 임의로 지어낸 용어로, 공식적인 용어와 다를 수 있다. 분할수와 그 생성함수 자연수 \(n \ge 0\)의 분할수 \(p(n)\)이란, 합이 \(n\)이 되는 단조 감소하는 자연수열(분할)의 개수를 말한다. 물론 빈 수열의 합은 0이기 때문에 \(p(0) = 1\)이다. 엌ㅋㅋㅋㅋㅋ 좀 더 정상적인 예시로, ..

이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, \(n \ge 7\)에 대해 \(\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}\)이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 \(\ell_{n} \sim e^{n}\)이 성립하기 때문에, 충분히 큰 \(n\)에 대해서는 자명히 성립하는 부등식이다. 다만 PNT가 좀 overkill이기도 하고, 기왕 non-analytical한 증명이 있으니 이야기해보도록 하자. 증명은 다음의 글에서 가져왔다. https://math.stackexchange.com/questions/851328/textlcm1-2-3-ldots-n-geq-2n-for-n-ge..

Ore's theorem은 그래프에 해밀턴 회로가 존재할 조건과 관련된 정리이다. Statement를 바로 쓰면 다음과 같다. \(n \ge 3\)개의 정점으로 구성된 단순그래프 \(G\)에서, 모든 비인접(non-adjacent) 정점 \(x, y\)에 대해 \(\deg x + \deg y \ge n\)이 성립하면, \(G\)에는 해밀턴 회로가 존재한다. 여담으로 좀 더 강한 조건인 Dirac's theorem (모든 정점의 차수가 \(n/2\) 이상)도 있는데, 딱히 Ore's theorem 증명에 비해 쉬운지는 잘 모르겠다. 스포일러 방지선 Step 1. \(G\) is connected 두 정점 \(x\), \(y\)가 이미 인접(adjacent)한 경우에는 상관이 없다. \(x\)와 \(y\)가..