Routes in een rooster

q7883img1.gif

Het aantal kortste routes van A naar B in het rooster is gelijk aan:

$
\left( {\begin{array}{*{20}c}
9\\
4\\
\end{array}} \right) = 126
$

Je moet immers 9 keer een keuze maken tussen 'Oost' en 'Noord' en daarbij 4 keer 'Oost' kiezen.

Maar $
\left( {\begin{array}{*{20}c}
9\\
5\\
\end{array}} \right)
$ kan natuurlijk ook.

Het aantal kortste routes van A naar B via P is gelijk aan:

$
\left( {\begin{array}{*{20}c}
3\\
1\\
\end{array}} \right) \times \left( {\begin{array}{*{20}c}
6\\
3\\
\end{array}} \right) = 60
$

Onvolledige roosters

Om in een onvolledig rooster het aantal kortste routes van P naar Q te bepalen zet je bij elk kruispunt het aantal routes om er vanuit P te komen.

q7883img2.gif

q7883img3.gif