斜方格子の通り道

114

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

格子通路の場合の数

二項係数は、格子（正方晶）の左下から頂点をくぐって右上までの通路の場合の数ですが、
二項係数の格子は東 $[1, 0]$ 北 $[0, 1]$ に進みます。
今回はそれに北東 $[0.5, 0.5]$ を追加します。
格子（斜方晶)には、斜めにも頂点がある為、二項係数だけでは使えません。

高さ!FORMULA[3][37639][0]幅!FORMULA[4][37670][0]斜方格子高さ $a$ 幅 $b$ 斜方格子

三項係数を使う

図2,図3,図4,図5を見ると、左上と右下から少しずつ頂点を外した奥行きを持つ立方体ができるのが分かります。

この奥行の線が斜線と考えて、三項係数が斜線を含んだ格子通路の場合の数になります。

斜方格子はズレているので、斜線上の頂点を通るためには、必ずもう一度斜線上の頂点を通らねばなりません。そうしないと正方格子として右上の頂点にはたどり着けない。

よって斜線を通る（奥行きに進む)には偶数回必要になります。
しかし斜線を通らない場合、
斜方格子中の正方格子としての場合の数である二項係数を足します。

上図.奥行2,!FORMULA[5][2061539926][0] 下図.奥行2,!FORMULA[6][-1345922728][0]の三項係数を持つと考える斜方格子上図.奥行2, $(a = 1, b = 1)$ 下図.奥行2, $(a = 2, b = 2)$ の三項係数を持つと考える斜方格子
$a = 2, b = 2$ の場合、奥行 $0$ の二項係数も足して、奥行きは $4, 2, 0$ まであります。そのため

$\begin{array}{r} (\begin{array}{cc} 2 + 2 \\ 4 (2 - 2) (2 - 2) \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 2 + 2 \\ 2 (2 - 1) (2 - 1) \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 2 + 2 \\ 2 2 \end{array}) \end{array}$

上図!FORMULA[13][683248615][0]奥行4，下図!FORMULA[14][711877797][0]奥行6 上図 $a = 2, b = 2$ 奥行4，下図 $a = 3, b = 3$ 奥行6
奥行2，上図!FORMULA[15][-1963925536][0]　下図!FORMULA[16][1490135618][0] 奥行2，上図 $a = b, (a = 3, b = 3)$ 　下図 $a \neq b, (a = 2, b = 3)$
奥行4，上図!FORMULA[17][-1963925536][0],　下図!FORMULA[18][1490135618][0], 奥行4，上図 $a = b, (a = 3, b = 3)$ ,　下図 $a \neq b, (a = 2, b = 3)$ ,
$a = 3, b = 3$ の場合、奥行きは $6, 4, 2, 0$ まであります。そのため

$\begin{array}{r} (\begin{array}{cc} 3 + 3 \\ 6 (3 - 3) (3 - 3) \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 3 + 3 \\ 4 (3 - 2) (3 - 2) \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 3 + 3 \\ 2 (3 - 1) (3 - 1) \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 3 + 3 \\ 3 3 \end{array}) \end{array}$ となりますので、
$(a - k)$ または $(b - k)$ が $0$ になるまで足していきます。

$\sum_{k = 0}^{a \lor b} \begin{array}{r} (\begin{array}{cc} a + b \\ 2 k （ a - k) （ b - k ） \end{array}) \end{array}$

と定義します。

奥行きが奇数の場合

斜方格子はズレていますのが、正方格子に戻る必要はないので、終着点に行くため必ず一度は斜線上の頂点を通る。偶数回斜線を通ったら正方格子に戻ってしまいます。
よって斜線を通る（奥行きに進む)には奇数回必要になります。奥行き偶数回は高さと幅は自然数ですが、奥行き奇数回の斜方格子は高さと幅は自然数 $+ 0.5$ 。
奇数の場合、右上図!FORMULA[30][-1916951783][0]右下図!FORMULA[31][-1720438278][0] 奇数の場合、右上図 $a = 2.5, b = 2.5$ 右下図 $a = 1.5, b = 2.5$

