321 : 駒の交換

$2n+1$個の正方形からなる水平方向の列に、中央の空白の正方形をへだてて、片側に$n$個の赤の駒があり、もう一方の側に$n$個の青の駒がある。例えば$n=3$では次のとおりである：

p321_swapping_counters_1.gif

駒は、ある正方形から隣に移動させるか、隣の駒のさらにその隣が空いていれば、その駒を飛び越えることができる。

p321_swapping_counters_2.gif

駒の色の位置を完全に逆にするのに必要な操作の最小の回数を$M(n)$で表すとする。つまり、赤の駒を全て右に移し、青のカウンタを全て左に移す。

$M(3)=15$であることが確かめられる。この数は三角数でもある。

$M(n)$が三角数となる$n$で数列を作ると、最初の五つの項は次のとおりになる： 1, 3, 10, 22, 63 これらの和は 99 である。

この数列の最初の 40 個の項の和を求めよ。