driehoek van Pascal


De driehoek van Pascal.	© h.hofstede (h.hofstede@hogeland.nl)

In de linkerfiguur hierboven zijn nogmaals alle aantallen routes vanaf S in een regelmatig rooster weergegeven We weten intussen al dat de getallen precies de combinaties (nCr) weergeven. In de rechterfiguur is het rooster gedraaid zodat S bovenaan ligt. Als we de getallen nu weer rechtop zetten dan krijgen we de driehoek hier linksonder.

Rechts zie je dat daar eigenlijk alle combinaties op een rijtje staan.
De driehoek rechts heet de Driehoek van Pascal.

Elk getal uit de driehoek wordt dus gevonden door de getallen er direct linksboven en rechtsboven bij elkaar op te tellen. Dat zie je in de animatie hieronder.

Een paar interessante eigenschappen.

Tel de som van alle getallen van een rij op.
Dat geeft de sommen 1 - 2 - 4 - 8 - 18 - 32 - ....
Dat zijn precies de machten van 2.

Dat kun je als volgt zien:
Bekijk een rijtje van bijvoorbeeld 6 letters, A of B
Met 0 A's zijn er 6 nCr 0 = 1 mogelijkheden
Met 1 A is er 6 nCr 1 = 6 mogelijkheden
Met 2 A's zijn er 6 nCr 2 mogelijkheden
eenz.

In totaal zijn er (6 nCr 0) + (6 nCr 1) + (6 nCr 2) + ... + (6 nCr 6) mogelijkheden en dat is precies de som van de getallen van de zesde rij van de driehoek van Pascal.

Maar je kunt het totaal mogelijkheden ook als volgt berekenen:
Je moet 6 keer kiezen uit A of B. Zes keer uit twee mogelijkheden kiezen kan op 2⁶manieren.
Daarom is de som van de zesde rij gelijk aan 2⁶
En hetzelfde geldt natuurlijk voor een willekeurige andere rij.....

De priemgetal-rijen bestaan uit allemaal veelvouden van dat priemgetal.
Zo is de zevende rij bijvoorbeeld gelijk aan 1-7-21-35-35-21-7-1; allemaal zevenvouden!
En de elfde rij: 1-11-55-165-330-462-462-330-165-55-11-1; allemaal elfvouden!
Dat blijkt voor elk priemgetal zo te zijn!

Bewijs.

Daar rechts valt (p - r)(p - r - 1) ... 1 boven en onder de streep weg, zodat overblijft:

Kijk naar die p in de teller.
Omdat p een priemgetal is, kan die nooit wegvallen tegen een getal uit de noemer (die zijn allemaal kleiner dan p).
Dus de resulterende waarde van deze breuk zal altijd een priemfactor p hebben, dus deelbaar door p zijn.

Deze beide eigenschappen samen hebben weer een grappig bijgevolg.
Als de som van alle getallen uit een rij gelijk is aan 2^p en als dat (op de beide enen aan begin en eind na) allemaal veelvouden van p zijn, dan geldt dus dat 2^p - 2 voor elk priemgetal p altijd een veelvoud van p is!
Kijk maar:
2³ - 2 = 6, is een veelvoud van 3
2⁵ - 2 = 30, is een veelvoud van 5
2⁷ - 2 = 126, is een veelvoud van 7
2¹¹ - 2 = 2046, is een veelvoud van 11
enz.

(N.B. Dit is een speciaal geval van het theorema van Fermat, dat zegt dat voor elk priemgetal p geldt dat a^p - a een veelvoud van p is. Het geval a = 2 volgt dus gewoon uit de combinatieleer)

OPGAVEN

Uit de driehoek van Pascal volgt dus dat

Bewijs deze regel door de combinaties uit te schrijven als faculteiten.
Bedenk daarbij dat geldt:

Je hebt een stapeltje van 12 Donald Ducks in je kast liggen. Daarvan ga je er 5 aan je vriendje uitlenen.
Bij elke Donald Duck moet je dus beslissen of je hem wel (W) of niet (N) aan hem gaat uitlenen. Je zult vijf keer W kiezen en 7 keer N.
Bij welk getal uit welke rij van de driehoek van Pascal kun je het totaal aantal manieren waarop je de Donald Ducks kunt uitkiezen vinden? Hoe groot is dat aantal manieren?

792

Teken een groot stuk van de driehoek van Pascal. Kleur nu vervolgens alle oneven getallen zwart.
Wat valt je op aan de figuur die dan ontstaat?
Deze figuur is een zogenaamde fractal en heet de Sierpinski-driehoek.