鹿島建設プロコン2020-D Binomial Coefficient is Fun

　公式解説とは異なる、経路数を考えることによる導出を紹介する。

考察

　とりあえず、各を固定して考えよう。というのは、縦がマス、横がマスのグリッドにおいて、左下から右上に右移動と上移動だけで向かうときの経路の数に等しい。この値を掛け算するので、なんとなく大きなグリッドを作りたくなる。

これを...

こう！

　上図における橙と緑の長方形を通る経路の積がの値を決めたときの答えへの寄与である。本来はにおけるすべてのについての和を求めよ、という問題だから、縦をマスにして、上に移動することがの値を1大きくすることに対応させれば、縦がマス、横がマスのときの左下から最右列のいずれかの点への経路数が答えだ！と信じたいくなる。ところが、残念ながらサンプル1さえ合わない。縦の長さをに対応させようという作戦だったが、上図の橙と緑の長方形の境界部分の点から上に移動することが、に寄与するのかに寄与するのかの対応が不明瞭になるのである。
　そこで、この間に1列足してみる。

これならどうだ

　この1列を横に移動することが、上に移動することをへの寄与からへの寄与に変えるという役割を果たす。このようにすれば、左下から最右列へのいずれかの点への経路のとったときに、今足した1列をどこで通り過ぎたかを見ることで、との対応をとることができる。
　従って、答えはとして、マス、横がマスのグリッドにおいて、左下から最右列のある点に右移動と上移動だけで向かうときの経路数に等しくなる。ところが、ゴール地点が個あるので、このまま計算しようとしても間に合わない。そこで、さらに右に1列足してみる。

1列追加する前のグリッドの「左下から最右列のある点に行く経路数」が答えだったが、赤い列を横に移動することが、この「ある点」を決めることに対応することがわかる。つまり、答えは「マス、横がマスのグリッドにおいて、左下から右上の点に右移動と上移動だけで向かうときの経路数」となる。これはであり、公式解説の述べる値に一致した。