初投稿です。今後使いそうなのでここに置いておきます。
問題
$%$2次元$xy$座標平面上の移動を考える。移動時には、1ステップごとに今いる座標から上下左右のいずれかの方向に1だけ動ける。つまり、ある時点で$(x, y)$にいたとすると、その1ステップ後には$(x+1, y),(x-1, y),(x, y+1),(x, y-1)$のいずれかに移動するとする。このとき、$X, Y$を整数として、原点$(0, 0)$から$(X, Y)$まで$N$ステップで移動する方法は何通りあるか？
関連問題
この問題の考え方が使えるであろうAtCoderの問題です。
[ABC011-D] https://atcoder.jp/contests/abc011/tasks/abc011_4
[ARC012-D] https://atcoder.jp/contests/arc012/tasks/arc012_4
求解
前準備
$%$まず、$X, Y$の正負によらず、原点$(0, 0)$から$(X, Y)$まで行くときの最短手数は、そのマンハッタン距離です。よって、$X, Y$に絶対値をつけて第一象限および$x$軸, $y$軸の非負方向上での問題として考えることとします。
移動可能な条件
$%$当然ですが2点間のマンハッタン距離が$N$を超えるような場合は到達不可能です。また、$N\equiv X + Y(\mathrm{mod},,2)$が成り立たない場合も到達不可能です。よってこの2つのいずれかにあてはまる場合の答えは、0となります。以下の議論では、到達可能な場合について考えます。
具体的な計算
上下左右のそれぞれの方向に進む手数を$n_U, n_D, n_L, n_R$とします。このとき、この4つが満たすべき条件は、
n_U - n_D = Y \\
n_R - n_L = X \\
n_U + n_D + n_R + n_L = N \\
n_U \ge 0, n_D \ge 0, n_R \ge 0, n_L \ge 0 \\
n_U, n_D, n_R, n_L は整数
$%$です。等式が3つなので1つの自由度があるという感じでしょうか。$(n_U, n_D, n_L, n_R)$の組み合わせのうちで、この条件を満たすものすべてに対して、それぞれどの順序でどの方向に進むかが何通りあるか求めて足し合わせれば良いです。
$%$ここで、上の条件を満たす$(n_U, n_D, n_L, n_R)$の組を$C_{N, X, Y}$とします。求めたい場合の数を$P$とすると、
P = \sum_{(n_U, n_D, n_R, n_L)\in C_{N, X, Y}}\dfrac{N!}{n_U!n_D!n_R!n_L!}
$%$となります。条件式より、$n_U, n_D, n_L, n_R$のうち3つは残り1つを用いて表せます。実際、$n_L$を用いて、
\begin{align*}
n_R &= n_L + X \\
\\
n_D &= \dfrac{N - X - Y}{2} - n_L \\
\\
n_U &= \dfrac{N - X + Y}{2} - n_L
\end{align*}
と表せます。この$n_L$を新たに$n$とおきなおします。この$n$は$$0\le n\le \dfrac{N - X - Y}{2}$$
を満たす整数全体を動きます。よって$P$は、
P = \sum^{\frac{N-X-Y}{2}}_{n = 0}\dfrac{N!}{n!(n+X)!(\frac{N - X - Y}{2} - n)!(\frac{N - X + Y}{2} - n)!}
と表せ、これを計算していきます。右辺の和の中身は
\begin{align*}
(\mathrm{righthand}) =& \sum^{\frac{N-X-Y}{2}}_{n = 0}\dfrac{N!}{n!(n+X)!(\frac{N - X - Y}{2} - n)!(\frac{N - X + Y}{2} - n)!} \\
=& \sum^{\frac{N-X-Y}{2}}_{n = 0}{_{\frac{N-X-Y}{2}}}{\mathrm{C}}_n\dfrac{N!}{(\frac{N-X-Y}{2})!(n+X)!(\frac{N - X + Y}{2} - n)!} \\
=& \left.\sum^{\frac{N-X-Y}{2}}_{n = 0}{_{\frac{N-X-Y}{2}}}{\mathrm{C}}_n\dfrac{N!}{(\frac{N-X-Y}{2})!(n+X)!(\frac{N - X + Y}{2} - n)!}x^{n+X}x^{\frac{N - X + Y}{2} - n}\right|_{x = 1, y = 1} \\
=& \left.\sum^{\frac{N-X-Y}{2}}_{n = 0}{_{\frac{N-X-Y}{2}}}{\mathrm{C}}_n\dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!}\right. \\
& \times\left.\dfrac{d^{\frac{N - X - Y}{2} - n}}{dx^{\frac{N - X - Y}{2} - n}}x^{\frac{N + X - Y}{2}}\dfrac{d^{n}}{dx^{n}}x^{\frac{N - X + Y}{2}}\right|_{x = 1, y = 1} \\
=& \dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!} \\
& \times\left.\sum^{\frac{N-X-Y}{2}}_{n = 0}{_{\frac{N-X-Y}{2}}}{\mathrm{C}}_n\dfrac{d^{\frac{N - X - Y}{2} - n}}{dx^{\frac{N - X - Y}{2} - n}}x^{\frac{N + X - Y}{2}}\dfrac{d^{n}}{dx^{n}}x^{\frac{N - X + Y}{2}}\right|_{x = 1, y = 1} \\
=& \left.\dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!}\dfrac{d^{\frac{N - X - Y}{2}}}{dx^{\frac{N - X - Y}{2}}}\left(x^{\frac{N + X - Y}{2}}x^{\frac{N - X + Y}{2}}\right)\right|_{x = 1, y = 1} \\
=& \left.\dfrac{N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!}\dfrac{d^{\frac{N - X - Y}{2}}}{dx^{\frac{N - X - Y}{2}}}\left(x^N\right)\right|_{x = 1, y = 1} \\
=& \dfrac{N!N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!(\frac{N + X + Y}{2})!}
\end{align*}
となります。
まとめ
問題の解答としては、
\begin{align*}
\begin{cases}
\dfrac{N!N!}{(\frac{N-X-Y}{2})!(\frac{N + X - Y}{2})!(\frac{N - X + Y}{2})!(\frac{N + X + Y}{2})!} &(N\%2==(X+Y)\%2\,\,\mathrm{and}\,\, N < X + Y) \\
\\
0 & (\mathrm{otherwise})
\end{cases}
\end{align*}
となります。到達可能な場合は2つの二項係数の積で表せます。
修正箇所
まとめの部分の条件式を修正しました。(2020/01/21)