コンボリューションを考える

数学ガールの第7章、コンボリューションを読んでるだけでは理解できなかったので手を動かしてみることにした

母関数の積までは読んでて理解できたので図書室からスタート

前提の問題

 \displaystyle

\begin{align} 0 + 1 + 2 &= (0 + (1 + 2) ) \\ &= ((0 + 1) + 2) \\ \end{align} 2なら2通り ( C_2 = 2 ) \begin{align} 0 + 1 + 2+ 3 + ... + n &= ? \\ \end{align} nなら何通りか( C_n = ?)

だいたいこんな感じ、正直詳しく知りたい人は本買おう

ミルカさんの解

私が理解したところ

  •  C_n =(SからGまでの経路数) - (SからG'までの経路数)

やること

  • 下降階乗冪をフル回転

下降階乗冪をフル回転

\begin{align} \begin{split} C_n &= \begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n+1 \end{pmatrix} \\ &= \frac{(2n-0)(2n-1)(2n-2)...\bigl(2n - (n-1) \bigr) }{(n-0)(n-1)(n-2)...\bigl(n-(n-1) \bigr)} - \\ &\quad \frac{(2n-0)(2n-1)(2n-2)...\bigl(2n-(n+1-1)\bigr)}{(n+1-0)(n+1-1)(n+1-2)...\bigl(n+1-(n+1 -1)\bigr)} \\ &= \frac{(2n)^\underline{n}}{(n)^\underline{n}} - \frac{(2n)^\underline{n+1}}{(n+1)^\underline{n+1}} \end{split} \end{align}

でこの後通分を行う。書籍にはない2番目の式を見ると

分子は \begin{align} &\quad(2n-0)(2n-1)(2n-2)...\bigl(2n-(n+1-1)\bigr) \\ &=(2n-0)(2n-1)(2n-2)...\bigl(2n-(n-1)\bigr)(n) \\ &= (2n)^\underline{n}・n \end{align}

分母は \begin{align} &\quad(n+1-0)(n+1-1)(n+1-2)...\bigl(n+1-(n+1 -1)\bigr) \\ &=(n+1)・(n-0)・(n-1)・...・3・2・1 \\ &= (n+1)・(n)^\underline{n} \end{align}

ということで最終的な式は以下のようになる

\begin{align} \frac{(n+1)・(2n)^\underline{n}}{(n+1)・(n)^\underline{n}} -\frac{(2n)^\underline{n}・(n)}{(n+1)・(n)^\underline{n}} \end{align}

後は計算をするだけだった。要は私は下降階乗冪がよくわかってなかったため理解できなかった。

結論は

\begin{align} C_n = \frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} \end{align}

母関数へ旅をする

読んでて理解したのは母関数の閉じた式を入手したところ、そこから先を「僕」と同じように手を動かして進める。

まずは母関数の式

\begin{align} C(x) = \frac{1 \pm \sqrt{1-4x}}{2x} \end{align}

C(0)を考えると C_+(x)は不適であることになる。 そのため下の式を考える \begin{align} C(x) = \frac{1 - \sqrt{1-4x}}{2x} \end{align}

 \sqrt{1-4x}が邪魔なのでこれを冪級数 [tex:\sum_{k=0}^∞ K_k xk]を利用する

で、ここまで来て何なのだが、texで書くの疲れたのでこっからは写真.....、メモに見えてる某企業は何も関係ありません。たまたま近くにあったメモだったので使いました。

f:id:kataware8136:20180501151810j:plain

f:id:kataware8136:20180501152450j:plain f:id:kataware8136:20180501152457j:plain

母関数の国から数列の国へと帰ってきました。

感想

手を動かしてみると、読んでる時わからなかったのが理解できるようになったので、もし読んでるだけでわかりにくかったら手を動かすといいと思います。

無限級数の時の和の順序の変更には条件をきちんと述べる必要があるらしいのでそこらへんを調べにいってきます。