Praktische Opdracht
Recursief tellen?

Probleemomschrijving
Op hoeveel manieren kun je drie leerlingen uit een groep van 30 aanwijzen? Op hoeveel manieren kunnen 8 mensen om een ronde tafel gaan zitten?

Deze vragen zijn bekende telproblemen. In klas 4 heb je ze misschien moeten oplossen. De antwoorden zijn 4060 en 5040. Met de theorie over permutaties en combinaties kun je die antwoorden vinden. Maar er zijn ook telproblemen waarbij je anders te werk kunt of moet gaan.

Bekijk alle verschillende rijtjes met lengte 15 die uit enen en nullen In totaal zijn dat er 215 = 32768. Dat is niet moeilijk. Maar hoeveel zijn het er als je als extra voorwaarde stelt dat er geen twee nullen achter elkaar mag staan?

Dit probleem is niet meer zo eenvoudig. Toch is er een methode die hier hulp brengt. Die methode heet recursief. Je telt eerst het aantal rijtjes bij een kortere lengte, bijvoorbeeld rijtjes met lengte 1 en rijtjes met lengte 2. Die kun je "gewoon" tellen"

lengte 1

0

1

 

 

 

aantal(1) = 2

lengte 2

01

10

11

 

 

aantal(2) = 3

lengte 3

010

011

101

110

111

aantal(3) = 5

De vraag is nu: wat is aantal(15)?

Dat antwoord kun je vinden als je een formule kent die aantal(n) uitdrukt in de aantallen van kortere rijtjes, dus in aantal(n-1), aantal(n-2) etc. Je kunt met die formule dan aantal(4) bepalen met behulp van de gevonden aantallen, 2, 3 en 5. En daarna kun je aantal(5) op zijn beurt weer bepalen met aantal(4) en de eerdere resultaten. Etc. Dit telproces heet recursief tellen. Maar de vraag is nu natuurlijk: wat is de recursieve formule? Hoeveel voorgaande termen moet je eigenlijk kennen?

Voor wie
alle profielen

Omvang
8 slu

Beginkennis
Domein Eg;   subdomein combinatoriek en kansrekening: Je moet bij een meetkundige rij de formules voor term en som
                     kunnen gebruiken
ICT:              Je moet rijwaarden kunnen bepalen met een GR of met Excel.

Wat wordt er van je verwacht?
Eerst bestudeer je de verdere oplossing van het "rijtjes"-probleem. Die oplossing kun je vinden in de bijlage: recursief tellen. In die bijlage staat ook nog een ander probleem beschreven dat met recursie opgelost wordt: de torens van Hanoi. Daarna probeer je met behulp van recursief tellen twee van de volgende drie problemen op te lossen. Het gaat daarbij natuurlijk vooral om het vinden van de recursieve formule.

1)
Deze opdracht bestaat uit varianten op het inleidende probleem.

  1. Hoeveel verschillende rijtjes met lengte 20 bestaan er waarin geen drie enen achter elkaar staan?
    'n voorbeeld van zo'n rijtje: 011000001011010110000
  2. Hoeveel verschillende rijtjes met lengte 20 bestaan er die bestaan uit de symbolen 0 , 1 en 2 en waarin bovendien geen twee enen achter elkaar staan?
    'n voorbeeld van zo'n rijtje: 012220001210120101212

2)
Twee snijdende lijnen verdelen het vlak in 4 delen. Drie lijnen die elkaar onderling snijden verdelen het vlak in 7 gebieden. Een van die gebieden is eindig (heeft een eindige oppervlakte), de andere zes niet. Bij vier onderling snijdende lijnen zijn er drie "eindige" gebieden en acht "oneindige" gebieden.

Hoeveel "eindige" gebieden zijn er bij 50 onderling snijdende lijnen?

3)
Als je drie punten op een cirkel tekent en met elkaar verbindt dan ontstaan er vier gebieden. Bij vier punten ontstaan er 8 punten. Bij vijf punten vind je er (maximaal) 16. Maar bij zes punten krijg je er geen 32 maar 31 gebieden. Controleer dat maar. Hoeveel gebieden kun je (maximaal) krijgen bij12 punten op de cirkelrand?

Studiemateriaal
Bijlage: recursief tellen