無限にある数直線を考える. 最初は原点にrいるとする. このとき, 数直線の各位置に国を以下のように対応させる.

\[\dots, N-1, N, N, N-1, N-2, \dots, 2, 1, {\color{red} 1}, 2, 3, \dots, N-1, N, N, N-1, N-2, \dots, 2, 1, 1, 2, 3, \dots\]

ただし, 赤文字の \(1\) が数直線の原点にくるようにする. こうすることで \(i\) 日目から \(i+1\) 日目への移動は数直線上では左右のどちらかの移動だけで表せる.

\(M\) 日後に数直線上の \(i\) の位置に来るためには, 右への移動回数を \(x\) とすると \(x - (M-x) = i\) となればいいので, \(x = (i+M)/2\) となればいい. (整数にならない場合は移動できない)

この組み合わせの数は \(\combi{M}{x}\) 通りである.