グリコの洞窟の宝を見つけるヒントを得るために、俺が次に設定した問題は、次のようなものである。
持ち点は最初0点で、毎ターンに1/3の確率で0点、1/3の確率で1点、1/3の確率で2点を追加する。mターン後に得点がn点である確率を求めよ。
前回と同様に、横軸にm、縦軸にnを取り、確率の値を表に表す。今回は約分せずに分母をそろえて書き出してみると、
とりあえず、nの最初のいくつかの値について一般項を求めてみると（導出は省略、漸化式を繰り返し用いる）、
\[
\begin{align}
p(m,0) &= \left( \frac{1}{3} \right)^m \\
p(m,1) &= m \left( \frac{1}{3} \right)^m \\
p(m,2) &= \frac{m(m+1)}{2} \left( \frac{1}{3} \right)^m \\
p(m,3) &= \frac{m(m-1)(m+4)}{6} \left( \frac{1}{3} \right)^m \\
p(m,4) &= \frac{m(m-1)(m^2+7m-6)}{24} \left( \frac{1}{3} \right)^m
\end{align}
\]
これだけでは、ぱっと見ではあまり有用なパターンは見えない。しかし、表を見ると、今回は得点を追加する確率がすべて等しいので、きれいな対称性が現れることがわかる。この対称性をよりはっきり表すために、分子だけを取って左右対称に並べてみよう。
似たようなものをどこかで見たことがあるぞ。そう、これはパスカルの三角形に非常によく似ている。パスカルの三角形は、次の図のように、右上の数字と左上の数字を足し合わせたものを次々と書き並べていっているものだ。そして上の三角形は、左上と、真上と、右上の数字を足し合わせていったものを並べていったものである。上の三角形は、パスカルの三角形の、3つバージョンといえる。この三角形を、「ジャクリーヌの三角形」と名付けてみる。ジャクリーヌは、パスカルの妹の名前である。勝手に適当につけたけど、「そうたの三角形」とかつけるよりは痛くないだろう。
パスカルの三角形に現れる数字を二項係数といい、n段目の左からr番目（どちらも0から数え始める）の数字を\(_nC_r\)と表すのは知っているだろう。同様に、ジャクリーヌの三角形の数字を三項係数といい、n段目、左からr番目の数字を\(_nT_r\)と表してみる。これは既存の数学の用語、表記ではなく、俺が勝手に作った。しかし、日本語で検索しても、それらしいものは何もなかったので、自分で数学を作り上げることにした。
俺が足を踏み入れた密林は、まだ名前もついていない、未開の地だったようだ。誰も足を踏み入れたことのない場所を冒険するわくわくを胸に、俺はさらに奥へと進むことにした。これから、三項係数の性質をさらに探ってゆく。
さて、パスカルの三角形とジャクリーヌの三角形は見た目が似ているだけではない。様々な共通の性質を持っている。まず、次のような漸化式が成り立つ。
\[
\begin{align}
_nC_r &= _{n-1}C_{r-1} + _{n-1}C_r \\
_nT_r &= _{n-1}T_{r-2} + _{n-1}T_{r-1} + _{n-1}T_r
\end{align}
\]
二項係数の方は「左上と右上を足す」、三項係数の方は「左上と真上と右上を足す」という性質を表している。さらに、対称性から、次の等式も成り立つ。
\[
\begin{align}
_nC_r &= _nC_{n-r} \\
_nT_r &= _nT_{2n-r}
\end{align}
\]
このように、二項係数と三項係数は似た性質を持つことがわかる。今度は逆に、二項係数について知られている性質から、三項係数のそれに対応する性質を探っていこうと思う。
パスカルの三角形で、n段目の数字をすべて足し合わせると、\(2^n\)になることが知られている。ジャクリーヌの三角形では、n段目の数字を足し合わせると、何になるだろうか。
最初に挙げた表で、縦に並んだ数字をすべて足し合わせると、確率の和は1になるはずだから、当然1である。mターン後の確率の、分母は\(3^m\)だから、分子の和も\(3^m\)になるはずである。ところで、mターン後の確率の分子は、m段目の三項係数だから、ジャクリーヌの三角形のm段目の数字を足し合わせると、\(3^m\)になりそうである。試しに、4段目の数字をすべて足し合わせると81となり、これは確かに\(3^4\)である。
また、二項係数\(_nC_r\)は、\( (x+1)^n \)の展開式の\(x^r\)の係数であることも有名である。このことは、次のように表せる。
\[
(x+1)^n = _nC_0 x^0 + _nC_1 x^1 + _nC_2 x^2 + \dots + _nC_r x^r + \dots + _nC_{n-1} x^{n-1} + _nC_n x^n
\]
この式で、\(x=1\)とすると、左辺は\(2^n\)、右辺は二項係数の総和となるから、パスカルの三角形のn段目の総和が\(2^n\)になるという事実が証明される。
同様に、三項係数も、ある多項式の展開式の係数として表せないだろうか？その多項式に\(x=1\)を代入すると、3となるはずである。なぜなら、三項係数の和は\(3^n\)だからである。そして、\(_nT_r\)のrは0から2nまでの値を取りうるから、その展開式には\(x^{2n}\)という項が現れるはずである。よって、その多項式はおそらく2次式である。\(x=1\)のとき3となるもっとも簡単な2次式といえば、\(x^2+x+1\)である。試しに\((x^2+x+1)^2\)を展開してみると、\(x^4+2x^3+3x^2+2x+1\)となる。これはジャクリーヌの三角形の2段目の値と一致する。念のため、\((x^2+x+1)^3\)も頑張って展開してみると、\(x^6+3x^5+6x^4+7x^3+6x^2+3x+1\)となり、これもぴたりと一致する！このことから、次の式が成り立つようだ。
\[
(x^2+x+1)^n = _nT_0 x^0 + _nT_1 x^1 + _nT_2 x^2 + \dots + _nT_r x^r + \dots + _nT_{2n-1} x^{2n-1} + _nT_{2n} x^{2n} \tag{1}
\]
この式を使うと、三項係数の様々な性質を導くことができる。(1)式で\(x=1\)として、
\[
_nT_0 + _nT_1 + _nT_2 + \dots + _nT_{2k} + _nT_{2k+1} + \dots + _nT_{2n-1} + _nT_{2n} = 3^n \tag{2}
\]
\(x=-1\)として、
\[
_nT_0 - _nT_1 + _nT_2 - \dots + _nT_{2k} - _nT_{2k+1} + \dots - _nT_{2n-1} + _nT_{2n} = 1
\]
辺々足し引きすると、次の2式が得られる。
\[
\begin{align}
_nT_0 + _nT_2 + _nT_4 + \dots + _nT_{2k} + \dots + _nT_{2n} &= \frac{3^n+1}{2} \\
_nT_1 + _nT_3 + _nT_5 + \dots + _nT_{2k+1} + \dots + _nT_{2n-1} &= \frac{3^n-1}{2}
\end{align}
\]
さらに、\(\omega\)を1の3乗根の虚数のものの一つとし、(1)式で\(x=\omega,x=\omega^2\)とすると、
\[
\begin{align}
_nT_0 + _nT_1 \omega + _nT_2 \omega^2 + \dots + _nT_{3l} + _nT_{3l+1} \omega + _nT_{3l+2} \omega^2 + \dots &= 0 \\
_nT_0 + _nT_1 \omega^2 + _nT_2 \omega + \dots + _nT_{3l} + _nT_{3l+1} \omega^2 + _nT_{3l+2} \omega + \dots &= 0
\end{align}
\]
これらを足し合わせると、
\[
2 _nT_0 - _nT_1 - _nT_2 + \dots +2 _nT_{3l} - _nT_{3l+1} - _nT_{3l+2} + \dots = 0 \tag{3}
\]
(2)と(3)を足し合わせることによって、次の式が得られる。
\[
_nT_0 + _nT_3 + _nT_6 + \dots + _nT_{3l} + \dots = 3^{n-1}
\]
対称性から、おそらく\(_nT_{3l+1}\)と\(_nT_{3l+2}\)の和も同じく\(3^{n-1}\)となり、実際にジャクリーヌの三角形を書き出して計算してみると成り立っているが、証明はまだできていない。
三項係数の様々な性質が分かったところで、本来の目的である、三項係数の閉じた一般式を求めることに挑戦したい。二項係数の場合は、次の式が成り立つ。
\[
_nC_r = \frac{n!}{r!(n-r)!}
\]
\(_nT_r\)の一般式を、\((x^2+x+1)^n\)の展開式を利用して求めてみたい。多項定理から、次の式が成り立つ。
\[
\begin{align}
(x^2+x+1)^n &= \sum_{\substack{a+b+c=n \\ a,b,c \ge 0}} \frac{n!}{a!b!c!} (x^2)^a x^b 1^c \\
&= \sum_{\substack{a+b+c=n \\ a,b,c \ge 0}} \frac{n!}{a!b!c!} x^{2a+b}
\end{align}
\]
よって、\(x^r\)の係数は、
\[
_nT_r = \sum_{\substack{a+b+c=n \\ 2a+b=r \\ a,b,c \ge 0}} \frac{n!}{a!b!c!}
\]
例えば、\(_5T_3\)の場合、\(a+b+c=5, \quad 2a+b=3, \quad a,b,c \ge 0\)を満たすa,b,cの組は、\((a,b,c) = (0, 3, 2), (1, 1, 3)\)の二つだから、\(_5T_3 = \frac{5!}{0!3!2!} + \frac{5!}{1!1!3!} = 30\)と求まる。
これでは文字が多すぎるから、文字を減らしてみたい。rが偶数の時、\(r=2l\)とし、a,b,cの取りうる値を一般の場合において書き出してみると、
\[
\begin{align}
a &= 0, 1, 2, \dots, k, \dots, l \\
b &= 2l, 2l-2, 2l-4, \dots, 2l-2k, \dots, 0 \\
c &= n-2l, n-2l+1, n-2l+2, \dots, n-2l+k, \dots, n-l
\end{align}
\]
よって、
\[
\begin{align}
_nT_r &= \sum_{k=0}^{l} \frac{n!}{k!(2l-2k)!(n-2l+k)!} \\
&= \sum_{k=0}^{l} \frac{n!}{(2l-k)!(n-2l+k)!} \frac{(2l-k)!}{k!(2l-2k)!} \\
&= \sum_{k=0}^{l} {}_nC_{2l-k} \cdot {}_{2l-k}C_k
\end{align}
\]
\(r=2l+1\)の時も同様に、
\[
\begin{align}
a &= 0, 1, 2, \dots, k, \dots, l \\
b &= 2l+1, 2l-1, 2l-3, \dots, 2l-2k+1, \dots, 1 \\
c &= n-2l-1, n-2l, n-2l+1, \dots, n-2l+k-1, \dots, n-l-1
\end{align}
\]
\[
\begin{align}
_nT_r &= \sum_{k=0}^{l} \frac{n!}{k!(2l-2k+1)!(n-2l+k-1)!} \\
&= \sum_{k=0}^{l} \frac{n!}{(2l-k+1)!(n-2l+k-1)!} \frac{(2l-k+1)!}{k!(2l-2k+1)!} \\
&= \sum_{k=0}^{l} {}_nC_{2l-k+1} \cdot {}_{2l-k+1}C_k
\end{align}
\]
これらを一つの式にまとめて、
\[
_nT_r = \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor} {}_nC_{r-k} \cdot {}_{r-k}C_k \tag{*}
\]
試しに\(_5T_3\)の値を計算してみると、\(_5T_3 = \sum_{k=0}^{1} {}_5C_{3-k} \cdot {}_{3-k}C_k = _5C_3 \cdot _3C_0 + _5C_2 \cdot _2C_1 = 10 \cdot 1 + 10 \cdot 2 = 30\)となり、確かに成り立つ。
だいぶきれいな式が得られたが、まだ満足できない。シグマ記号のない、閉じた式が欲しいのだ。数字を代入するだけで、値が得られる公式を。しかし、この式を計算することは、現在の俺の知識では不可能だ。またしても、手詰まりだ。三項係数の林は、倒木でふさがれていた。
とはいえ、(*)式は容易に計算でき、ある程度シンプルなので良しとする。こうして俺は三項係数\(_nT_r\)という武器を手に入れた。ここで、最初の問題に戻ってみよう。
持ち点は最初0点で、毎ターンに1/3の確率で0点、1/3の確率で1点、1/3の確率で2点を追加する。mターン後に得点がn点である確率を求めよ。
俺はすでに、この問題に対する答えを知っている。これは明らかに
\[
p(m,n) = \frac{_mT_n}{3^m} = \sum_{k=0}^{\lfloor \frac{r}{2} \rfloor} {}_nC_{r-k} \cdot {}_{r-k}C_k \left( \frac{1}{3} \right)^m
\]
が答えである。
閉じた一般式を求めるという本来の目的は達成することができなかったが、容易に計算可能なシグマを含む式で妥協することによって、単純化したグリコ問題の解を求めることができた。
それでも俺は満足できなかった。道をふさいだ倒木の先に、何があるのかをこの目で確かめてみたかった。少なくとも、先に行くことができなくても、そこに何があるかを知りたかった。しかし、助けを求めようとしても、日本語で検索しても何も出てこない。やはり俺がここに初めて迷い込んだ人物で、自分で開拓していかなければならないのだろうか。
ちょっと待て、英語で検索してみればよいではないか。
第3話に続く
