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\]

Het 3n+1 vermoeden

Neem een natuurlijk getal n. Als het even is, deel het door 2. Als het oneven is, vermenigvuldig je het met 3 en tel er 1 bij op. Met de uitkomst doe je hetzelfde, en dat blijf je maar herhalen.

Neem bijvoorbeeld 6, dan ontstaat volgende rij : 6,3,10,5,16,8,4,2,1. We noemen dit de Collatz rij van 6. De lengte van deze Collatz rij is 9. De lengte van dergelijke rij kan snel oplopen. Zo is de lengte van de  Collatz rij van 27 gelijk aan 111.

Het 3n + 1-vermoeden zegt dat bovengenoemd iteratieproces bij iedere mogelijke startwaarde altijd een keer bij 1 zal uitkomen. De precieze oorsprong van het 3n + 1- vermoeden is niet helemaal duidelijk. In de jaren dertig was Lothar Collatz( 1910-1990), een Duitse wiskundige, met soortgelijke problemen bezig, en het 3n + 1-probleem wordt algemeen aan hem toegeschreven. Het is tot op heden nog steeds niet bewezen.

Er zijn enkele aanwijzingen dat het vermoeden van Collatz juist is. Voor alle getallen onder 10^{19}   is inmiddels gecontroleerd dat ze aan het vermoeden voldoen. Het probleem met het controleren is dat het alleen het vermoeden kan weerleggen. Als het vermoeden waar is, kan er geen bewijs voor gevonden worden op deze manier.

Bewijzen met verhaaltjes

Hoe bewijs je volgende formule? 

    \[k(k-1)\binom{n}{k}=n(n-1)\binom{n-2}{k-2}\]

Het gaat zeer snel door gebruik te maken van de definitie van  binomiaalcoëfficiënten. Maar er is ook een andere manier, die je ook kan gebruiken als het gebruik van de definitie wat ingewikkelder ligt. We verzinnen gewoon een verhaaltje …

Je wilt op school met n leerlingen een leerlingenraad van k personen oprichten, waarbij een voorzitter en een ondervoorzitter moeten aangeduid worden.

  • Het linkerlid van bovenstaande vergelijking komt overeen met volgende procedure: kies eerst k leden uit de n leerlingen. Dit  kan op \binom{n}{k} manieren. Kies in die groep van k gekozenen een voorzitter ( k mogelijkheden) en een ondervoorzitter ( k-1 mogelijkheden).
  • Het rechterlid correspondeert met de procedure: kies uit de n leerlingen eerst een voorzitter ( n mogelijkheden), dan een ondervoorzitter( n-1 mogelijkheden) en vul tenslotte aan tot je een groep van k leden hebt. Je moet dus nog k-2 leerlingen kiezen uit de n-2 beschikbare (\binom{n-2}{k-2} mogelijkheden).
  • Aangezien beide procedures hetzelfde probleem oplossen , zijn linkerlid en rechterlid gelijk aan elkaar.

Technieken bij kansrekening

