Even en oneven elementen

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%

Stochastische wandelingen

We bestuderen enkele eenvoudige stochastische wandelingen in d = 1,2 of 3 dimensies. Hier beweegt een fictieve wandelaar over het rooster \mathbb{Z}^d door vanuit een punt naar één van de 2d buurpunten te lopen. Bij elke stap die hij doet zijn alle 2d richtingen even waarschijnlijk. Bovendien zijn alle stappen onafhankelijk van elkaar. De stochastische wandeling wordt ook wel eens de dronkemanswandeling genoemd, omdat de stappen van een (echt) dronken man goed gemodelleerd zouden kunnen worden met toevallige gebeurtenissen.


We onderzoeken de  stelling van Polya die zegt dat het deeltje zeker terugkomt naar de beginpositie enkel en alleen als de wandeling gebeurt in 1 of 2 dimensies. De stelling van Pólya is ook wel eens als volgt geformuleerd: a drunken man will always come home, but a drunken bird never will. Lees meer hierover in volgende tekst.