linker hoekje rechter hoekje

Driehoek van Pascal


Inleiding
Blaise Pascal (1623-1662) heeft de driehoek die zijn naam draagt niet zelf uitgevonden. Eigenlijk komt de eer toe aan Chinese wiskundigen. De oudste ons overgeleverde afbeelding van de driehoek van Pascal vinden we terug in een boek van de vooraanstaande Chinese wiskundige Choe Chioe-Shao uit 1303. Ook publiceerde de bekende Italiaanse wiskundige Niccolo Fontana (1499-59), beter bekend als Tartaglia, in zijn boek getiteld  ďAlgemene Verhandeling  over Rekenen en MetenĒ al een rechthoekige versie van de driehoek die bekend is geworden onder de naam 'Rechthoek van Tartaglia'. Deze publicatie verscheen echter pas na zijn dood. Meer dan een eeuw later was het echter Pascal die als eerste de eigenschappen van de driehoek en hun verband met andere wiskundige theorieŽn onderzocht en op papier gezet heeft. Hij legde o.a. het verband tussen de driehoek en de oplossing van belangrijke problemen uit de waarschijnlijkheidsleer.

Bij het bewijzen van allerlei eigenschappen van de driehoek van Pascal speelt het " Principe der Volledige Inductie" een belangrijke rol. Het "Principe der Volledige Inductie" is een hoeksteen voor het het gehele bouwwerk van de moderne wiskunde. Met dit principe kunnen verschillende eigenschappen, zoals het hockeystickpatroon, erg gemakkelijk bewezen worden. Pascal is ook de eerste geweest die het beginsel der volledige inductie helder geformuleerd heeft.

Hoewel inductief redeneren in het dagelijks leven niet erg gebruikelijk is, vormt het toch de basis voor zeer belangrijk en fundamenteel onderzoek op tal van gebieden, met name in de waarschijnlijkheidsrekening en de statistiek.

De bedoeling van deze les  is een aantal van de belangrijkste eigenschappen van de driehoek van Pascal te behandelen en te bewijzen. Het verband met binomiaalcoŽfficiŽnten en combinatoriek zal hierbij ook aan de orde komen. Ook zal aandacht geschonken worden aan het "Principe van de Volledige Inductie".

 De regel volgens welke de driehoek van Pascal wordt gevormd staat bekend als de "Formule van Pascal". Bij de driehoek van Pascal spelen binomiaalcoŽfficiŽnten en de eigenschappen daarvan een belangrijke rol. Daarom eerst een korte samenvatting van de noodzakelijke kennis over binomiaalcoŽfficiŽnten om de driehoek van Pascal te kunnen begrijpen.

Omhoog


BinomiaalcoŽfficiŽnten


Definitie 1
Stel n is een natuurlijk getal, dus n { 0, 1, 2, ∑ ∑ ∑ }.
Voor een natuurlijk getal n 1 is n faculteit, genoteerd n!, gedefinieerd als het product van de getallen van 1 tot en met n:

n! = 1 2 ∑ ∑ ∑ (n - 1) n

Verder spreken we af dat 0! = 1.

Voorbeeld: 5! = 1 2 3 4 5 = 120


Definitie 2

De grootheid 

 gedefinieerd door   = 
n!
 p!(n - p)!
 noemt men binomiaalcoŽfficiŽnt.

Hierbij is p = { 0, 1, 2, ∑ ∑ ∑ , n - 1, n}.

De notatie wordt uitgesproken als n boven p.

Voorbeeld 1: 

 = 
7!
 2!(7 - 2)!
 = 
7!
 2! 5!
 = 
7 6 5!
 2! 5!
 = 
7 6
 2 1
 = 21

Voorbeeld 2: 

 = 
0!
 0!(0 - 0)!
 = 
0!
 0! 0!
 = 
1
 1 1
 =  1

Voorbeeld 3: 

 = 
 n!
 0!(n - 0)!
 = 
n!
 1 n!
 = 
n!
n!
 =  1

Voorbeeld 4: 

 = 
n!
 n!(n - n)!
 = 
n!
 n! 0!
 = 
n!
 n! 1
 = 
n!
n!
 = 1

We vermelden hier enkele belangrijke eigenschappen van de binomiaalcoŽfficiŽnten:

1.

   =   (symmetrie eigenschap)   Zie bewijs
 

