Nieuwe pagina 1


OPGAVEN

1.	Hoeveel kortste routes zijn er in het rooster hiernaast van A naar B?

2.	Hoeveel verschillen de kortste routes in een vierkantenrooster zijn er van (3,2) naar (7,5)?

3.	Hoeveel verschillende kortste routes zijn er in het rooster hiernaast van A via B naar C?



OPLOSSING

1.	71 routes.

2.	4 opzij en 3 omhoog kan op 7 nCr 3 = 35 manieren

3.	van A naar B: 5 nCr 2 = 10 routes. van B naar C: 6 nCr 2 = 15 routes. in totaal 10 • 15 = 150 routes.

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.

Tel de kruispunten waar je vandaan kunt komen 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 kan het met combinaties.
Immers dan is een route niets anders dan een rijtje letters.
Moet je bijvoorbeeld van A naar B 4 stappen naar rechts en 3 omhoog, dan is een mogelijkheid RRRRBBB
Er zijn 7 nCr 3 = 35 zulke routes (rijtjes) mogelijk.