Categorie archieven: Discrete wiskunde

Pariteit van een permutatie

Geplaatst op door

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

Geplaatst op door

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

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.