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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.17：最短経路1（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

(1) A地点からB地点へ行く道順

(2) 途中でC，D地点を通る道順

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

A地点からB地点へは，右へ6区画，上へ5区画進む必要がある．右へ1区画進むことを$\rightarrow$，上へ1区画進むことを$\uparrow$と表すと，A地点からB地点へは6個の$\rightarrow$と5個の$\uparrow$の順列で表される．

(1) A地点からB地点へは，6個の$\rightarrow$と5個の$\uparrow$の順列であるから，

\[
\frac{11!}{6!5!}=462(\text{通り})
\]

(2) A地点からC地点へは，右へ2区画，上へ1区画進めばよい．

つまり，2個の$\rightarrow$と1個の$\uparrow$の順列であるから，$\frac{3!}{2!1!}=3(\text{通り})$

C地点からD地点へは右へ2区画，上へ2区画進めばよい．

つまり，2個の$\rightarrow$と2個の$\uparrow$の順列であるから，$\frac{4!}{2!2!}=6(\text{通り})$

D地点からB地点へは右へ2区画，上へ2区画進めばよい．

つまり，2個の$\rightarrow$と2個の$\uparrow$の順列であるから，$\frac{4!}{2!2!}=6(\text{通り})$

よって，A地点からC，Dを経由してB地点まで行く道順は，

\[
3\times 6\times 6=108\text{（通り）}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 例題A1.2.17の別解
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) ${}_{11}\mathrm{C}_5=462(\text{通り})$

(2) ${}_3\mathrm{C}_1\times{}_4\mathrm{C}_2\times{}_4\mathrm{C}_2=3\times 6\times 6=108(\text{通り})$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.17：最短経路1（One More）★★
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

(1) A地点からB地点へ行く道順

(2) 途中でC，D地点を通る道順

(3) 途中でE地点を通る道順

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

A地点からB地点へは，右へ7区画，上へ6区画進む必要がある．右へ1区画進むことを$\rightarrow$，上へ1区画進むことを$\uparrow$と表すと，A地点からB地点へは7個の$\rightarrow$と6個の$\uparrow$の順列で表される．

(1) A地点からB地点へは，7個の$\rightarrow$と6個の$\uparrow$の順列であるから，

\[
\frac{13!}{7!6!}=1716(\text{通り})
\]

(2) A地点からC地点へは，右へ3区画，上へ2区画進めばよい．

つまり，3個の$\rightarrow$と2個の$\uparrow$の順列であるから，$\frac{5!}{3!2!}=10(\text{通り})$

C地点からD地点へは右へ2区画，上へ2区画進めばよい．

つまり，2個の$\rightarrow$と2個の$\uparrow$の順列であるから，$\frac{4!}{2!2!}=6(\text{通り})$

D地点からB地点へは右へ2区画，上へ2区画進めばよい．

つまり，2個の$\rightarrow$と2個の$\uparrow$の順列であるから，$\frac{4!}{2!2!}=6(\text{通り})$

よって，A地点からC，Dを経由してB地点まで行く道順は，

\[
10\times 6\times 6=360\text{(通り)}
\]

(3) 右の図のように，E地点の左隣りの地点をX地点，右隣りの地点をY地点とする．

A地点からX地点へは，右へ3区画，上へ3区画進めばよい．

つまり，3個の$\rightarrow$と3個の$\uparrow$の順列であるから，$\frac{6!}{3!3!}=20(\text{通り})$

X地点からY地点まで行く道順は，1通り

Y地点からB地点へは，右へ3区画，上へ3区画進めばよい．

つまり，3個の$\rightarrow$と3個の$\uparrow$の順列であるから，$\frac{6!}{3!3!}=20(\text{通り})$

よって，A地点からE地点を経由してB地点まで行く道順は，

\[
20\times 1\times 20=400\text{(通り)}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 問題A1.2.17の別解
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

(1) ${}_{13}\mathrm{C}_6=1716(\text{通り})$

(2) ${}_5\mathrm{C}_2\times{}_4\mathrm{C}_2\times{}_4\mathrm{C}_2=10\times 6\times 6=360(\text{通り})$

(3) ${}_6\mathrm{C}_3\times 1\times{}_6\mathrm{C}_3=20\times 1\times 20=400(\text{通り})$

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

% 側注1
同じものを含む順列を考える．

% 側注2
下の図のように，AからCまで，CからDまで，DからBまでの道順を考える．

% 側注3
積の法則を用いる．

% 側注4
11個の場所から，$\uparrow$が入る5個の場所を選ぶ．

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

% 側注1
下の図のように，AからXまで，YからBまでの道順を考える．

% 側注2
同じものを含む順列を考える．

% 側注3
下の図のように，AからCまで，CからDまで，DからBまでの道順を考える．

% 側注4
積の法則を用いる．

% 側注5
13個の場所から，$\uparrow$が入る6個の場所を選ぶ．

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

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

A地点からB地点への最短経路は，右の図の(i)のように，右または上へ進むことによって得られる（左や下へ進まない）．右へ1区画進むことを$\rightarrow$，上へ1区画進むことを$\uparrow$と表すと，例えば右の図のような道順は，

\[
\rightarrow\uparrow\uparrow\rightarrow\uparrow\uparrow\rightarrow\rightarrow\rightarrow\uparrow\rightarrow
\]

と表される．他の道順も同様に，6個の$\rightarrow$と5個の$\uparrow$で表されるので，6個の$\rightarrow$と5個の$\uparrow$を1列に並べる順列と考える（同じものを含む順列）．

なお，別解のように組合せを用いた考え方で求めてもよい．右の図の(ii)のような11個の場所に，$\uparrow$が入る5個の場所を選ぶと，残りの場所には$\rightarrow$が入るので，組合せを用いた考え方でも求めることができる．

(i)

(ii)