2.

+ =   (optelregel of de "Formule van Pascal")          Zie bewijs
 

3.

 n - p + 1 
 p
 
Zie bewijs

Voor het bewijs van deze eigenschappen wordt verwezen naar de Appendix.
De optelregel of de formule van Pascal (Eigenschap 2) gebruiken we bij het opbouwen van de driehoek van Pascal.

Omhoog


Bewijzen m.b.v. volledige inductie
Stel we moeten een formule bewijzen (zoals het Binomium van Newton) waarin het natuurlijk getal n voorkomt, waarbij  n = 1, 2, 3, ∑ ∑ ∑.  We willen aantonen dat de formule geldig is voor alle waarden van n. Je zou de formule kunnen verifiŽren voor n = 1, n = 2 tot en met n = 10.000. Zou de formule dan telkens kloppen dan zou je geneigd zijn aan te nemen dat de formule juist is voor alle waarden van n. Je weet dit echter niet zeker! Met het principe van de volledige inductie kunnen we de formule bewijzen voor alle n.

Het bewijs bestaat uit twee stappen die we aanduiden met I en II.

  1. Bewijs dat de formule juist is voor n = 1.

  2. Neem aan dat de formule juist is voor n = m. Als daaruit volgt dat de formule ook juist is voor n = m + 1, dan is de formule juist voor alle waarden van n.

Immers als de formule juist is voor n = 1, dan is hij volgens stap II ook juist voor n = 2. Maar dan ook voor n = 3 enzovoort. Dit noemen we inductie.

In de wiskunde wordt veel gebruik gemaakt van het principe van de volledige inductie om stellingen te bewijzen waarin het natuurlijk getal n voorkomt.

Omhoog


Driehoek van Pascal
De driehoek van Pascal is meer dan alleen een driehoekig schema van rijtjes van getallen. In de driehoek liggen een groot aantal patronen en eigenschappen verborgen. Sommige zijn voordehandliggend, andere weer niet, Toch zijn ze allemaal interessant genoeg om te onderzoeken. De bedoeling van deze les  is een aantal van de belangrijkste eigenschappen te behandelen en te bewijzen. Het verband met binomiaalcoŽfficiŽnten en combinatoriek zal hierbij ook naar voren komen

De driehoek van Pascal is een driehoekig schema van getallen waarbij de volgende rij getallen verkregen word door optelling van de twee getallen in de vorige rij die er net boven staan. Op de zijden van de driehoek worden daarbij eerst 1-en geplaatst. (Let op het verband met Definitie 2 voorbeeld 2, 3 en 4)

rij 0 1
rij 1 1 1
rij 2 1 2 1
rij 3 1 3 3 1
rij 4 1 4 6 4 1
rij 5 1 5 10 10 5 1
rij 6 1 6 15 20 15 6 1
enzovoort

Bij nader onderzoek blijkt de Driehoek van Pascal een rangschikking van de waarden van de binomiaalcoŽfficiŽnten volgens onderstaand schema te zijn

 
rij 0                  
0
0
                 
rij 1
1
0
1
1
rij 2
2
0
2
1
2
2
rij 3
3
0
3
1
3
2
3
3
  ∑
rij n
n
0
n
 p-1
n
 p
n
n-1
n
n
rij n+1  
n+1
0
n+1
p
n+1
n
n+1
n+1
                                 
             Optelregel                     Optelregel   

In de ne rij ( n 0), staan de binomiaalcoŽfficiŽnten  voor p = 0, 1, ..., n. Met de formule van Pascal kun je deze driehoek gemakkelijk naar onderen voortzetten. In de driehoek van Pascal zitten dus binomiaalcoŽfficiŽnten verborgen. BinomiaalcoŽfficiŽnten spelen ook een belangrijke rol in het Binomium van Newton. Je kunt met de Driehoek van Pascal dus vrij eenvoudig binomiaalcoŽfficiŽnten bepalen.

Omhoog


De som van een rij
De som van de getallen in een willekeurige rij is gelijk aan 2n, waarbij n het rijnummer voorstelt. Enkele voorbeelden:

rij 0      1 = 20
rij 1 1 + 1 = 2 = 21
rij 2 1 + 2 + 1 =  4 = 22
rij 3 1 + 3 + 3 + 1 = 8 = 23
rij 4 1 + 4 + 6 + 4 + 1 = 16 = 24

