Tag archieven: permutaties

Even en oneven elementen

Geplaatst op door

Hoe groot is de kans dat bij een permutatie van \{1,2,...,n\} geen 2 even elementen en geen 2 oneven elementen naast elkaar staan?

Of anders geformuleerd: Er zijn in een gezelschap een aantal jongens en een aantal meisjes. Ze moeten op 1 rij gaan staan. Hoe groot is de kans dat geen twee jongens of twee meisjes naast elkaar gaan staan?

  • Het totaal aantal permutaties van n elementen is n!.
  • Als n even is ( n = 2m) zijn er evenveel jongens als meisjes. Er zijn twee mogelijke schikkingen JMJM… of MJMJ…; Bij elk van de mogelijkheden kan je de jongens op m! manieren ordenen en ook de meisjes op m! manieren rangschikken. Het totaal aantal mogelijkheden is dus 2.m!.m!
  • Als n oneven is (n = 2m – 1) zijn er bijvoorbeeld m – 1 jongens en m meisjes. in dit geval kan je enkel MJM…krijgen en zijn er dus in het totaal (m-1)!.m! mogelijkheden.
  • Noteer met P(n) de kans dat geen twee jongens of twee meisjes naast elkaar gaan staan bij n personen. Als n = 2m, dan is

        \[K(2m)=K(2m-1)=\frac{m!}{m(m+1)...(2m-1)}\]

  • Zo is K(1)=K(2)=1; K(3)=K(4)=33,3% ; K(5)=K(6)=10% ; K(7)=K(8)=2,86% en K(9)=K(10)=0,79%

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)

 

Schuifpuzzel

Geplaatst op door

 

De schuifpuzzel is een puzzel, meestal op een bord van 4  op 4 met 15 verschillende stukken en 1 leeg veld; Het wordt dan ook   15-puzzel genoemd, maar bestaat ook in andere afmetingen. De bedoeling is om de stukken terug in de goede volgorde te krijgen door de stukken te schuiven.

De oorspronkelijke versie van dit spel werd in 1874 ontwikkeld door de New Yorkse postdirecteur Noyes Palmer Chapman. De vierkantjes zaten los en de speler kon ze in willekeurige volgorde neerleggen en dan proberen de puzzel door schuiven op te lossen. In de afbeelding hierboven uit Sam Loyds Cyclopedia waren in de beginpositie de getallen 14 en 15 van plaats gewisseld. 

Niet elke beginpositie is oplosbaar. Wiskundigen hebben onderzocht welke beginopstellingen kunnen worden opgelost. Neem bijvoorbeeld bovenstaande puzzel, beter afgebeeld als:

Is dit oplosbaar?

Twee speltoestanden worden als equivalent gedefinieerd als de ene door een aantal malen schuiven in de andere kan worden overgevoerd. Deze relatie is een equivalentierelatie.  Of  de puzzel oplosbaar is betekent dus of bovenstaande schikking equivalent is met de begintoestand. Men kan aantonen dat twee speltoestanden equivalent zijn als de pariteit van de permutatie van de 16 elementen die de ene in de andere overvoert gelijk aan die van de ‘afstand’  tussen de lege velden van de twee speltoestanden (dit betekent dat de twee lege velden zoals bij een schaakbord dezelfde of een verschillende kleur hebben). Wat geeft dit nu voor onze opgave?

  • de lege vakken staan in begin en eind situatie opdezelfde plaats: dus pariteit 0
  • De eindsituatie wordt bekomen uit de beginsituatie via 1 transpositie ( 1 omkering: 14 versus 15); Dus is de permutatie oneven en heeft pariteit 1.
  • De twee pariteiten zijn verschillend en dus is de puzzel onoplosbaar. Er werd dus ten onrechte een prijs van 1000$ uitgereikt voor de oplossing!

 

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

Nagels en draad

Geplaatst op door

Een aardig knutselwerkje: klop wat nagels in een plank en verbind deze met wat draad en probeer alzo een mooie figuur te bekomen. In volgend artikel kan je lezen over een wiskundige versie van deze activiteit. Permutaties en ideeën uit d etheorie der groepen worden hier geïllustreerd.