Dumontpermutatie

Dumontpermutaties, genoemd naar de wiskundige Dominique Dumont, zijn permutaties die aan welbepaalde voorwaarden moeten voldoen. Dumont legde het verband tussen dergelijke permutaties en de Genocchigetallen.

Dumontpermutaties zijn gedefinieerd op permutaties van een even aantal getallen.

Dumontpermutaties van de eerste soort

Een Dumontpermutatie van de eerste soort is een permutatie $P=p_1,p_2,\dots ,p_n$ van $1,2,\dots ,n$ waarin voor elke $i=1,2,\dots ,n$:

• als $p_i$ even is, dan is $p_i>p_{i+1}$
• als $p_i$ oneven is, dan is $p_i<p_{i+1}$ of $i=2n$.

In een dergelijke permutatie is een even getal dus groter dan het daaropvolgende (wat betekent dat de permutatie niet kan eindigen op een even getal) en een oneven getal kleiner dan het daaropvolgende, of het is het laatste van de permutatie. Anders gezegd: van links naar rechts beschouwd, begint elke daling bij een even getal en elke stijging bij een oneven getal.

Voorbeeld: van al de permutaties van vier elementen 1,2,3,4 zijn dit de enige Dumontpermutaties van de eerste soort:

• 2,1,4,3
• 3,4,2,1
• 4,2,1,3

Dumontpermutaties van de tweede soort

In een Dumontpermutatie van de tweede soort van $1,2,\dots ,2n$ geldt voor elke $i=1,2,\dots ,n$:

• $p_{2i}<2i$ en
• $p_{2i-1}\ge 2i-1$

Elk getal op een even positie is dus kleiner dan het volgnummer van die positie, en elk getal op een oneven positie is groter dan of gelijk aan het volgnummer van die positie.

Voorbeeld: van al de permutaties van vier elementen 1,2,3,4 zijn dit de enige Dumontpermutaties van de tweede soort:

• 2,1,4,3
• 3,1,4,2
• 4,1,3,2

Dumont toonde aan dat er een bijectie kan gemaakt worden tussen de verzameling van de Dumontpermutaties van de eerste soort en die van de tweede soort van dezelfde lengte, wat betekent dat er evenveel Dumontpermutaties zijn van de eerste soort als van de tweede soort.

Aantal Dumontpermutaties

Noem $D_1(2n)$ het aantal Dumontpermutaties van de eerste soort met lengte $2n$ en $D_2(2n)$ het aantal Dumontpermutaties van de tweede soort met lengte $2n$. Dumont bewees dat:

$D_1(2n)=D_2(2n)=|G(2n+2)|$,

waarin $G(i)$ het i-de Genocchigetal is, een veelvoud van het i-de Bernoulligetal.

De even Genocchigetallen zijn de rij (Sjabloon:Link OEIS):

$-1,1,-3,17,-155,2073,-38227,929569,-28820619,\dots$

Opmerking: De definities van Dumontpermutaties zijn ook geldig voor permutaties van oneven lengte $2n+1$ als men het grootste element $2n+1$ als laatste plaatst in de permutatie. Het aantal Dumontpermutaties verandert daardoor niet.

Dumontpermutaties van de derde en vierde soort

Burstein et al. onderzochten de permutaties waarin, van links naar rechts beschouwd, elke daling gebeurt van een even getal naar een even getal. Dit zijn dus de permutaties $P=p_1,p_2,\dots ,p_n$ van $1,2,\dots ,2n$ waarin voor elke $i=1,2,\dots ,2n-1$ geldt:

• als $p_i>p_{i+1}$, dan zijn $p_i$ en $p_{i+1}$ beide even.

Voorbeeld: van al de permutaties van vier elementen 1,2,3,4 zijn dit de enige permutaties die hieraan voldoen:

• 1,2,3,4
• 1,3,4,2
• 1,4,2,3

Dergelijke permutaties moeten altijd beginnen met 1. Burstein et al. bewezen dat er een bijectie kan gemaakt worden tussen de verzameling van deze permutaties en die van de Dumontpermutaties van de eerste soort. Hun aantal is dus ook gegeven door de Genocchigetallen en ze noemden deze permutaties daarom de Dumontpermutaties van de derde soort.

Verder definieerden ze ook Dumontpermutaties van de vierde soort. Een permutatie $P=p_1,p_2,\dots ,p_n$ van $1,2,\dots ,2n$ is een Dumontpermutatie van de vierde soort als voor elke $i=1,2,\dots ,2n$ geldt:

• $p_i<i⟺p_i$ en $i$ zijn beide even.

Met andere woorden: een getal in een dergelijke permutatie kan enkel kleiner zijn dan zijn volgnummer in de permutatie als zowel het getal als het volgnummer even zijn.

Voorbeeld: van al de permutaties van vier elementen 1,2,3,4 zijn dit de enige permutaties die hieraan voldoen:

• 1,2,3,4
• 1,4,3,2
• 1,3,4,2

Ook hier geldt dat deze permutaties steeds met een 1 moeten beginnen. Tussen de Dumontpermutaties van de derde soort en die van de vierde soort is ook een bijectie mogelijk zodat het aantal Dumontpermutaties van de vierde soort eveneens door de Genocchigetallen is bepaald.

Externe links

• Sergey Kitaev: "Patterns in permutations and words." Springer-Verlag, 2011., blz. 274. ISBN 9783642173332
• The (Combinatorial) Object Server genereert allerlei permutaties, waaronder Dumontpermutaties