randomthoughts.hatenablog.com
randomthoughts.hatenablog.com
第1話では、グリコのゲームに関する確率の問題を設定し、そのあまりの複雑さに挫折した。ひとまず問題を単純化しようとし、単純化しすぎてこれも失敗した。
第2話では、グリコ問題よりは単純ではあるものの、ヒントを得るために十分複雑な問題を設定し、その過程で三項係数なるものの性質について探求した。三項係数の閉じた一般式を求めることには失敗したが、十分計算可能なシグマを含む式を得ることができ、ひとまず問題は解決とした。しかし、閉じた一般式の存在がどうしても気になる。林の奥にあるはずの宝を見てみたい。
三項係数の林の中で途方に暮れていた俺は、人類が発明した最強の情報収集装置、インターネットの助けを借りることにした。しかし、日本語で検索しても何も出てこない。三項係数とは俺が勝手に作った言葉なのだが、もし誰かがそのような概念をすでに作り出していたとしたらその人もそれを三項係数と名付けるだろうし、また少し言葉を変えて調べてみても、それらしい情報は一つも見当たらない。
そこで、英語で検索してみることにした。帰国子女の本領発揮である。三項係数を英語で言うとしたらどうなるだろう。二項係数がbinomial coefficientだから、trinomial coefficientかな？とりあえずこれで検索してみよう。
あった。一発で見つかってしまった。ページ数はかなり少ないものの、Trinomial Coefficientというタイトルのページが一つ見つかった。そのページはこれ。
しかもWolframのページだからかなり詳しく、信頼できそうだ。
三項係数の林には、先客がいた。森の奥深くの秘境であるとはいえ、やはり誰かがすでにここを探検していた。
このページの三項係数の説明を見てみよう。
A trinomial coefficient is a coefficient of the trinomial triangle. Following the notation of Andrews (1990), the trinomial coefficient \({{n}\choose{k}}_2\), with \(n \ge 0\) and \( -n \le k \le n\), is given by the coefficient of \(x^{n+k}\) in the expansion of \((1+x+x^2)^n\).
和訳すると、
三項係数とは、三項三角形の係数である。アンドリューズ(1990)の記法に従うと、\(n \ge 0\)かつ\( -n \le k \le n\)のとき、三項係数\({{n}\choose{k}}_2\)は、\((1+x+x^2)^n\)の展開式の\(x^{n+k}\)の係数によって与えられる。
まず、俺が「ジャクリーヌの三角形」と名付けた三角形は、"Trinomial triangle" 「三項三角形」という名がついているらしい。そして、アンドリューズなる人が1990年に三項係数について研究しており、三項係数を\({{n}\choose{k}}_2\)と表している。俺はこれを\(_nT_r\)と表記したから、表記は若干ずれている。まあ欧米では二項係数を\(_nC_r\)ではなく\({n}\choose{r}\)と表すのが一般的だから、不思議なことではない。
一番興味深いのが、三項係数が、\( -n \le k \le n\)のとき、\((1+x+x^2)^n\)の展開式の\(x^{n+k}\)の係数だと定義されていることだ。俺は三項係数を\(0 \le k \le 2n\)のとき、\((1+x+x^2)^n\)の展開式の\(x^k\)の係数と定義した。俺は二項係数と同様にkを0から数え始めたが、ここで用いられている定義は、三項三角形の中央の値をk=0とし、左端をk=-n、右端をk=nと表している。対称性を重視した定義といえる。よって、俺の定義とアンドリューズの定義には、次のような関係が成り立つ。
\[
_nT_k = {{n}\choose{k-n}}_2
\]
また、
\[
_nT_k = _nT_{2n-k}
\]
\[
_nT_k = _{n-1}T_{k-2} + _{n-1}T_{k-1} + _{n-1}T_k
\]
という関係式は、
\[
{{n}\choose{k}}_2 = {{n}\choose{-k}}_2
\]
\[
{{n}\choose{k}}_2 = {{n-1}\choose{k-1}}_2 + {{n-1}\choose{k}}_2 + {{n-1}\choose{k+1}}_2
\]
という関係式に対応する。こちらの方が、対称性がよく表されていてきれいな気がする。
ちゃんとした定義と形は少々違うが、ここまで近く、本質的に等しいものを自力で作り出せたことに強く感動した。
ここで、本題である、三項係数の閉じた一般式についての記述を読んでみよう。
The trinomial coefficient can be given by the closed form
\[
{{n}\choose{k}}_2 = \begin{cases}
1 \quad \text{for} \quad n=k=0 \\
C_{k+n}^{(-n)}(-\frac{1}{2}) \quad \text{otherwise,}
\end{cases}
\]
where \(C_n^{(\lambda)}(z)\) is a Gegenbauer polynomial.
？？？
n=k=0の時に1なのはわかるよ。でもGegenbauer polynomialって何だ？
Wolframの説明を見ても意味不明だったので、Wikipediaの説明を見てみる。
数学において、ゲーゲンバウアー多項式 (Gegenbauer polynomials) または超球多項式 (ultraspherical polynomials) \(C_n^{(\alpha)} (x)\)とは、レオポルド・ベルンハルト・ゲーゲンバウアー(1849–1903) にちなんで命名された、区間\([-1,1]\)上で定義される重み関数\((1-x^2)^{\alpha -\frac{1}{2}}\)の直交多項式をいう。ゲーゲンバウアー多項式は、ルジャンドル多項式及びチェビシェフ多項式の一般事例であり、ヤコビ多項式の特殊事例である。
なるほどね。よくわかったよ。とても分かりやすいね。
これが何を意味するのかは、皆さん自分で調べてみてください。俺は何一つ理解できませんでした。
倒木の先には確かに宝があったが、それは険しく高い、ゲーゲンバウアーの崖の上にあった。その上からの眺め想像を絶するほど美しいのだろうが、今の俺の実力では、登るどころか、足をかけることもできそうにない。ただ下から、絶望的に切り立った断崖を見上げ、その上の景色に思いをはせるのみだ。
唯一役に立ちそうなことは、ゲーゲンバウアー多項式の満たす漸化式だ。それは以下のようなものである。
\[
\begin{align}
C_{0}^{(\alpha )}(x) &= 1 \\
C_{1}^{(\alpha )}(x) &= 2 \alpha x \\
C_{n}^{(\alpha )}(x) &= {\frac{1}{n}} \left[2x(n+\alpha -1)C_{n-1}^{(\alpha )}(x)-(n+2\alpha -2)C_{n-2}^{(\alpha )}(x)\right]
\end{align}
\]
これと、俺が第2話で導いた式
\[
\begin{align}
_nT_0 &= 1 \\
_nT_1 &= n \\
_nT_2 &= \frac{1}{2} n(n+1) \\
_nT_r &= _{n-1}T_{r-2} + _{n-1}T_{r-1} + _{n-1}T_r
\end{align}
\]
を比較してみよう。
\[
\begin{align}
_nT_0 &= {{n}\choose{-n}}_2 = C_0^{(-n)}(-\frac{1}{2}) = 1 \\
_nT_1 &= {{n}\choose{-n+1}}_2 = C_1^{(-n)}(-\frac{1}{2}) = 2 (-n) \left(-\frac{1}{2}\right) = n \\
_nT_2 &= {{n}\choose{-n+2}}_2 = C_2^{(-n)}(-\frac{1}{2}) \\
&= {\frac{1}{2}} \left[2\left(-\frac{1}{2}\right)(2-n -1)C_{1}^{(-n)}(-\frac{1}{2})-(2-2n -2)C_{0}^{(-n)}(-\frac{1}{2})\right] \\
&= {\frac{1}{2}} \left[(n-1)C_{1}^{(-n)}(-\frac{1}{2})+2nC_{0}^{(-n)}(-\frac{1}{2})\right] \\
&= {\frac{1}{2}} \left[(n-1)n+2n\right] \\
&= {\frac{1}{2}} n(n+1)
\end{align}
\]
ここまではあってるぞ。では一般的な漸化式について比較してみよう。
\[
\begin{align}
_nT_r &= {{n}\choose{-n+r}}_2 = C_r^{(-n)}(-\frac{1}{2}) \\
&= {\frac{1}{r}} \left[2\left(-\frac{1}{2}\right)(r-n -1)C_{r-1}^{(-n)}(-\frac{1}{2})-(r-2n -2)C_{r-2}^{(-n)}(-\frac{1}{2})\right] \\
&= {\frac{1}{r}} \left[(n-r+1)C_{r-1}^{(-n)}(-\frac{1}{2})+(2n-r+2)C_{r-2}^{(-n)}(-\frac{1}{2})\right] \\
\end{align}
\]
あれ、これ以上簡単にならないぞ。なぜか考えてみると、俺が導きたい漸化式は三項三角形で、三項係数とその左上と、真上と、右上の項の間に成り立つ漸化式だが、上の式は三項係数とその左と2つ左との間に成り立つ式だ。一つ上の段との関係ではなく、一つの段のなかでの関係なのだ。
しかしそれはそれでよしとしよう。新しい漸化式が得られた。
\[
_nT_r = {\frac{1}{r}} \left[(n-r+1) _nT_{r-1}+(2n-r+2) _nT_{r-2}\right]
\]
しかし、どうやらこれ以上先へは進めないようだ。
これまで、三項係数について深く研究してきた。すべてを理解し、ゲーゲンバウアーの崖を上ることには及ばなかったが、三項係数の性質について多くのことを知ることができ、単純化したグリコ問題を（ほとんど）解くことができた。これから、単純化したグリコ問題を解くプロセスで学んだことを武器に、グリコの洞窟に戻る。
第4話に続く
