Categorie archieven: Discrete wiskunde

Derangement

Geplaatst op door

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

Geplaatst op door

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.

De huwelijksstelling van Hall

Geplaatst op door

Zes vrouwen vallen elk op een aantal vrijgezelle mannen. Kunnen de zes vrouwen met de zes mannen worden gekoppeld, zó dat elke vrouw een man van haar keuze trouwt?

In sommige gevallen is het eenvoudig om te zien dat er geen oplossing mogelijk is. Als er een dame bij is die niemand leuk vindt, lukt het niet. Ook als er twee vrouwen zijn die enkel één en dezelfde man willen, loopt het mis.

Kan het met de volgende keuze?
Een nodige en voldoende voorwaarde op het bestaan van een oplossing is dat iedere k dames samen met tenminste k  verschillende mannen willen trouwen. Hierbij is 1 \leq k\leq6. Omdat de dames a,c,d en f samen maar drie verschillende mannen willen huwen, namelijk de nummers 2,3 en 6, is het dus onmogelijk alle zes dames uit te huwelijken!

Deze stelling, die dateert uit 1933, werd bewezen door de Engelse wiskundige Philip Hall ( 1904-1982).

Als het zo is dat we niet alle dames kunnen koppelen, dan kunnen we ons wel de vraag stellen: wat is het maximaal aantal dames dat kan gekoppeld worden?

Hiervoor vertalen we het probleem naar een probleem met grafen: Voor iedere vrouw is er een bijhorend punt in A en voor iedere man is er een punt in B. We trekken een lijn tussen een vrouw en een man, als zij met hem wilt trouwen.

De resulterende graaf heet bipartiet omdat de punten zijn opgedeeld in twee groepjes en lijnen altijd punten uit verschillende groepen verbinden. Een aantal lijnen noemt men een matching als geen twee lijnen eenzelfde eindpunt hebben. Een uithuwelijking is dus eigenlijk een matching. In het rood staat hierboven een matching met 4 lijnen. Een betere matching wordt gegeven door volgende figuur, waarin 5 vrouwen kunnen worden uitgehuwelijkt.

Vierkanten en rechthoeken op een schaakbord

Geplaatst op door

Hoeveel vierkanten en rechthoeken kan men vormen op een n x n schaakbord?

  • Nemen we eerst het aantal vierkanten. We noteren V(n) voor het aantal vierkanten dat je kan tekenen op een nxn bord. Voor de 1×1 vierkanten heb je n mogelijke verticale posities en n horizontale, dus n^2 mogelijke vierkanten. Voor de 2×2 vierkanten heb je n – 1 verticale en horizontale mogelijke plaatsingen , dus (n-1)^2 mogelijkheden. Uiteindelijk is het totaal aantal vierkanten gelijk aan n^2+(n-1)^2+\cdots+2^2+1^2. 

        \[V(n)=\frac{n(n+1)(2n+1)}{6}\]

  • Met R(n) noteren we het aantal rechthoeken dat je kant tekenen op een nxn schaakbord. Voor een rechthoek heb je 2 verticale en twee horizontale lijnen nodig. Er zijn n+1 verticale en n+1 horizontale lijnen op een schaakbord. Om de verticale lijnen te kiezen heb je dus {n+1}\choose{2} =\frac{n(n+1)}{2}  mogelijkheden. Idem voor de keuze van de twee horizontale lijnen. Dus

        \[R(n)=\frac{n^2(n+1)^2}{4}\]

  • Voor een 8×8 schaakbord heb je dus 204 vierkanten en 1296 rechthoeken. Van die rechthoeken zijn er 1092 die geen vierkant zijn.

Delannoy getallen

Geplaatst op door

Beschouw in het vlak de punten P(x,y) met  natuurlijke getallen als coördinaten .Je kan je verplaatsen in het vlak volgens de vectoren (1,0) , (0,1)  en (1,1). Het aantal manieren waarop men vanuit de oorsprong het punt P(m,n) kan bereiken noemt men het Delannoy getal d(m,n), vernoemd naar de Franse legerofficier en amateur wiskundige Henri-Auguste Delannoy (28 sept 1833 – 5 febr 1915). Bij definitie stellen we d(0,0)=1.

Onderstaande tekening laat zien dat er bijvoorbeeld 13 mogelijke manieren zijn om het punt P(2,2) te bereiken:

Een tabel met enkele waarden van de Delannoy getallen :

We geven enkele eigenschappen:

  • d(m,0) = d(0,n) = 1
  • Er is een recursief verband tussen deze getallen: d(m,n) = d(m – 1,n) + d(m,n – 1) + d(m – 1,n – 1): elk getal in bovenstaande tabel is de som van zijn linkerbuur, zijn bovenbuur en het getal linksboven. Dit wordt beter geïllustreerd als we de tabel geven in de vorm van de driehoek van Pascal. ( teken de diagonalen van bovenstaande tabel). Nu is elk getal de som van de driehoek erboven.
  • We stellen de verplaatsingen over (1,0), (0,1) en (1,1) respectievelijk voor door O,N en D. Wanneer we k keer D gebruiken om P(m,n) te bereiken,  moeten we m – k keer O en n – k keer N gebruiken. Om te berekenen op hoeveel manieren dit kan, maken we gebruik van de formule van de herhalingspermutaties : we moeten
    k + (m – k) + (n – k ) = m + n – k symbolen rangschikken, waarvan er k van het soort D zijn , m – k van het soort O en  n – k van het soort N. We vinden dus voor elke waarde van k kleiner of gelijk aan het minimum van m en n als aantal mogelijkheden:

        \[\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

    In het totaal heb je dan :

        \[\sum_{k=0}^{ min(m,n)}\dfrac{(m+n-k)!}{k! (m-k)! (n-k)!}\]

  • Op de tweede rij en tweede kolom vinden we alle oneven getallen :
    d(m,1) = 2m+1. Dit is gemakkelijk te bewijzen met bovenstaande formule