1愛媛大学 2002年 数学 第1問解答・解説

東へ進む回数を$e$、西を$w$、南を$s$、北を$n$とする。点$A(1,2)$に着くことと道のりが$7$であることから、 $$e-w=1,\qquad n-s=2,\qquad e+w+s+n=7.$$ よって$w=e-1,\ s=n-2$であり、$e\ge1,\ n\ge2$である。これらを道のりの式に代入すると $$e+(e-1)+(n-2)+n=7,$$ したがって$e+n=5$。ゆえに$(e,n)=(1,4),(2,3),(3,2)$である。

各場合の$(e,w,s,n)$は、それぞれ$(1,0,2,4),(2,1,1,3),(3,2,0,2)$となる。同じ移動の並び替えは同一の経路なので、各場合の経路数は $$\displaystyle \frac{7!}{e!w!s!n!}$$ である。したがって総数は $$\displaystyle \frac{7!}{1!0!2!4!}+\frac{7!}{2!1!1!3!}+\frac{7!}{3!2!0!2!}=105+420+210=735.$$ 以上より、（1）の条件は$e+n=5,\ e\ge1,\ n\ge2$であり、（2）の総数は$735$通りである。

終点への水平・垂直変位と総歩数を連立し、非負整数制約から移動回数の組を列挙する。各組ごとに同じ向きの移動を区別しない順列数を多項係数で求めて合算する。