Kwadraten in de driehoek van Pascal

In de driehoek van Pascal kan je veel verbanden vinden. Vandaag gaan we op zoek naar kwadraten.

  • Kijk naar de derde kolom van de driehoeksgetallen 1,3,6,10,… en tel daar de elementen twee per twee op en je vindt de rij 4,9,16,25,… Hoe kan je dit verklaren?  De som van de elementen is altijd van de vorm

        \[\binom{n}{2}+\binom{n+1}{2}\]


    Uitrekenen geeft \frac{1}{2}n(n-1)+\frac{1}{2}n(n+1)=n^2.
  • Kijk naar de vierde kolom 1,4,10,20,35,56,…en bereken het verschil van de derde en de eerste, de vierde en de tweede enz. , dan vorm je de rij 9,16,25,… Verklaring?

        \[\binom{n+2}{3}-\binom{n}{3}\]

    Uitrekenen met de formule van Stiffel geeft: \Big(\binom{n+2}{3}-\binom{n+1}{3}\Big)+\Big(\binom{n+1}{3}-\binom{n}{3}\Big)=\binom{n+1}{2}+\binom{n}{2}=n^2.

Pariteit van een permutatie

Elke permutatie kan geschreven worden als het product ( samenstelling) van transposities. Een transpositie of omwisseling is een twee-cykel, zoals bijvoorbeeld (12).

Dit product kan op verschillende manieren tot stand komen, maar het is wel zo dat het aantal transposities dat je nodig hebt, steeds hetzelfde is. Als dat aantal even is , spreken we van een even permutatie. Als het aantal oneven is , spreken we van een oneven permutatie.  Dit noem je de pariteit van de permutatie

Een voorbeeldje van een oneven permutatie:

    \[(1234) =(14)(13)(12)\]

    \[(1234)=(12)(23)(34)\]

Let op de volgorde! Zoals bij de samenstelling , werken we van achter na voor. Nog een paar voorbeelden met afbeelding:

 

is een even permutatie, want de permutatie is te schrijven als (16)(15)(13)(28)(27)(24).

is een oneven permutatie, want de permutatie is te schrijven als (14)(32)(35)

 

Stelling van Van der Waerden

In de wiskunde zijn er verschillende  stellingen die elk op hun eigen manier zeggen dat totale wanorde onmogelijk is.  Zo hebben we bijvoorbeeld het vermoeden van Baudet: Als je de hele verzameling \mathbb{N} in twee verzamelingen A en B verdeelt, is het dan noodzakelijk zo dat (ten minste) één van die twee verzamelingen willekeurig lange rekenkundige rijtjes bevat?

De Nederlandse wiskundige Van der Waerden publiceerde in 1927 een bewijs. In het artikel staat een algemenere bewering :  voor elk paar positieve gehele getallen r en k is er een getal N zodanig dat indien men {1, 2, …, N }  in r  klassen verdeelt, er minstens een klasse is die een rekenkundige rij van lengte k bevat. Het kleinste getal N waarvoor dit geldt noemt men het Van der Waerden-getal W(r,k).

Zo is bijvoorbeeld W(2,3) =  9. Een kleinere waarde is er niet want {{1,2,4,5},{3,4,6,8}} is een verdeling van {1,2,3,4,5,6,7,8} in twee delen die geen rekenkundige rij met 3 elementen bevat. In onderstaande tekening kleur je de getallen van 1 tot en met 9 in 2 kleuren; je ziet dat je steeds een rekenkundige rij van drie elementen krijgt in eenzelfde kleur.

Derangement

Een derangement is een permutatie zonder vaste punten, met andere woorden een ordening waar geen enkel element op de juiste plaats staat.  Het aantal derangements van n verschillende elementen wordt aangeduid met !n : subfaculteit. Het probleem van het tellen van het aantal derangementen werd in 1708 voor het eerst beschouwd door Pierre Raymond de Montmort, die het probleem oploste in 1713, ongeveeer tegelijkertijd met Nicolaas Bernoulli.

Voor 3 elementen zijn er 3! = 6 permutaties. De ordeningen  312 en 231 zijn derangements. Het zijn de enige, dus !3=2. Voor 4 elementen is, het al wat moeilijker:

Hierboven zie je de 24 permutaties van de 4 elementen {1,2,3,4}. De blauwe zijn de derangements, dus !4=9. Je kan nagaan dat !5=44, !6= 265 en !7=1854. Er zijn echter ook formules beschikbaar om de subfaculteiten uit te rekenen:

    \[\text{!n}=(n-1)[!(n-1)+!(n-2)]\]

    \[\text{!n}=n!\sum_{i=0}^n\dfrac{(-1)^i}{i!}\]

 

Uit deze laatste formule kan je de verhouding tussen !n en n! afleiden:

    \[\dfrac{!n}{n!}=\dfrac{1}{e} \approx 0,368\]

Stapelen

Hoe kan je 15 appelsienen (allemaal even groot) in een zo klein mogelijke vierkante doos schikken? 
Je zou 4 rijen van 4 kunnen nemen en er eentje uitnemen. Dan heeft de doos een lengte gelijk aan vier keer de diameter van de appelsien. Kan het in een kleinere doos? En hoeveel ruimte blijft er dan over?

Vraagstukken over het stapelen van bollen ( appelsienen, knikkers, biljartballen, kanonskogels of moleculen) vormen uitdagende wiskundige problemen.

 In 1587 keek ontdekkingsreiziger Walter Raleigh naar een piramidevormige stapel kanonskogels en vroeg zich af , of er een formule bestond die berekende hoeveel kogels er in zo een stapel waren. Hoe groot waren de gaten tussen de kogels? En kon je de bollen misschien efficiënter opstapelen? Hij speelde zijn vragen door naar de Duitse wiskundige Johannes Kepler die in 1611 het vermoeden formuleerde dat het niet beter kon dan de gebruikelijke manier van stapelen. Deze manier van stapelen vult iets meer dan 74% van de ruimte . Elke andere schikking van even grote bollen zou gemiddeld meer ruimte ongebruikt laten.

Dit kon slechts in 1998 bewezen worden door de Amerikaan Thomas Hales. Het bewijs was gebaseerd op een computercontrole van een groot aantal gevallen en werd pas in 2017 officieel aanvaard.