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

Een veelhoek in driehoeken verdelen.
       
In een willekeurige veelhoek gaan we een aantal niet-snijdende diagonalen tekenen zodat die veelhoek wordt verdeeld in alleen nog maar driehoeken.
De vraag gaat worden: 
       

Op hoeveel manieren kun  je dat bij een n-hoek doen?
       
een verkenning...
       
Om een beetje een "gevoel" voor een probleem te krijgen is het vaak handig eerst zomaar eens wat gevallen te bekijken. Wie weet zie je een regelmaat of zo. Laten we daarom een aantal veelhoeken op zoveel mogelijk manieren in driehoeken gaan verdelen.
       

       
(de eerste driehoek daar valt over te twisten of je dat nou 1 of 0 manieren moet noemen) Je ziet dat dit al snel aardig uit de hand loopt. Ik kan je vast verraden dat een zevenhoek op 42 manieren in driehoeken verdeeld kan worden.
De vraag is dus:  welke regelmaat zit er in de serie  1 - 2 - 5 - 14 - 42 - .....

Een recursieformule.

Laten we het aantal manieren om een n-hoek met diagonalen in driehoeken te verdelen  vanaf nu  dn noemen.
We gaan proberen een recursierelatie voor dn op te stellen.  Ofwel; de vraag is:  hoe kun je als je d1, d2, d3, ...dn-1 weet, de volgende dn uit de rij berekenen?
Neem een veelhoek met n zijden en kies ιιn daarvan als basiszijde. Dan is er bij elke verdeling van de veelhoek altijd een driehoek te vinden waarvan die basiszijde een zijde is.
       

In de veelhoek hiernaast  (een 9-hoek, maar dat doet er niet toe) is de blauwe zijde als basis gekozen, en die is zijde van de blauwe driehoek.

Dan verdeelt die driehoek de veelhoek in twee nieuwe veelhoeken., in de figuur de rode en de groene veelhoek. En als de ene veelhoek daarvan k zijden heeft, dan heeft de andere er  n + 1 - k , immers in toptaal zijn er n - 1 zijden van de oorspronkelijke veelhoek (de basis niet meer) plus de twee gestippelde nieuwe zijden, dus dat zijn n + 1 zijden.
       
De veelhoek met k zijden kan op  dk manieren verdeeld worden, en de veelhoek met  n + 1 - k zijden op  dn + 1 - k manieren. In totaal kan deze figuur dus op  dk • dn + 1 - k  manieren in driehoeken verdeeld worden.

Maar dit verhaal geldt voor elk aantal k bij de gekozen basiszijde. We moeten alleen uitkijken bij de twee randgevallen die je hieronder ziet.
 

       
Bij deze twee gevallen blijven er na weglaten van de driehoek niet twee veelhoeken over, maar eentje met n - 1 zijden. Dat betekent dat k dus moet lopen van 3 tot en met n - 2.

Voor het totaal aantal manieren om de negenhoek hierboven onder te verdelen geldt dan:

d9 = d8 + d3 • d7 + d4 • d6 + d5 • d5 + d6 • d4 + d7 • d3 + d8

Daarbij stelt elke term uit deze rij een manier voor waarop de blauwe driehoek gekozen kan worden. De eerste en laatste term zijn van die twee randgevallen hierboven. Je ziet ook dat het handig is dat we d3 = 1 hebben gekozen.
't Is trouwens wiskundig nog mooier als we kiezen d2 = 1  en die eerste en laatste term vervangen door d2 • d8  en  d8 • d2

Dan ziet onze recursieformule voor een willekeurige n (in plaats van n = 9) er zo uit:
       

dn = d2dn - 1 + d3dn - 2 + d4dn - 3 + ... + dkdn +1- k + .... + dn - 3d4 +  dn - 2d3 + dn - 1d2
       
de formule in werking:
d3 = 1
d4 = 1 • 1 + 1 • 1 = 2
d5 = 1 • 2 + 1 • 1 + 2 • 1 = 5
d6 = 1 • 5 +  1 • 2 + 2 • 1 + 5 • 1 = 14
d7 = 1 • 14 + 1 • 5 + 2 • 2 + 5 • 1 + 14 • 1 = 42
d8 = 1 • 42 + 1 • 14 + 2 • 5 + 5 • 2 + 14 • 1 + 42 • 1 = 132
enz.
       
