最短経路2

PからQまで行く最短経路の総数を求めよ。

図に書き入れたA〜Dの各点は最短経路で行く場合、
必ずどれかを通る。　なおかつ、どの2点も両方通ることはない。
つまりA〜Eの各点を通る経路の数の和が最短経路の総数となる。
[1]Aを通る経路 1通り
[2]Bを通る経路　4!3!×6!5!=24通り
[3]Cを通る経路
　Cのあと縦に進む場合4!3!×4!3!=16通り
Cのあとに横に進む場合4!3!×5!3!2!=40通り
あわせて56通り
[4]Dを通る経路 6!4!2!=15通り
[1]〜[4]を合計すると　1+24+56+15=96通り