We kunnen bewijzen dat de som van de getallen in de n-de rij gelijk is aan 2n. Daarvoor bekijken we nogmaals de driehoek van Pascal, maar dan genoteerd m.b.v. binomiaalcoŽfficiŽnten.

rij - 0                  
0
0
                 
rij - 1
1
0
1
1
rij - 2
2
0
2
1
2
2
rij - 3
3
0
3
1
3
2
3
3
rij - n
 n
0
 n
 p -1
 n
 p
 n
n -1
 n
 n

De som S van de getallen in de n-de rij is:

S
 n
0
 +
 n
1
 +   + 
 n
 p
 +   + 
 n
 n

In verkorte vorm, gebruikmakende van het somteken

S =

Volgens het Binomium van Newton geldt:

2n  = (1 + 1)n = 1n- p 1 p =  = S

Hiermee is bewezen dat S = 2n.

Omhoog


Priemgetallen
Als in de driehoek van Pascal het 1-ste element van een rij een priemgetal is (Let op! Het 0-de element van elke rij is 1.), dan zijn alle elementen van die rij (behalve de 1-en) deelbaar door dat priemgetal. Om deze eigenschap nader te onderzoeken en te bewijzen beschouwen we nogmaals de driehoek van Pascal:

rij 0
1
rij 1 1 1
rij 2 1 2 1
rij 3 1 3 3 1
rij 4 1 4 6 4 1
rij 5 1 5 10 10 5 1
rij 6 1 6 15 20 15 6 1
rij 7 1 7 21 35 35 21 7 1
enzovoort

We zien dat deze eigenschap klopt voor rij 2, 3, 5 en 7. Bijvoorbeeld in rij 7  zijn 7, 21, en 35 allen deelbaar door 7. Het vermoeden rijst dus dat deze eigenschap misschien wel altijd geldt. Om dit aan te tonen bekijken we de n-e rij waarbij we aannemen dat n een priemgetal is

rij n :   
 n
0
 n
1
∑ ∑ ∑
 n
 p
∑ ∑ ∑
 n
n -1
 n
 n
 

We gaan nu bewijzen dat de binomiaalcoŽfficiŽnt

 
 n
 p
 een veelvoud is van  n.

Bij het bewijs roepen we de  "Hoofdstelling der Rekenkunde" te hulp.
 

   
Hoofdstelling der Rekenkunde

Ieder geheel getal 1 kan op slechts ťťn manier (afgezien van de volgorde der factoren) geschreven worden als het product van priemfactoren.

We kunnen daarom spreken van de priemfactorontbinding van dat getal. Schrijf je bijvoorbeeld het getal 2750 als een product van priemgetallen:

2750 = 2 5 5 5 11 = 2 53 11;

dan heb je ťťn factor 2, drie factoren 5 en ťťn factor 11 en het is nooit anders, hoe je het ook doet.
     

 

Nu is

 
 n
 p
 voor p = 1, 2,∑ ∑ ∑n -1 een geheel getal en kan dus volgens de 

Hoofdstelling der Rekenkunde geschreven worden als het product van priemfactoren. Het enige dat we nu nog hoeven te bewijzen is dat n ťťn van deze priemfactoren is.

Nu is

 
 n
 p
 = 
n!
 p!(n - p)!
 = 
 n (n -1)! 
 p!(n - p)!
 =  n  
 (n -1)! 
 p!(n - p)!
 voor p = 1, 2,∑ ∑ ∑n-1

Teller en noemer van het quotiŽnt 

 (n -1)! 
 p!(n - p)!
 bevatten verder uitsluitend factoren n.

We weten dus zeker dat n een priemfactor is van

 
 n
 p
 is.

Bovendien weten we nu ook dat 

 (n -1)! 
 p!(n - p)!
 =  m een geheel getal moet zijn.

Dus is

 
 n
 p
 =  n  m een veelvoud van n.

Hiermee is het bewijs geleverd.

Omhoog


Het magische getal 11
We beschouwen nogmaals de driehoek van Pascal.

rij 0 1
rij 1 1 1
rij 2 1 2 1
rij 3 1 3 3 1
rij 4 1 4 6 4 1
rij 5 1 5 10 10 5 1
rij 6 1 6 15 20 15 6 1
enzovoort

