>>180
k次元立方体の中の格子上の道のりがmになる格子点の数は
立方体の一辺が十分大きければ(n>=mならば)
二項定理を使って、(k+m)Cm または (k+m)!/(k!m!)と表せる。

n<m≦nk のときは、ちょっと確証がないのだが
(k+m)Cm - k((k+m-n-1)C(m-n-1)) じゃないかと思うんだが…
できるなら検算してみてくれ。