도로망 최단경로

도로망을 따라 $\mathrm{A}$지점에서 출발하여 $\mathrm{B}$지점까지 최단거리로 갈 때, 그림의 $\mathrm{P} _{1}$, $\mathrm{P} _{2}$, $\mathrm{P} _{3}$ 지점 중 어느 한 지점을 지난다.

ⅰ) $\mathrm{A} \rightarrow P _{1} \rightarrow B$인 경로로 이동하는 경우 $\mathrm{A}$지점에서 $\mathrm{P} _{1}$지점까지 최단거리로 가는 경우의 수는 $1$, $\mathrm{P} _{1}$지점에서 $\mathrm{B}$지점까지 최단거리로 가는 경우의 수는 $1$이므로 이때의 경우의 수는 $1 \times 1 = 1$이다. ⅱ) $\mathrm{A} \rightarrow P _{2} \rightarrow B$인 경로로 이동하는 경우 $\mathrm{A}$지점에서 $\mathrm{P} _{2}$지점까지 최단거리로 가는 경우의 수는 $\displaystyle \frac{5 !}{4 !}$, $\mathrm{P} _{2}$지점에서 $\mathrm{B}$지점까지 최단거리로 가는 경우의 수는 $\displaystyle \frac{5 !}{4 !}$이므로 이때의 경우의 수는 $\displaystyle \frac{5 !}{4 !} \times \frac{5 !}{4 !} = 25$이다. ⅲ) $\mathrm{A} \rightarrow P _{3} \rightarrow B$인 경로로 이동하는 경우

$\mathrm{A}$지점에서 $\mathrm{P} _{3}$지점까지 최단거리로 가는 경우의 수는 $\mathrm{A}$지점에서 $\mathrm{C}$지점까지 최단거리로 가는 경우의 수 $\displaystyle \frac{4 !}{3 !}$이다. $\mathrm{P} _{3}$지점에서 $\mathrm{B}$지점까지 최단거리로 가는 경우의 수는 $\mathrm{D}$지점에서 $\mathrm{B}$지점까지 최단거리로 가는 경우의 수 $\displaystyle \frac{4 !}{3 !}$이다. 따라서 이때의 경우의 수는 $\displaystyle \frac{4 !}{3 !} \times \frac{4 !}{3 !} = 16$이다. ⅰ), ⅱ), ⅲ)의 경우는 동시에 일어나지 않으므로 구하는 경우의 수는 $1 + 25 + 16 = 42$이다.