De wegenstructuur in Amerikaanse steden is in het algemeen erg overzichtelijk. In de benaming van de wegen is die overzichtelijkheid terug te vinden: 1^st street, 2^nd street ... en 1^st avenue, 2^nd avenue,... .

Het karakteristieke schaakbordpatroon van veel Amerikaanse steden. Noord-zuid lopen de avenue’s, oost-west de streets.

figuur 1

Randy Walker wandelt van het kruispunt 2^nd street, 1^st avenue naar het kruispunt 3^rd street, 4^th avenue zonder omwegen.

Maak een plattegrond zoals in figuur 1 en teken daarin alle mogelijke wandelingen.

Doe hetzelfde voor een wandeling van 2^nd street, 1^st avenue naar 4^th street, 3^rd avenue.

figuur 2

Bij het stukje plattegrond (figuur 2) zijn $10$ verschillende wandelingen van $A$ naar $B$ mogelijk.

Teken deze wandelingen. Pak het systematisch aan.

figuur 3

Hoeveel wandelingen zijn er in de plattegrond (figuur 3) mogelijk:

van $A$ naar $B$ ?
van $B$ naar $C$ ?

Hoe kun je uit je antwoorden op de vorige vraag het aantal wandelingen van $A$ naar $C$ vinden?

In de plattegrond hiernaast wordt bij elk kruispunt vermeld hoeveel routes er zonder omwegen naar dat kruispunt leiden, gerekend vanaf het stadhuis. Bij drie kruispunten is het aantal routes al ingevuld.

Vul zelf de aantallen in bij de andere twaalf kruispunten.

Bij het tellen van het aantal routes raak je makkelijk in de knoop. Daarom is het handig om bij elk ‘tussenpunt’ het aantal routes naar dat punt te schrijven.

Punt $B$ ligt vier hokjes rechts van $A$ en drie hokjes boven $A$ . Nils heeft geteld dat er $20$ kortste routes zijn van $A$ naar het punt links van $B$ ; hij heeft ook geteld dat er $15$ kortste routes zijn van $A$ naar het punt onder $B$ . Die aantallen staan bij de betreffende kruispunten.

Weet je nu ook hoeveel kortste routes er zijn van $A$ naar $B$ ?

Je hebt nu een principe ontdekt waarmee je aantallen kortste routes in een rooster kunt uitrekenen.

Noteer het getal $1$ bij elk punt in het rooster dat op maar één manier te bereiken is.
Gebruik vervolgens de optelmethode om het aantal routes naar de overige roosterpunten te bepalen.

Bepaal in onderstaande situaties het aantal kortste routes van $S$ naar $F$ door bij elk tussenpunt het aantal routes te schrijven en de optelmethode toe te passen.

In Square City is een fraaie tuin aangelegd die niet door voetgangers mag worden betreden.

Hoeveel kortste routes zijn er van $A$ naar $B$ ?

Veel telproblemen kunnen worden opgelost met behulp van het onderstaande getallenpatroon: de driehoek van Pascal. Elk getal ( $\neq 1$ ) is de som van zijn twee bovenburen.

Blaise Pascal
(1623 - 1662)

Het getallenpatroon is genoemd naar de Franse filosoof en wiskundige Blaise Pascal. Het werd onder zijn naam in 1665 (postuum) gepubliceerd.
Pascal was overigens niet de eerste wiskundige die de tabel ontdekte en gebruikte. In een Chinees wiskundeboek, van de schrijvers Ssu Yuan Yu en Chuh Shih Chieh, uit het jaar 1303, is de tabel al te vinden. En dat de tabel nog veel ouder is, blijkt uit het feit dat hij in het Chinese boek ‘de antieke tabel’ wordt genoemd.

Bekijk de driehoek van Pascal. De driehoek begint met regel 0; de onderste regel is regel 9.

Hoe ziet regel 10 er uit?

Nog een keer de driehoek van Pascal maar nu in de vorm van een plattegrond.

Op regel 0 staat $1$ . De getallen op regel 1 zijn opgeteld $2$ . De getallen op regel 2 zijn opgeteld $4$ .

