数え挙げの手法

物を数えるというのは数学の基本である。代数的トポロジーでも, もちろん重要である。高校のころから慣れ親しんでいる (?) 二項係数も, 代数的トポロジーでの計算で登場する。例えば, コホモロジー作用素の計算などで。

• 二項係数 (binomial coefficients)

二項係数 \(\binom{n}{k}\) は, \(n\)個のものから \(k\)個のものを選ぶ場合の数であるが, 他にも数え上げるものはいろいろある。 凸多面体の中の lattice point の数とか。Spanning tree の数を数えると parking function や Catalan number などの概念を得る。 順番に大小関係が入れ替わっている permutation (alternating permutation と呼ぶ) の数を数えると Euler number というものになる。Stanley は [Sta10] という alternating permutation についての survey を書いている。

• parking function
• Catalan number
• Euler number

Joyal は, [Joy81] で, 有限集合から構成されるものを数え上げるための概念として species というものを導入した。

• species

Grassmann多様体の totally positive part の cell を数え上げるために, Steingrimsson と Williams は [SW07] で permutation tableaux というものを導入した。

• permutation tableaux

有限集合の様々な分割の仕方についてまとめたものとして, Proctor の [Pro] がある。

References

[Joy81]

André Joyal. “Une théorie combinatoire des séries formelles”. In: Adv. in Math. 42.1 (1981), pp. 1–82. url: http://dx.doi.org/10.1016/0001-8708(81)90052-9.

[Pro]

Robert A. Proctor. Let’s Expand Rota’s Twelvefold Way For Counting Partitions! arXiv: math/0606404.

[Sta10]

Richard P. Stanley. “A survey of alternating permutations”. In: Combinatorics and graphs. Vol. 531. Contemp. Math. Providence, RI: Amer. Math. Soc., 2010, pp. 165–196. arXiv: 0912.4240.

[SW07]

Einar Steingrı́msson and Lauren K. Williams. “Permutation tableaux and permutation patterns”. In: J. Combin. Theory Ser. A 114.2 (2007), pp. 211–234. arXiv: math/0507149. url: http://dx.doi.org/10.1016/j.jcta.2006.04.001.