Als we een rij omzetten in een geheel getal door elk element van de rij te beschouwen als een cijfer van dat getal, dan krijgen we machten van 11. Tot en met rij 4 is dit direct na te gaan.
  

     

0.

Rij 0 komt overeen met het getal 1 = 110.

1.

Rij 1 komt overeen met het getal 11 = 111.

2.

Rij 2 komt overeen met het getal 121 = 112.

3.

Rij 3 komt overeen met het getal 1331 = 113.

4.

Rij 4 komt overeen met het getal 14641 = 114.

Daarna komen er in de rijen elementen voor die uit meer dan ťťn cijfer bestaan. In rij 5 komt bijvoorbeeld het element 10 voor en in rij 6 de elementen 15 en 20. Om deze rijen in een geheel getal om te zetten moeten we even stilstaan bij de manier waarop een getal in ons tientallig stelsel weergegeven wordt.

In het tientallig stelsel worden getallen genoteerd met behulp van een buitengewoon ingenieus hulpmiddel, het zogenaamde positiestelsel, waarbij de waarde van een cijfer afhangt van de plaats of positie, die het in het getal inneemt. Om een getal in het tientallig stelsel weer te geven hebben we tien symbolen nodig: 0, 1, 2, 3, 4, 5, 6, 7, 8 en 9.

Voorbeeld: 4157  =   4000 + 100 + 50 + 7 = 4 103 + 1 102 + 5 101 + 7 100

Met deze wetenschap gaan wij de elementen van rij 5 van de Driehoek van Pascal omzetten in een geheel getal. Rij 5 bestaat uit de elementen 1, 5, 10, 10, 5, 1. Het getal dat met rij 5 overeenkomt is 161051 want:

1 105 + 5 104 + 10 103 + 10 102 + 5 101 + 1 100 = 161051

Er blijkt 161051 = 115.

Het getal dat met rij 6  (1, 6, 15, 20, 15, 6, 1)  overeenkomt is 1771561 want:

1 106 + 6 105 + 15 104 + 20 103 + 15 102 + 6 101 + 1 100 = 1771561

Er blijkt 1771561 = 116.

We kunnen bewijzen dat het getal dat met de n-de rij overeenkomt gelijk is aan 11n. Daarvoor bekijken we nogmaals de driehoek van Pascal, maar dan genoteerd m.b.v. binomiaalcoŽfficiŽnten.

rij - 0                  
0
0
                 
rij - 1
1
0
1
1
rij - 2
2
0
2
1
2
2
rij - 3
3
0
3
1
3
2
3
3
rij - n
 n
0
 n
 p -1
 n
 p
 n
n -1
 n
 n

Het getal  g dat met de n-de rij overeenkomt berekenen we als volgt:

g
 n
0
  10n  +
 n
1
  10n-1  + +
 n
 p
  10n-p + +
 n
 n
  100

In verkorte vorm, gebruikmakende van het somteken

g = 10n- p

Volgens het Binomium van Newton geldt:

11n  = (10 + 1)n = 10n- p 1 p = 10n- p = g

Hiermee is bewezen dat g = 11n.

Omhoog


Het hockeystickpatroon
Als je een willekeurig aantal opeenvolgende getallen op een diagonaal, te beginnen met het getal 1 op ťťn van de randen, bij elkaar optelt, dan is de som gelijk aan het getal dat niet op de diagonaal ligt direct onder het laatste getal. Je herkent hierin een hockeystickpatroon. In onderstaande figuur zie je een aantal voorbeelden.

               1 + 3 = 4
               1 + 4 + 10 = 15
               1 + 8 + 36 + 120 = 165
               1 + 6 + 21 + 56 + 126 = 210

Om te bewijzen dat dit altijd zo is, en niet alleen geldt voor de voorbeelden die we gegeven hebben moeten we bewijzen dat:

S
 r
0
 +
 r + 1
1
  +
 r + n
 n
 = 
 r + n +1
 n
 voor r, n0

Of in verkorte vorm, gebruikmakende van het somteken

S =  n
 r + p
 p
 = 
 r + n +1
 p
 voor n, p, r0
 p = 0

Hierin is r het rijnummer van de rij waar het hockeystickpatroon begint en n + 1 het aantal getallen op de steel,  de lengte van de steel dus.

