トップ > 数学A > 同じものを含む順列:道順

 同じものを含む順列:道順


 ここでは同じものを含む順列の中でよく出題される問題を解いて行く。 図1の上図のように、東西に5本、南北に6本の碁盤目状の道があるとする。 この時、PからQまで最短で行く道順は何通りあるだろうか。  

fig2-12-1.png

 

fig2-12-2.png

図2.

最短でPからQに向かうので、進む方向は必ず北方向か東方向である。 図1の下の図のような道順が考えられるのである。 この時、道順である矢印だけを抜き出して考える図3のようになる。  

fig2-12-3.png

図3.

上向きの矢印は北向き、右向きの矢印は東向きに向かうことを表している。 つまり、PからQまで行く最短の方法は上向きの矢印が4つ、右向きの矢印が5つであることがわかる。 このことからPからQまで行く最短の方法これらの矢印を1列に並べる総数に等しいのである。 これは同じものを含む順列であるので、 \begin{eqnarray} \frac{9!}{4!5!} = \frac{9\cdot8\cdot7\cdot6}{4\cdot3\cdot2\cdot1} = 126 \end{eqnarray} となり、126通りあることがわかるのである。

広告