조합론에서의 Cayley’s theorem은 완전그래프 $K_{n}$의 서로 다른 spanning tree가 $n^{n-2}$개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : $[n] := \set{1,\dots,n}.$ Proof of the theorem (By A. Joyal) $K_{n}$의 spanning tree의 개수를 $t_{n}$이라고 두고, $n^{2}t_{n} = n^{n}$임을 보인다. Definition. 정점 $n \ge 1$개의 트리 $T$에서 정점 $a, b$를 골라 $a$를 start, $b$를 end로 부르자....
Grundy Number는 PS에서 굉장히 자주 쓰이는 데 비해 그 증명이나 수학적 배경이 잘 알려져 있지 않다. 앞으로 일련의 포스팅에서는 Sprague-Grundy Theorem에 대해 공부한 것을 PS 스타일로 정리하려 한다. 그 중에서 이 글은 Grundy Number의 정의와 Sprague-Grundy theorem의 증명에 대해 다룬다. Nim-Game의 필승 전략에 대한 사전 지식이 필요하며, 문제풀이에 최적화된 글이기 때문에 statement가 실제 theorem의 내용과는 다소 차이가 있다. References sirkingnightingfail, “A Blog on Sprague-Grundy Theorem” Wikipedia: Sprague-Grundy theorem Definition of Game “게임”은 상당히 광범위한 용어이지만, Sprague-Grundy theorem의 영향 아래 있는 “Game”은 다음의 조건을 만족하는 일종의 state collection을 말한다....