바둑판 모양 도로의 최단 경로 개수

가로, 세로를 각각 $a$, $b$ 라고 하면, 세로 길이가 3인 경로는 가로의 길이가 3이상인 경로에 포함된다. 따라서 가로의 길이가 3이상인 경로의 수만 구한다.

(i) 길이가 5인 경로는 $( aaaaa )$, $b$, $b$, $b$ 의 순열에서 $\displaystyle \frac{4 !}{3 !} = 4$가지 (ii) 길이가 4인 경로는 $( aaaa )$, $a$, $b$, $b$, $b$의 순열인데. $( aaaa )$$b$-($a$, $b$, $b$) === $\displaystyle \frac{3 !}{2 !} = 3$ $b ( aaaa ) b$, $a$, $b$ ===== ${3 !} = 6$ ($a$, $b$, $b$)-$b ( aaaa )$ === $\displaystyle \frac{3 !}{2 !} = 3$ (iii) 길이가 3인 경로는 $( aaa )$, $a$, $a$, $b$, $b$, $b$의 순열인데. $( aaa ) b$-($a$, $a$, $b$, $b$) === $\displaystyle \frac{4 !}{2 ! 2 !} = 6$ $b ( aaa ) b$, $a$, $a$, $b$ ==== $\displaystyle \frac{4 !}{2 !} = 12$ ($a$, $a$, $b$, $b$)-$( aaa ) b$ === $\displaystyle \frac{4 !}{2 ! 2 !} = 6$ 그러므로 구하려는 경로의 수는 $4 + ( 3 + 6 + 3 ) + ( 6 + 12 + 6 ) = 40$