2項係数と関連した話題

2項係数は, 高校数学でも登場する基本的な combinatorial number である。 その generating function が \((t+1)^n\) であるというのが二項定理である。

• 2項定理

代数的トポロジーを勉強し始めて本格的に2項係数を使うのは, コホモロジー作用素, つまり Adem relation を使うときだろう。

そのために, 2項係数を mod \(p\) で考えたときの公式を知っているとよい。 例えば, \begin{align*} n & = n_{0}+n_1p+\cdots +n_{k}p^k \\ m & = m_{0}+m_{1}p+\cdots +m_{k}p^k \end{align*}

を自然数 \(n\) と \(m\) の \(p\)進展開とするとき, mod \(p\) で \[ \binom{n}{m} \equiv \binom{n_{0}}{m_{0}}\binom{n_{1}}{m_{1}}\cdots \binom{n_{k}}{m_{k}} \] となる。これは Steenrod と Epstein [Ste62] では Lemma 2.6 として述べられているが, 元々誰が発見したのかよく分からない。 より古くは, Fine の [Fin47] に証明があるが, そこでは Lucas の本 “Theorie des Nombres” が参照されている。 Mestrovic [Meš] は Lucas の定理と呼び, その一般化などについて述べている。

代数的トポロジーではあまり使わないが, \(p\)巾を法とした公式もある。 Grinberg の [Gri] では, \(p^2\) を法とした公式が扱われている。

Adem relation の証明には, Bullett と MacDonald の 組み合せ論的なものがある。

• Bullett-MacDonald による Adem relation の証明 [BM82]

Adem relation の証明のときもそうであるが, 2項係数を掛けたものを足してできる数を単純な式で表せると便利である。 そのような公式を見つける方法としては, Wilf-Zeilberger 理論がある。 より一般に hypergeometric series についてのものであるが。

• Wilf-Zeilberger algorithm

原論文は Wilf と Zeilberger の [WZ90] であるが, Zeilberger の解説 [Zei] や Tefera による “WHAT IS \(\ldots \)” [Tef10] がある。またより詳しくは, Petkovšek と Wilf と Zeilberger の本 [PWZ96] を見るとよい。この本は Wilf のホームページから download できる。

2項係数には, quantum algebra 的な一般化である, \(q\)-binomial coefficients があり, 様々な場面で使われている。もう一つ変数を増やした \(q,t\)-binomial coefficients を Reiner と Stanton が [RS10] で定義している。Coskun によるもの [Cos] もある。

• \(q\)-binomial coefficients
• \(q,t\)-binomial coefficients

他にも, 古典的な組み合せ論的な関係式の quantum version も色々考えられている。MacMahon Master Theorem など。

• MacMahon Master Theorem

2項定理の一般化もある。 Blumen の [Blu] など。 Aguiar [Agu98; Agu00] は2項係数の braided analogue を定義し, その性質を調べている。

• binomial braids

Cano と Díaz [CD] は, continuous version を考えている。 その元になっているのは, 正方格子の lattice path の数としての2項係数の解釈である。彼等は “continuous directed path” の moduli space の体積として定義している。また Catalan number の continuous 版も定義している。

• continuous binomial coefficients

References

[Agu00]

Marcelo Aguiar. “Zonotopes, braids, and quantum groups”. In: Ann. Comb. 4.3-4 (2000). Conference on Combinatorics and Physics (Los Alamos, NM, 1998), pp. 433–468. url: http://dx.doi.org/10.1007/PL00001289.

[Agu98]

Marcelo Aguiar. “Braids, \(q\)-binomials, and quantum groups”. In: Adv. in Appl. Math. 20.3 (1998), pp. 323–365. url: http://dx.doi.org/10.1006/aama.1998.0585.

[Blu]

Sacha C. Blumen. Two generalisations of the Binomial theorem. arXiv: math/0512233.

[BM82]

S. R. Bullett and I. G. Macdonald. “On the Adem relations”. In: Topology 21.3 (1982), pp. 329–332. url: http://dx.doi.org/10.1016/0040-9383(82)90015-5.

[CD]

Leonardo Cano and Rafael Diaz. Continuous Analogues for the Binomial Coefficients and the Catalan Numbers. arXiv: 1602.09132.

[Cos]

Hasan Coskun. Multiple analogues of binomial coefficients and related families of special numbers. arXiv: 1001.3466.

[Fin47]

N. J. Fine. “Binomial coefficients modulo a prime”. In: Amer. Math. Monthly 54 (1947), pp. 589–592. url: http://dx.doi.org/10.2307/2304500.

[Gri]

Darij Grinberg. On binomial coefficients modulo squares of primes. arXiv: 1712.02095.

[Meš]

Romeo Meštrović. Lucas’ theorem: its generalizations, extensions and applications (1878–2014). arXiv: 1409.3820.

[PWZ96]

Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger. \(A=B\). With a foreword by Donald E. Knuth, With a separately available computer disk. Wellesley, MA: A K Peters Ltd., 1996, pp. xii+212. isbn: 1-56881-063-6. url: http://www.math.upenn.edu/~wilf/AeqB.html.

[RS10]

Victor Reiner and Dennis Stanton. “\((q,t)\)-analogues and \(\GL _n(\F _q)\)”. In: J. Algebraic Combin. 31.3 (2010), pp. 411–454. arXiv: 0804.3074. url: http://dx.doi.org/10.1007/s10801-009-0194-z.

[Ste62]

N. E. Steenrod. Cohomology operations. Lectures by N. E. Steenrod written and revised by D. B. A. Epstein. Annals of Mathematics Studies, No. 50. Princeton, N.J.: Princeton University Press, 1962, pp. vii+139.

[Tef10]

Akalu Tefera. “What is \(\dots \) a Wilf-Zeilberger pair?” In: Notices Amer. Math. Soc. 57.4 (2010), pp. 508–509.

[WZ90]

Herbert S. Wilf and Doron Zeilberger. “Rational functions certify combinatorial identities”. In: J. Amer. Math. Soc. 3.1 (1990), pp. 147–158. url: http://dx.doi.org/10.2307/1990986.

[Zei]

Doron Zeilberger. WZ Theory, Chapter II. arXiv: math/9811070.