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

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

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

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

이 포스팅에서 다룰 것은 AKS primality test에 사용하는 lemma 중 하나로, n≥7n \ge 7n≥7에 대해 ℓn:=lcm(1,2,...,n)≥2n\ell_{n} := \mathrm{lcm}(1,2, ... , n) \ge 2^{n}ℓn​:=lcm(1,2,...,n)≥2n이 성립한다는 것이다. 사실 Prime Number Theorem에 의해서 ℓn∼en\ell_{n} \sim e^{n}ℓn​∼en이 성립하기 때문에, 충분히 큰 nnn에 대해서는 자명히 성립하는 부등식이다. 다만 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≥3n \ge 3n≥3개의 정점으로 구성된 단순그래프 GGG에서, 모든 비인접(non-adjacent) 정점 x,yx, yx,y에 대해 deg⁡x+deg⁡y≥n\deg x + \deg y \ge ndegx+degy≥n이 성립하면, GGG에는 해밀턴 회로가 존재한다. 여담으로 좀 더 강한 조건인 Dirac's theorem (모든 정점의 차수가 n/2n/2n/2 이상)도 있는데, 딱히 Ore's theorem 증명에 비해 쉬운지는 잘 모르겠다. 스포일러 방지선 Step 1. GGG is connected 두 정점 xxx, yyy가 이미 인접(adjacent)한 경우에는 상관이 없다. xxx와 yyy가..