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 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.

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.

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.

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 n^e 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.

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

We kunnen bewijzen dat de som van de getallen in de n-de rij gelijk is aan 2ⁿ. 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 = 2ⁿ.

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.

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

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.

Dus is

n  p

=

n  m een veelvoud van n.

Hiermee is het bewijs geleverd.

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.
  

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 10³ + 1 10² + 5 10¹ + 7 10⁰

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 10⁵ + 5 10⁴ + 10 10³ + 10 10² + 5 10¹ + 1 10⁰ = 161051

Er blijkt 161051 = 11⁵.

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

1 10⁶ + 6 10⁵ + 15 10⁴ + 20 10³ + 15 10² + 6 10¹ + 1 10⁰ = 1771561

Er blijkt 1771561 = 11⁶.

We kunnen bewijzen dat het getal dat met de n-de rij overeenkomt gelijk is aan 11ⁿ. 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 = 11ⁿ.

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, n 0

Of in verkorte vorm, gebruikmakende van het somteken

S =	n	r + p  p	=	r + n +1  p	voor n, p, r 0
	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, r 0

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 0

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 0

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.

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.

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
				=	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!