Een snellere recursieformule.
       
Het is nog wel een nadeel dat je om een dn te berekenen steeds alle voorgaanden nodig hebt. Het zou natuurlijk mooier zijn als je dn alleen uit dn - 1 zou kunnen berekenen.

En dat kan!

Beschouw de formule  f(x) = d2x2 + d3x3 + d4x4 + ...
Neem, nu deze functie in het kwadraat:

f 2 = (d2x2 + d3x3 + d4x4 + ...) • ( d2x2 + d3x3 + d4x4 + ...)

Stel dat je de haakje wegwerkt en alle zelfde machten van x bij elkaar neemt. Dan krijg je dit:

f 2 = x4 • (d2d2)  + x5 • (d2d3 + d3d2) + x6 • (d2d4 + d3d3 + d4d4) + x7 • (d2d5 + d3d4 + d4d3 + d5d2) + ....

Maar daar tussen haakjes staan precies de termen uit onze gevonden recursierelatie!!!!!
d3 = d2d2
d4 = d2d3 + d3d2
d5 = d2d4 + d3d3 + d4d2
enz.

Dat betekent dus   f 2 = d3x4 + d4x5 + d5x6 + d6x7 + ....
Voeg daar de termen  d2x3  en  -d2x3  aan toe, en je hebt:    f 2 = -d2x3 + d2x3 +  d3x4 + d4x5 + d5x6 + d6x7 + ....
Maar  f  zelf was gelijk aan:   f  =  d2x2 + d3x3 + d4x4 + ...
Dus als je berekent  f 2 - x • f  dan vallen bijna alle termen tegen elkaar weg, en dan krijg je:
f 2 - x • f  =  -x3    (immers d2 was gelijk aan 1)

We gaan proberen daar een gewone vergelijking voor f(x) van te maken.

4f 2 - 4xf = -4x3
4f 2 - 4xf + x2 = x2 - 4x3
(2f - x)2  = x2 (1 - 4x)
2f - x = ± x√(1 - 4x)
2f  =  x ± x√(1 - 4x)
f  = 1/2x • (1 ± √(1 - 4x))

Die laatste wortel gaan we uitwerken met een Taylorreeks rondom x = 0.
f (x) = (1 - 4x)0,5
f '(x) = 0,5 • -4 • (1 - 4x)-0,5
f ''(x) = 0,5 • -0,5 • (-4)2 • (1 - 4x)-1,5
f '''(x) = 0,5 • -0,5 • -1,5 • (-4)3 • (1 - 4x)-2,5
enz.

x = 0 invullen betekent dat dat stuk met x steeds gelijk wordt aan 1.
Met de faculteiten erbij wordt de Taylorreeks dan:

De functie g wordt dan   1/2x ± 1/2x • (1 - 4x)1/2 
Omdat we al weten dat g(x) als laagste macht x2  heeft, moeten we wel kiezen voor het minteken (zodat die 1/2x tegen -1/2x wegvalt).
Kijk naar de coλfficiλnten van de verschillende machten van x en kijk vooral wat er bij elke volgend coλfficiλnt bijkomt vergeleken met de vorige.

• er komt elke keer een factor -4 bij van de kettingregel.
• er komt een factor  -(2n - 3)/2 bij van de macht die er bij het differentiλren vσσr komt te staan  (1/2, -1/2, -3/2, -5/2 enz).
• er komt een 1/n bij van de  1/n! uit de Taylorreeks.
Samen betekent dat, dat er steeds een factor  -4 • -(2n - 3)/2n = (4n - 6)/n  bijkomt als je van dn naar  dn + 1  gaat  
Conclusie:

       
Kijk; dαt is tenminste een eenvoudige recursierelatie waar je mee thuis kunt komen.
Ik heb een ongebreideld vertrouwen in de wiskunde dus ik ga hem niet eens controleren!!!!
       

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