| Routes in een rooster | |
| Tel
het aantal kortste routes in een rooster van punt A naar punt B. Schrijf bij elk knooppunt op hoeveel manieren je er kunt komen. Stel dat je dat voor knooppunt P wilt weten Vraag jezelf dan af vanaf welke knooppunten je in de vorige stap naar P kunt zijn gekomen. |
|
| Als
je bijv. van linksonder naar rechtsboven moet gaan, dan moet elke stap
naar rechts of naar boven zijn. Dus om in P te zijn moet je vanaf Q of vanaf R zijn gekomen (Zie de figuur hiernaast). Het aantal routes van A naar P is daarom gelijk aan het aantal routes van A naar R plus het aantal van A naar Q. Dus tel de getallen die bij R en Q horen bij elkaar op. |
 |
| Consequent toepassen van deze regel levert in onderstaand routes bijvoorbeeld dat er 29 kortste routes van A naar B zijn. | |
|
|
|
| Regelmatig
rooster Bij een volledig regelmatig (vierkanten) rooster komen op deze manier de getallen van de driehoek van Pascal tevoorschijn. Daarin staan de combinaties nCr. Om dan van A(0,0) naar B(x,y) te gaan zijn er ((x + y) nCr x) routes Dus bijv. van (0,0) naar (4,5) kan op 9 nCr 4 manieren. |
|
