1. 概要 本記事では，数え上げに関する Cycle Lemma と呼ばれる定理を紹介します． これはある種の整数列について，列の巡回シフトのうち，累積和が常に正になるものの個数を決定するもので，主張も証明も易しいです．本記事では Cycle Lemma を証明し，そこ…

1. 概要 本記事では，parking function（駐車関数）と呼ばれる数列の個数を数え上げる問題を解説します． Parking function はハッシュテーブルの研究などに関連して現れた組合せ論的対象です．またその呼称の通り，駐車場に車を停めるというユニークな問題…