ontmoetingen


Ontmoetingen	© h.hofstede (h.hofstede@hogeland.nl)

Stel dat 5 studenten van plan zijn op een dag een bepaalde tijd in de studiezaal door te brengen. Dan kan het zijn dat sommigen toevallig tegelijk in de studiezaal zijn. We noemen een groep van 2 of meer studenten die tegelijk aanwezig zijn een "ontmoeting".

Als we een tijdlijn tekenen, dan komt het erop neer dat we langs deze lijn willekeurig vijf lijnstukken van willekeurige lengte moeten plaatsen, en kijken welke lijnstukken "overlappen".

Achtereenvolgens zie je hier de ontmoetingen: ab, abc, bc, de, zoals hieronder aangegeven.

Als dezelfde ontmoetingen in andere volgorde plaatsvinden, dan telt dat als verschillend.
De tijdsbalk linksonder is daarom verschillend van die hierboven, maar die rechtsonder is hetzelfde.

De vraag is: Op hoeveel manieren kunnen die ontmoetingen plaatsvinden? Het gaat daarbij alleen om wélke studenten tegelijk aanwezig zijn, niet hoe lang dat duurt. We nemen verder aan dat de begin- en eindpunten van de verschillende lijnstukken nooit exact op dezelfde plaats liggen.

Laten we het aantal manieren tellen door gewoon één voor één die lijnstukken neer te gaan leggen......
Om het eerste lijnstuk neer te leggen is er maar één mogelijkheid, immers de precieze plaats op de lijn doet er niet toe; het gaat alleen om de plaats relatief ten opzichte van de andere lijnstukken.
Als dat eerste lijnstuk eenmaal ligt, dan is de lijn daarmee in drie gebieden verdeeld: links van het beginpunt, samen met het lijnstuk en rechts van het eindpunt:

Als je het beginpunt van lijnstuk b hebt gekozen in gebied I, dan zijn er voor het eindpunt 3 mogelijkheden (I, II en III). Als het beginpunt in gebied II ligt zijn er twee mogelijkheden voor het eindpunt (II en III) en met het beginpunt in II is er voor het eindpunt maar één mogelijkheid (ook in III) In totaal geeft dat 3 + 2 + 1 = 6 mogelijkheden voor lijnstuk 2.

Als lijnstuk 1 en 2 liggen, zijn er 4 begin- of eindpunten die de lijn nu in 5 gebieden verdelen.
Voor het beginpunt van lijnstuk 3 zijn er dus 5 mogelijkheden, en voor het eindpunt daarvan zijn er 5 + 4 + 3 + 2 + 1 = 15 mogelijkheden.
In totaal zijn er voor drie lijnstukken dus 1 • 6 • 15 = 90 mogelijkheden.

Als er n - 1 lijnstukken al liggen, dan zijn er 2(n - 1) = 2n - 2 begin- en eindpunten dus 2n - 1 gebieden. Dus 2n - 1 mogelijke beginplaatsen voor lijnstuk n
Voor het eindpunt zijn er dan (2n - 1) + (2n - 2) + (2n - 3) + ... + 2 + 1 mogelijkheden.
Dat is gelijk aan ¹/₂•(2n - 1) •(2n) = n • (2n - 1) (de som van een meetkundige rij).

Voor het totaal aantal manieren om N lijnstukken te plaatsen moet je al die aantallen met elkaar vermenigvuldigen.

Maar ja, dat staat dan wel heel geleerd, maar verder heb je daar eigenlijk niet zoveel aan. Laten we dit product voorlopig P noemen. Het is misschien handiger de getallen n • (2n -1) gewoon op te schrijven.
Dat geeft: P = (1 • 1) • (2 • 3) • (3 • 5) • (4 • 7) • (5 • 9) • .......• (n • (2n - 1))
Daar staan eigenlijk twee series getallen: de eersten tussen haakjes en de tweeden
Als je die bij elkaar zet staat er: P = (1 • 2 • 3 • 4 • 5 • ... • n) • (1 • 3 • 5 • 7 • 9 • (2n -1))
En het grappige komt pas als je in die eerste serie elk getal met 2 vermenigvuldigt.
Dan staat er: 2ⁿ • P = (2 • 4 • 6 • 8 • 10 • ... • 2n) • (1 • 3 • 5 • 7 • 9 • (2n -1))
Daar aan de rechterkant staan nu precies alle getallen van 1 tot en met 2n, dus dat is gelijk aan (2n)!

Kijk! Dat is tenminste een formule waar je wat mee kunt.
Invoeren in je GR bijvoorbeeld.
Dat geeft de tabel hiernaast.
Daarin zie je bijvoorbeeld dat er voor onze vijf studenten maar liefst 113400 ontmoetingsmogelijkheden zijn.