難問奇問数学自作問題20-平安京リレーマラソンと組み合わせ問題-

大学入試 自作問題 奇問 場合の数 組み合わせ

「 { \displaystyle n \geq m } を自然数とする。 { \displaystyle {}_{2n} C _n=\sum_{k=0}^{m} \  {}_{m} C _k {}_{2n-m} C _{n-k} } が成り立つことを示せ。」 

 

考え方のポイントは、

碁盤状迷路を用いて示すこと。

  { \displaystyle {}_{m} C _k {}_{2n-m} C _{n-k} } から予想される通り、 { \displaystyle n\times n} の正方形碁盤目経路において、第一走者は { \displaystyle m }ブロック、第二走者は { \displaystyle 2n-m } ブロックだけ進む場合に相当する。

 

このヒントを利用すればすぐに証明できる。