On a question about pattern avoidance of cyclic permutations

In dit artikel wordt een open vraag van Archer et al. over cyclische permutaties die het dalende patroon $\delta_k$ en het patroon $\tau=1432$ vermijden, opgelost door expliciete formules af te leiden via een analyse van cykelstructuren en het toepassen van de stelling van Dilworth.

De kern

Stel je voor dat je een grote groep mensen hebt, elk met een uniek nummer van 1 tot $n$. In de wiskunde noemen we een manier om deze mensen in een rij te zetten een permutatie.

Dit artikel gaat over een heel specifiek soort "rij" en een paar regels die we moeten volgen om te voorkomen dat er bepaalde patronen ontstaan. Het klinkt misschien saai, maar het is eigenlijk een spannend raadsel over hoe je mensen kunt ordenen zonder dat ze in de verkeerde volgorde staan.

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen:

1. De twee soorten rijen

De auteurs kijken naar twee manieren om deze mensen te ordenen:

• De "Eén-lijn" rij: Dit is de gewone manier waarop je mensen op een foto zet. Ze staan in een rechte lijn: persoon 1, persoon 2, persoon 3, enzovoort.
• De "Cirkel" rij: Stel je voor dat deze mensen in een cirkel staan, hand in hand. Omdat het een cirkel is, maakt het niet uit waar je begint; als je de cirkel een beetje draait, is het nog steeds dezelfde groep. Dit noemen ze een cyclische permutatie.

2. Het spel: "Vermijd deze patronen!"

Het doel van het spel is om te voorkomen dat er bepaalde ongewenste patronen in de rijen ontstaan. Het is alsof je een regelaar bent die zegt: "Nee, die drie mensen mogen niet zo staan!"

Er zijn twee soorten verboden patronen:

1. Het dalende patroon ($\delta_k$): Stel je voor dat je een trechter hebt. Als je in de "Eén-lijn" rij kijkt, mogen er niet $k$ mensen achter elkaar staan die steeds kleiner worden (zoals 5, 4, 3, 2, 1). Dat is een "aflopende trap". Het artikel kijkt naar wat er gebeurt als we deze trap verbieden.
2. Het "1432"-patroon in de cirkel: Dit is een ingewikkelder regel. Als je door de cirkel loopt, mag je niet een specifieke volgorde tegenkomen die eruit ziet als een kleine berg die eerst hoog is, dan laag, dan weer hoog, dan weer laag (in wiskundige termen: 1-4-3-2).

3. Het mysterie dat opgelost wordt

Eerder onderzoekers hadden al twee van de drie mogelijke scenario's opgelost. Ze hadden de regels voor de cirkel alvastgelegd, maar er bleef één lastig geval over: het geval waar het verboden patroon in de cirkel "1432" is.

Het was alsof ze een puzzel hadden met drie stukjes, en twee lagen al perfect op hun plek. Het derde stukje (het 1432-stukje) bleef echter een raadsel. De auteurs van dit artikel zeggen: "Wacht even, wij gaan dat laatste stukje nu oplossen!"

4. Hoe lossen ze het op? (De Magische Sleutels)

Om dit raadsel op te lossen, gebruiken de auteurs twee slimme trucs:

• De "Dilworth's Theorema" (De Ladder-truc):
  Stel je voor dat je een berg mensen hebt die in een chaotische rij staan. De wiskundige regel van Dilworth zegt eigenlijk: "Als je niet kunt vinden dat er een lange, aflopende trap is, dan kun je de hele groep wel verdelen in een klein aantal 'stapels' of 'ladders' waar iedereen in omhoog loopt."
  De auteurs gebruiken deze regel om te bewijzen dat als je de "aflopende trap" in de gewone rij verbiedt, de structuur van de cirkel heel strak en voorspelbaar wordt. Het is alsof je een rommelige kamer opruimt door te zeggen: "Alles moet in een van deze drie kasten passen."

• De "Structuur-analyse" (De Bouwplaat):
  Ze kijken heel nauwkeurig naar hoe de mensen in de cirkel (de standaardvorm) moeten staan om het "1432"-patroon te vermijden. Ze ontdekken dat er maar heel weinig manieren zijn om de mensen te plaatsen zonder dat het verboden patroon ontstaat. Het is alsof je een Lego-bouwsel maakt waarbij er maar één specifieke manier is om de blokken te stapelen zonder dat het instort.

5. Het resultaat: De Formule

Na al dit rekenen en redeneren, vinden ze een simpele formule. Dit is als een recept dat je kunt gebruiken om precies te weten hoeveel manieren er zijn om de mensen te ordenen, afhankelijk van hoeveel mensen er zijn ($n$).

• Voor kleine groepen (als je verbiedt dat er 3 mensen aflopen) is er één formule.
• Voor iets grotere groepen (als je verbiedt dat er 4 mensen aflopen) is er een andere formule.
• Voor grote groepen (als je verbiedt dat er 5 of meer mensen aflopen) is er weer een andere, heel elegante formule.

Samenvatting in één zin

De auteurs hebben een langdurig wiskundig raadsel opgelost door te bewijzen dat als je mensen in een cirkel zet en verbiedt dat ze een specifiek "berg-vallei" patroon vormen, er precies een bepaald aantal veilige manieren zijn om ze te ordenen, en ze hebben de exacte formule gevonden om dat aantal te berekenen.

Het is een mooi voorbeeld van hoe wiskundigen, door slimme regels en logische trucs, chaos in een geordend systeem kunnen omzetten.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "On a question about pattern avoidance of cyclic permutations" van Zuo-Ru Zhang en Hongkuan Zhao, vertaald en samengevat in het Nederlands.

