DouKaku?

図.1のような。格子状の経路があるとします。

(1)  このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。

(2)  (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。

P-+-+-+    P-+-+-+
| | | |    | | | |
+-+-+-+    +-+-+-+
| | | |    |   | |
+-+-+-+    +-+-+ +
| | | |    | | | |
+-+-+-+    +-+ +-+
| | | |    | | | |
+-+-+-Q    +-+-+-Q
  図.1       図.2

経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。


※問題は、野﨑昭弘「離散数学『数え上げ理論』」(講談社 ブルーバックス)「第3章 道順を数える」から拝借させて頂きました。