Vul deze lijst aan tot en met regel 6.

Heb je enig idee welke uitkomst je krijgt als je de getallen op regel 10 optelt? En op regel $x$ ?

Opvallend, toch? Elke som is een macht van $2$ .

Weet je daar een verklaring voor? Welke?

Dwars door Square City loopt een kanaal, zoals je al eerder gezien hebt. Langs het kanaal is een mooie boulevard aangelegd met gezellige restaurants en barretjes.
Een inwoonster van Square city wil vanuit punt $A$ zo snel mogelijk naar de boulevard.

Uit hoeveel routes kan zij kiezen?

In opgave 46 heb je berekend hoeveel kortste routes er zijn in een rooster van $(0,0)$ naar $(4,3)$ . Als het goed is, kwam je aan $35$ . Elke kortste route bestaat uit $7$ stappen (een stap is $1$ naar boven of $1$ naar rechts). Van die $7$ stappen moet je er $3$ naar boven doen (en $4$ naar rechts). Het aantal kortste routes vind je in de driehoek van Pascal in de $7$ ^e rij (zie onderstaande figuur).

In welke rij kun je het aantal kortste routes van $(0,0)$ naar $(5,2)$ vinden? Hoeveel van die routes zijn er?

Hoeveel kortste routes zijn er van $(0,0)$ naar $(6,4)$ ?

Als je met behulp van de driehoek van Pascal het aantal kortste routes van $(0,0)$ naar $(14,6)$ wilt bepalen, moet je de driehoek aanvullen tot en met de $20$ ^e rij. Dat is een heel karwei. Dit getal kun je gelukkig ook eenvoudig op je (grafische) rekenmachine berekenen met de optie $n C r$ .

De rekenmachine geeft $20 nCr 6 = 38.760$ .

De $20$ staat voor het totaal aantal stappen van $(0,0)$ naar $(14,6)$ en de $6$ staat voor het aantal stappen dat je naar boven gaat.

Het aantal kortste routes van $(0,0)$ naar $(14,6)$ noteren we met het combinatiegetal $(\begin{matrix} 20 \\ 6 \end{matrix})$ ; spreek uit: twintig boven zes.

Het aantal kortste routes van $(0,0)$ naar $(14,6)$ bestaat uit $20$ stappen. In plaats van te letten op het aantal stappen dat je naar boven gaat, kun je ook letten op het aantal stappen dat je naar rechts gaat; dat zijn er $14$ .

Bereken $(\begin{matrix} 20 \\ 14 \end{matrix})$ op je rekenmachine. Geldt $(\begin{matrix} 20 \\ 14 \end{matrix}) = (\begin{matrix} 20 \\ 6 \end{matrix})$ ?

$(\begin{matrix} 20 \\ 7 \end{matrix})$ is het aantal kortste routes van het punt $(0,0)$ naar het punt $B$ .

Wat zijn de coördinaten van $B$ ? Er zijn twee mogelijkheden; geef ze beide.

Met welk combinatiegetal kun je het aantal kortste routes van $(0,0)$ naar $(10,8)$ noteren? Er zijn twee mogelijkheden; geef ze beide.

Voor welk getal $n \neq 7$ geldt: $(\begin{matrix} 16 \\ n \end{matrix}) = (\begin{matrix} 16 \\ 7 \end{matrix})$ ?

Welk combinatiegetal hoort bij het aantal kortste routes van $(2,3)$ naar $(8,6)$ ? Bereken dit aantal op je rekenmachine.

Hoeveel kortste routes zijn er van $(0,0)$ naar $(7,3)$ ?

Hoeveel kortste routes zijn er van $(7,3)$ naar $(10,8)$ ?

Hoeveel kortste routes zijn er van $(0,0)$ , via $(7,3)$ , naar $(10,8)$ ?

Hoeveel kortste routes zijn er van $(0,0)$ , via $(7,3)$ naar $(10,8)$ en dan vervolgens via $(5,5)$ terug naar $(0,0)$ ?