右上の図の例を見ると $a = 2.5, b = 2.5$ の場合、奥行きは $5, 3, 1$ まであります。そのため
$\begin{array}{r} (\begin{array}{cc} 2.5 + 2.5 \\ 1 2 2 \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 2.5 + 2.5 \\ 3 1 1 \end{array}) \end{array}$ + $\begin{array}{r} (\begin{array}{cc} 2.5 + 2.5 \\ 5 0 0 \end{array}) \end{array}$ となり、
$(a - (k - 1 / 2))$ または $(b - (k - 1 / 2))$ が $0$ になるまで足していきます。

$\sum_{k = 0}^{(a + 0.5) \lor (b + 0.5)} \begin{array}{r} (\begin{array}{cc} a + b \\ 2 k - 1 （ a - (k - 1 / 2)) （ b - (k - 1 / 2) ） \end{array}) \end{array}$

と定義します。

モツキン数との関係

上の図形を半分にしたらこんな感じ
奇数、偶数
格子の高さと幅が同値で、斜めに切断した図形から進めます。
この場合左下から右上までの行き方はカタラン数 $C_{n}$ を使って、さらにモツキン数 $M_{n}$ を作る。
カタラン数　
$(a + b = 2 n)$
$C_{n} = \frac{2 n!}{n! n!} \frac{1}{n + 1}$
モツキン数　
$M_{n}$ = $\sum_{k = 0}^{n / 2} \frac{n!}{2 k! (n - 2 k)!} C_{k}$ = $\sum_{k = 0}^{n / 2} \frac{n!}{2 k! (n - 2 k)!} \frac{2 k!}{k! k!} \frac{1}{k + 1}$
半分に切った奥行きが偶数回の斜方格子(公式1)で表すと(左辺）、偶数のモツキン数（右辺）になる。 $(a = b = 2 n / 2 = n)$

$\sum_{k = 0}^{n} \frac{2 n!}{2 k! 2 (n - k)!} \frac{2 (n - k)!}{(n - k)! (n - k)!} \frac{1}{(n - k) + 1}$ = $\sum_{k = 0}^{n} \frac{2 n!}{2 k! 2 (n - k)!} \frac{2 k!}{k! k!} \frac{1}{k + 1}$

半分に切った奥行きが奇数回の斜方格子(公式2)で表すと(左辺）、奇数のモツキン数（右辺）になる。 $(a = b = (2 n - 1) / 2 = n - 1 / 2)$

$\sum_{k = 0}^{n - 1 / 2} \frac{2 n - 1!}{2 k - 1! 2 (n - k)!} \frac{2 (n - k)!}{(n - k)! (n - k)!} \frac{1}{(n - k) + 1}$ = $\sum_{k = 0}^{n - 1 / 2} \frac{2 n - 1!}{2 k! 2 (n - k) - 1!} \frac{2 k!}{k! k!} \frac{1}{k + 1}$

左辺の $(n - k)$ が $n \to 0$ 、右辺の $k$ が $0 \to n$ になっていく等価なものです。

斜方格子通路の場合の数に戻ります。

斜めの線を切断しない場合、 $\frac{1}{k + 1}$ が必要ないので
モツキン数の公式の $\frac{1}{k + 1}$ を外せば、
$(a = b = n)$ , $(a = b = n - 1 / 2)$ の場合の斜方格子の通り道を偶数用(公式1)、奇数用(公式2)の二つに分けなくていい。

$\sum_{k = 0}^{n / 2} \frac{n!}{2 k! (n - 2 k)!} \frac{2 k!}{k! k!}$ = $\sum_{k = 0}^{n / 2} \frac{n!}{(n - 2 k)! k! k!}$

※ $(a = b = n)$ , $(a = b = n - 1 / 2)$ ではない(高さと幅の距離が同じでない)場合もあるので、高さもしくは幅において距離を追加する場合、追加距離 $m$ を付け加える。

$\sum_{k = 0}^{n / 2} \frac{(n + m)!}{(n - 2 k)! k! (k + m)!}$
$= \sum_{k = 0}^{n / 2} \begin{array}{r} (\begin{array}{cc} n + m \\ n - 2 k \end{array}) \end{array}$ $\begin{array}{r} (\begin{array}{cc} 2 k + m \\ k \end{array}) \end{array}$