【数学A】例題1.2.18：最短経路2（One More）★★★

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.18：最短経路2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

右の図のような格子状の道路がある．A地点からB地点まで最短経路で行くとき，次のような道順は何通りあるか．

(1) C地点を通らない道順

(2) C地点またはD地点を通る道順

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.18の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) A地点からB地点へのすべての道順は，$\frac{10!}{6!4!}=210\text{（通り）}$

C地点を通る道順は，$\frac{4!}{2!2!}\times\frac{5!}{3!2!}=60\text{（通り）}$

よって，C地点を通らない道順は，$210-60=150(\text{通り})$

(2) D地点を通る道順は，$\frac{7!}{4!3!}\times\frac{2!}{1!1!}=70(\text{通り})$

C地点かつD地点を通る道順は，

\[
\frac{4!}{2!2!}\times\frac{2!}{1!1!}\times\frac{2!}{1!1!}=24(\text{通り})
\]

よって，(1)より，C地点を通る道順は60通りであるから，求める道順は，

\[
60+70-24=106(\text{通り})
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.18：最短経路2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

右の図のような格子状の道路がある．A地点からB地点まで最短経路で行くとき，次のような道順は何通りあるか．

(1) C地点を通らない道順

(2) C地点またはD地点を通る道順

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.18の解答（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) A地点からB地点へのすべての道順は，$\frac{10!}{5!5!}=252\text{(通り)}$

C地点を通る道順は，$\frac{4!}{2!2!}\times\frac{5!}{2!3!}=60\text{(通り)}$

よって，C地点を通らない道順は，$252-60=192(\text{通り})$

(2) D地点を通る道順は，$\frac{6!}{3!3!}\times\frac{3!}{1!2!}=60(\text{通り})$

C地点かつD地点を通る道順は，

\[
\frac{4!}{2!2!}\times 1\times\frac{3!}{1!2!}=18(\text{通り})
\]

よって，(1)より，C地点を通る道順は60通りであるから，求める道順は，

\[
60+60-18=102(\text{通り})
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.18の側注：最短経路2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
C地点を通る道順は，下の図のように，AからXへの道順$\frac{4!}{2!2!}$通り，XからYへの道順1通り，YからBへの道順$\frac{5!}{3!2!}$通りを掛け合わせたものである．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.18の側注：最短経路2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% 側注1
C地点を通る道順は，下の図のように，AからXへの道順$\frac{4!}{2!2!}$通り，XからYへの道順1通り，YからBへの道順$\frac{5!}{2!3!}$通りを掛け合わせたものである．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.18の考え方・補足など：最短経路2（One More）★★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 考え方
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) A地点からB地点への経路は，C地点を通る場合と通らない場合の2つに分けられるので，「C地点を通らない道順$=\text{A地点からB地点へのすべての道順}-\text{C地点を通る道順}$」，つまり，$n(\overline{C})=n(U)-n(C)$を利用する．

(2) 求める道順は，$n(C\cup D)$であり，「CまたはD地点を通る道順$=\text{C地点を通る道順}+\text{D地点を通る道順}-\text{C地点かつD地点を通る道順}$」，つまり，$n(C\cup D)=n(C)+n(D)-n(C\cap D)$を利用する．

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 余談
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

道順の総数は，具体的に道順の総数を書き込む（数え上げる）ことによっても求めることができる．右の図の(i)において，Pまでの道順が$p$通り，Qまでの道順が$q$通りあるとき，Rまでの道順は$p+q$通りとなる．

(i)

このことから，例えば右の図の(ii)のように，A地点からB地点までの道順を書き込んでいくと，210通りであることがわかる．なお，このように書き込むことによって求める方法は，道路の一部が欠けている場合や3方向に進むことができる道路（例題では東，北の2方向）などの場合に有効であることが多い．

(ii)