Titel: Oplossing van een open probleem rondom patroonvermijding in cyclische permutaties

1. Probleemstelling

Het artikel richt zich op het tellen van cyclische permutaties (permutaties die bestaan uit één enkele cyclus) die aan specifieke restricties voldoen. De auteurs bestuderen de verzameling $A^\circ_n(\delta_k; \tau)$, bestaande uit permutaties $\pi \in S_n$ die twee voorwaarden tegelijkertijd moeten voldoen:

1. Eén-lijn notatie: De permutatie vermijdt het dalende patroon $\delta_k = k(k-1)\cdots 21$.
2. Standaard cyclusvorm: Alle cyclische rotaties van de standaard cyclusvorm $C(\pi)$ (die begint met 1) vermijden een gegeven patroon $\tau$ van lengte 4.

Recent werk van Archer et al. had reeds de gevallen $\tau = 1324$ en $\tau = 1342$ opgelost, maar het geval $\tau = 1432$ bleef een open vraag. Het doel van dit artikel is om deze laatste case op te lossen en expliciete formules af te leiden voor het aantal zulke permutaties, aangeduid als $a^\circ_n(\delta_k; 1432)$, voor $k \in \{3, 4\}$ en $k \ge 5$.

2. Methodologie

De auteurs combineren structurele analyse van cyclusvormen met combinatorische stellingen uit de orde-theorie. De kernmethodologie omvat:

• Reductie van Patroonvermijding (Propositie 2.1):
  Een cruciale stap is het bewijzen dat een cyclische permutatie $\pi$ alle rotaties vermijdt van het patroon 1432 dan en slechts dan als de standaard cyclusvorm $C(\pi)$ zowel het patroon 321 als 2143 vermijdt. Dit reduceert het probleem van het controleren van alle rotaties tot het controleren van één specifieke vorm.
• Structuuranalyse (Lemma 2.2):
  Voor permutaties die 321 en 2143 vermijden, leiden de auteurs strikte voorwaarden af voor de volgorde van de elementen in de cyclusvorm. Bijvoorbeeld, als $C(\pi) = (1, j, c_3, \dots)$, dan moeten de elementen $2, 3, \dots, j-1$in oplopende volgorde voorkomen, en moeten elementen groter dan$j$ die tussen specifieke posities voorkomen, ook monotoon zijn.
• Toepassing van Dilworth's Stelling:
  Om de restrictie op de één-lijn notatie (het vermijden van dalende deelrijen van lengte $k$) te analyseren, definiëren de auteurs een partiële orde $S_\pi$ op de indices. Een dalende deelrij van lengte $k$ komt overeen met een antichain van grootte $k$ in deze orde. Volgens Dilworth's stelling vermijdt $\pi$ het patroon $\delta_k$ als de poset $S_\pi$ kan worden overdekt door $k-1$ ketens.
• Bijjecties en Recursie:
  De auteurs construeren expliciete bijjecties tussen verzamelingen van permutaties van grootte $n$ en $n-1$ (bijvoorbeeld door het element 2 of $n$ te verwijderen/Toe te voegen) om recursieve relaties op te stellen.

3. Belangrijkste Resultaten

De auteurs leiden expliciete formules af voor het aantal permutaties $a^\circ_n(\delta_k; 1432)$ voor $n \ge 5$, afhankelijk van de waarde van $k$:

• Geval $k=3$ (Vermijden van $\delta_3 = 321$):
  De formule is:
  $$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
  Dit correspondeert met OEIS-reeks A061925.

• Geval $k=4$ (Vermijden van $\delta_4 = 4321$):
  De formule is:
  $$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$

• Geval $k \ge 5$ (Vermijden van $\delta_k$):
  Het artikel bewijst (Lemma 4.1) dat voor $k \ge 5$ de restrictie op de één-lijn notatie redundant wordt. Als de standaard cyclusvorm 321 en 2143 vermijdt, dan vermijdt de één-lijn notatie automatisch $\delta_5$ (en dus ook elke $\delta_k$ voor $k \ge 5$).
  De telling wordt dus puur bepaald door het aantal cyclische permutaties die 321 en 2143 vermijden in hun cyclusvorm:
  $$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
  Dit correspondeert met OEIS-reeks A088921.

4. Significatie en Bijdrage

• Oplossing van een Open Vraag: Het artikel sluit definitief de door Archer et al. gelaten open vraag over het patroon $\tau = 1432$.
• Unificatie van Methoden: Het werk toont een elegante synthese tussen patroonvermijding in permutaties, de structuur van cyclische rotaties en de toepassing van Dilworth's stelling uit de orde-theorie om restricties op één-lijn notaties te vertalen naar keten-overdekkingen.
• Verwachte Resultaten: De resultaten bevestigen en generaliseren eerdere conjectures en specifieke gevallen bestudeerd door Pan, die reeds connecties hadden gelegd met rijen zoals Pell, Tetranacci en Padovan in gerelateerde contexten.
• Combinatorische Inzicht: De paper biedt een diep inzicht in hoe de interactie tussen de cyclusstructuur en de lineaire notatie beperkingen oplegt aan de mogelijke permutaties, wat leidt tot schone, gesloten formules.

Samenvattend biedt dit artikel een volledige classificatie en telling van cyclische permutaties die het patroon 1432 in alle rotaties vermijden, gecombineerd met vermijding van dalende patronen van lengte $k$, waarbij voor grote $k$ de lineaire restrictie automatisch wordt vervuld door de cyclusrestricties.