「山びこ通信」2017年度春学期号より下記の記事を転載致します。
『かず』１〜２年 『中学・高校数学』 A・B 『高校数学』
担当 浅野 直樹
これらすべてのクラスでの取り組みに共通するような問題を見つけました。
図1 と図2 は碁盤の目状の道路とし，すべて等間隔であるとする．以下の問いに答えよ．
(1) 略
(2) 略
(3) 図2 において，点A から点B に行く最短経路は全部で何通りあるか求めよ．ただし斜線の部分は通れないものとする．
（九州大）
小学１年生でも問われていることの意味はわかるでしょう。何日かかけて地道に数えれば正しい答えにたどり着けるとも想像できます。少し工夫をするとしたら、下図のように各点まで進む最短経路の総数を書き込むことによって比較的簡単に数え上げることができます。
ある点まで進む最短経路の総数は、その点の１つ左の点まで進む最短経路の総数と１つ下の点まで進む最短経路の総数を足せば求めることができるというのがポイントです。最短経路なので左から右に進むか下から上に進むかのどちらかしかあり得ないからです。こうした考え方は、かず１～２年クラスで取り組んでいる迷路やパズルでしばしば現れます。
高校生（あるいは進度の早い中学生）なら計算で求めたくなることでしょう。点A から点B に行く最短経路は12C6 = 924 通りと求められるということは定番です。そして斜線の部分を通る最短経路は下図のX1～X6 のうち少なくとも1 点を通ります。
点A からX1～X6のうち少なくとも1 点を通る総数は、P からX1～X6 のうち少なくとも1 点を通る総数に等しいので、その総数はP からB への最短経路の総数であり、12C5 = 792 通りです。以上より、求める総数は924 − 792 = 132 通りとなります。
実はここで求めたのはカタラン数と呼ばれるものです。参加人数が決まっている場合にトーナメント表の作り方が何通りあるかもカタラン数になります。例えば４人で考えてみましょう。平等な形のトーナメントを((ab)(cd))、a さんとb さんが最も不利でd さんが最も有利な形を(((ab)c)d) のように表すことができます。右カッコの場所さえ決めれば左カッコは自動的に決まるのでそれを無視するとab)cd))、ab)c)d) のようになります。求めたい総数は、まずa を左端に配置し、残りのbcd の文字と３つの右カッコをすでに並べた右カッコの個数が文字の個数を超えないように並べる総数なので、３×３マスの最短経路で対角線より上の部分を通らない総数と等しくなります。
このような問題を各学年の生徒と共に考えるのは楽しいです。
（問題文と図はhttp://kumamoto.s12.xrea.com/nyusi/Qdai_tech_2008_kouki.pdf から引用させていただきました）