第25回近大数コン問5

下から $n$ ,左から $m$ の頂点を以下のように $(n,m)$ と名づける。
$$\begin{matrix} &&&&&&(6,0)\\ &&&&&(5,0)&(5,1)\\ &&&&(4,0)&(4,1)&(4,2)\\ &&&(3,0)&(3,1)&(3,2)&(3,3)\\ &&(2,0)&(2,1)&(2,2)&(2,3)&(2,4)\\ &(1,0)&(1,1)&(1,2)&(1,3)&(1,4)&(1,5)\\ (0,0)&(0,1)&(0,2)&(0,3)&(0,4)&(0,5)&(0,6)\\ \end{matrix}$$
$A=(0,0)$ から $(n,m)$までのパス全体に対する重みの合計を $A_{n,m}$ とする. $A$ から $(n,m)$ に向かう, パスのうち, $(n-1,k)\rightarrow (n,k-1)$ を通るパスの重みの合計は, $k\times A_{n-1,k}$ である.したがって,
$$A_{n,m}=\sum_{k=0}^{m+1}kA_{n-1,k}$$
が従う. ここで, 形式冪級数 $f_n(x)=\sum_{k=0}^{\infty}A_{n,k}x^k$ と置くと,
$$f_0(x)=1+x+x^2+\cdots=\frac{1}{1-x}$$
及び,
$$ \begin{align} \sum_{k=0}^{m+1}kA_{n-1,k}&=\sum_{k=0}^{m+1}[x^{k-1}]f_{n-1}^{\prime}(x)\\ &=[x^{m}]\frac{1}{1-x}f_{n-1}^{\prime}(x) \end{align}$$
が成立. 従って,
$$f_n(x)=\frac{1}{1-x}f_{n-1}^{\prime}(x)$$ であり,
$$\begin{align} f_0(x)&=\frac{1}{1-x}\\ f_1(x)&=\frac{1}{1-x}\bigg(\frac{1}{1-x}\bigg)^{\prime}=1\frac{1}{(1-x)^3}\\ f_2(x)&=\frac{1}{1-x}\bigg(1\times\frac{1}{(1-x)^3}\bigg)^{\prime}=1\times 3\frac{1}{(1-x)^5}\\ f_3(x)&=\frac{1}{1-x}\bigg(1\times3\frac{1}{(1-x)^5}\bigg)^{\prime}=1\times 3\times 5\frac{1}{(1-x)^7}\\ \end{align}$$
となり,
$$f_n(x)=(2n-1)!!\frac{1}{(1-x)^{2n+1}}$$
となる. 求める答えは $A_{k,0}=[x^0]f_{k}(x)=(2k-1)!!$.