We onderzoeken 3 types oefeningen van kansrekening, gebaseerd op de manier waarop we ze benaderen.

  • Door te tellen. Neem bijvoorbeeld een zak met 16 knikkers , 4 blauwe en 12 groene. Je neemt er twee tegelijkertijd. Wat is de kans dat ze allebei blauw zijn? We gebruiken de formule van Laplace en we zoeken eerst het aantal mogelijkheden om 2 knikkers te nemen: C(16,2), het aantal combinaties van 2 elementen uit 16. Dan tellen we het aantal gunstige mogelijkheden: C(4,2). Besluit, na vereenvoudiging :

        \[P(\text{ 2 keer blauw} )= \dfrac{1}{20}\]

  • Meetkundige benadering. Neem een getal tussen 1 en 4 en een tweede getal tussen 2 en 6. Bereken de kans dat de som van die twee getallen groter is dan 5.Alle mogelijkheden om die 2 getallen te nemen komen overeen met de punten in de rechthoek ABCD.  De rechte Ef heeft vergelijking x+y=5. De gunstige mogelijkheden zijn de punten in de veelhoek EBDCF. De kansen kunnen nu berekend worden door de oppervlakten te delen. Nu is E(1,4) en F(3,2), dus we vinden

        \[P(x+y>5)=\dfrac{5}{6}\]

  • Kansen bereken via algebra. Jan en Piet spelen een spel met twee dobbelstenen. Ze gooien om de beurt en wie het eerst dubbel 1 gooit, die wint. Jan mag beginnen. Hoe groot is de kans dat Jan wint?Noteer de winstkansen van Jan en Piet respectievelijk door x en y. Dan weten we al zeker dat x+y=1. De kans dat Jan wint bij de eerste worp is \dfrac{1}{36}. De kans dat Piet bij zijn eerste worp wint is \dfrac{35}{36}*\dfrac{1}{36},  want eerst moet Jan verliezen en dan moet hij winnen. De kans dat Jan wint bij zijn tweede worp is \dfrac{1}{36}*\Big(\dfrac{35}{35}\Big)^2 . De kans dat Piet  wint bij zijn tweede worp is \dfrac{1}{36}*\Big(\dfrac{35}{35}\Big)^3. Je kan zo verder gaan en via de som van de termen van een meetkundige reeks het gewenste resultaat vinden, maar je kan ook opmerken dat de kans dat Piet wint altijd de kans is dat Jan wint vermenigvuldigd met \dfrac{35}{36}, dus y=\dfrac{35}{36}*x. Je krijgt een stelsel met 2 vergelijkingen en 2 onbekenden, dat als resultaat geeft dat x=\dfrac{36}{71}

Een korte geschiedenis van pi

Pi is de verhouding tussen de omtrek en de middellijn van een cirkel:

    \[\pi=\dfrac{\text{omtrek}}{\text{middellijn}}\]

Dit leidt tot de misvatting dat pi een rationaal getal is, want het kan geschreven worden als een breuk! We vergeten hierbij dat, in een breuk, felle en noemer gehele getallen moeten zijn. Maar bij pi is hetzij de omtrek , hetzij de diameter irrationaal. 

Het idee van pi als constante bestaat al lang. De Egyptenaren schatten het op \frac{25}{8}=3,125 en de Mesopotamiërs gaven het de waarde van \sqrt{10}\approx 3,162.

Archimedes was de eerste die pi grondig onderzocht. Door veelhoeken in een cirkel te  tekenen en hun omtrek te berekenen, kon hij pi schatten tussen \frac{223}{71} en \frac{22}{7}. sinds Archimedes is de nauwkeurigheid van pi groter geworden. Dank zij de computer kennen we nu pi tot op miljarden cijfers nauwkeurig.

Een paar schattingen door de eeuwen heen:

  • papyrus Rhind ( 1650 BC) :  3,16045
  • Archimedes (250 BC) : 3,1418
  • Ptolemaeus (150 AD) 3,14166
  • Brahmagupta (640 AD): 3,1622   
  • Al-Khwarizmi (800 AD) : 3,1416
  • Fibonacci (1220 AD) : 3,141818

Het symbool \pi, voor pi werd in 1706 geïntroduceerd door William Jones in zijn boek Synopsis Palmariorum Mathesis. 

Pi kan ook voorgesteld worden door een reeks . De veertiende eeuws Indiase wiskundige Madhava gebruikte de volgende reeks :

    \[\frac{\pi}{4}=1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\frac{1}{9}\cdots\]

Dit convergeert eerder traag naar pi. Euler gebruikte de reeks :

    \[\frac{\pi^2}{6}=1+\frac{1}{2^2}+\frac{1}{3^2}+\frac{1}{4^2}+\frac{1}{5^2}\cdots\]

De Engelse wiskunde Wallis maakte gebruik van:

    \[\frac{\pi}{2}=\frac{2}{1}*\frac{2}{3}*\frac{4}{3}*\frac{4}{5}*\frac{6}{5}\cdots\]