Bewijs
We geven het bewijs m.b.v. het principe van de "Volledige Inductie".

Stap 1
We gaan uit van een willekeurig rijnummer r en tonen eerst aan dat de formule juist is voor n = 0. Gemakkelijk is na te gaan dat:

 0
 p = 0
 r + p
 p
 = 
 r + 0
 0
 =  1  = 
 r + 0 +1
 0
 voor n, r0

Stap 2
We nemen nu aan dat de formule juist is voor n = m 0 en gaan bewijzen dat daaruit volgt dat de formule ook juist is voor n = m +1. Als de formule juist is voor n = m dan geldt:

 m
 p = 0
 r + p
 p
 = 
 r + m +1
 m
 voor r 0 en m

We moeten nu bewijzen dat daaruit volgt dat:

 m + 1
 p = 0
 r + p
 p
 = 
 r + m +2
 m + 1
 voor r 0 en m

Er geldt:

 m + 1
 p = 0
 r + p
 p
 = 
 m
 p = 0
 r + p
 p
 + 
 r + m + 1
 m + 1
 
 = 
 r + m +1
 m
 + 
 r + m + 1
 m + 1
 
Volgens de optelregel is dit:
 
 = 
 r + m + 2
 m + 1

Hetgeen te bewijzen viel!

Je ziet dat de optelregel, ook wel de formule van Pascal, ook hier weer een belangrijke rol speelt.

Opmerking
Vanwege de symmetrie geldt deze eigenschap ook voor hockeystickpatronen die op de rechterzijde van de driehoek van Pascal beginnen.

Omhoog


In deze les zijn slechts een beperkt aantal eigenschappen behandeld. Eigenschappen waarvan het bewijs binnen het bereik van HAVO 5 en VWO 5/6 leerlingen ligt. GeÔnteresseerde leerlingen worden aangespoord op zoek te gaan naar de vele andere websites over de driehoek van Pascal waar het verband met de combinatoriek, waarschijnlijkheidsleer en andere takken van de wiskunde aan de orde komen. De zoekmachine Google is daarvoor een uitstekend hulpmiddel.

 Omhoog


Appendix


Het bewijs van de symmetrie eigenschap: = . Volgens de definitie geldt:

 

 =  
 n!
 (n - p)!(n - (n - p))!
 
 =  
 n!
 (n - p)!(n - n + p)!
 
 =  
 n!
 (n - p)!p!
 
 =  
 n!
 p!(n - p)!
 
 =  

Hetgeen te bewijzen viel!


Het bewijs van de formule van Pascal: + =

We beschouwen eerst de term . Er geldt:

 

 =  
n!
 p!(n - p)!
 
 =  
 n + 1 - p     (n + 1)n!
n + 1  p!(n + 1 - p)(n - p)!
 
 =  
 n + 1 - p     (n + 1)!
n + 1  p!(n + 1 - p)!
 
 =  
 n + 1 - p   
n + 1
                                                (1)

We beschouwen nu de term . Volgens de definitie geldt:

 

 =  
n!
 ( p - 1)!(n - (p - 1))!
 
 =  
  p     (n + 1)n!
 n + 1  p( p - 1)!(n + 1 - p)!
 
 =  
  p     (n + 1)!
 n + 1  p!(n + 1 - p)!
  
 =  
  p   
 n + 1
                                                (2)

Uit (1) en (2) volgt:   

 

 +    =  
  p     +    n + 1 - p   
 n + 1 n + 1
 
 = 
  p  +    n + 1 - p   
 n + 1 n + 1
 
 = 
 p + n + 1 - p   
 n + 1
 
 = 
 n + 1   
 n + 1
 
 = 
  
 
     = 

Hetgeen te bewijzen viel!


Het bewijs van de regel: 

 n - p + 1 
 p
 

We beschouwen de term . Volgens de definitie geldt:

 

 =  
n!
 p!(n - p)!
 
(n + 1 - p)n!
 p( p - 1)!(n + 1 - p)(n - p)!
 
 =  
  (n + 1 - p)    n!
p  ( p - 1)!(n + 1 - p)!
 
 =  
  (n + 1 - p)    n!
p  ( p - 1)!(n - (p - 1))!
  
 =  
  (n + 1 - p)   
p
                                               

Hetgeen te bewijzen viel!


Omhoog