On a question about pattern avoidance of cyclic permutations

In diesem Papier wird die von Archer et al. offene Frage zur Mustervermeidung in zyklischen Permutationen für den Fall $\tau=1432$ durch die Herleitung expliziter Formeln mittels einer Strukturanalyse und des Satzes von Dilworth gelöst.

Das Wesentliche

Stellen Sie sich vor, Sie haben einen Kreis aus Freunden, die sich in einer bestimmten Reihenfolge die Hände reichen. In der Mathematik nennen wir das eine zyklische Permutation. Jeder hat eine Nummer von 1 bis n. Wenn Sie diese Handreichung in einer Liste aufschreiben (z. B. wer wem als Erstes die Hand gibt), entsteht eine Zahlenfolge.

Das Ziel dieses Forschungsartikels ist es, herauszufinden, wie viele solche Kreise man bilden kann, ohne dass bestimmte „verbotene Muster" entstehen.

Hier ist die Geschichte des Papers, einfach erklärt:

1. Das Problem: Verbotene Muster

Stellen Sie sich vor, Sie spielen ein Spiel mit Regeln:

• Regel A (Die absteigende Leiter): In Ihrer Liste der Handreichungen darf es keine lange, absteigende Leiter geben. Wenn Sie zum Beispiel 5, 4, 3, 2, 1 hintereinander sehen, ist das verboten. Je länger die Leiter (je größer die Zahl k), desto strenger die Regel.
• Regel B (Der verdrehte Kreis): Wenn Sie den Kreis in alle möglichen Richtungen drehen (jeder Freund könnte theoretisch anfangen, die Hand zu reichen), darf in keiner dieser Drehungen ein bestimmtes Muster auftauchen. Das Muster, das die Forscher hier untersuchen, ist wie eine kleine, verdrehte Schlange: 1-4-3-2.

Die Forscher aus dem Paper (Zhang und Zhao) wollten wissen: Wie viele solcher Kreise gibt es eigentlich, wenn wir diese Regeln einhalten?

2. Der Hintergrund: Ein ungelöstes Rätsel

Ein Team von Wissenschaftlern (Archer et al.) hatte sich bereits mit diesem Spiel beschäftigt. Sie hatten zwei der drei möglichen „Schlangen-Muster" (1324 und 1342) gelöst. Aber das dritte Muster, 1432, war ein hartes Nussknacker-Rätsel geblieben. Niemand wusste, wie man die Anzahl der erlaubten Kreise für dieses spezielle Muster berechnet.

3. Die Lösung: Ein cleverer Trick mit „Ketten"

Die Autoren dieses Papers haben das Rätsel gelöst. Wie haben sie das gemacht? Sie haben eine sehr elegante Brücke zwischen zwei Welten gebaut:

• Die Welt der Kreise (Zyklische Permutationen): Hier schauen sie, wie die Freunde im Kreis stehen.
• Die Welt der Listen (Einzeil-Notation): Hier schauen sie auf die Liste der Handreichungen.

Der Schlüssel-Trick (Dilworths Theorem):
Stellen Sie sich vor, Sie haben einen Haufen Karten. Sie wollen sie in so wenige Stapel wie möglich sortieren, sodass in jedem Stapel die Zahlen von klein nach groß aufsteigen.

• Wenn Sie einen Stapel brauchen, um alle Karten zu sortieren, ist die Liste perfekt geordnet.
• Wenn Sie viele Stapel brauchen, gibt es viele „Abwärts"-Sprünge.

Die Autoren nutzten einen mathematischen Satz (Dilworths Theorem), der besagt: Die Anzahl der Stapel, die Sie brauchen, ist genau so groß wie die längste absteigende Kette, die Sie in der Liste finden können.

Das war der Durchbruch!

• Sie zeigten: Wenn der Kreis bestimmte „schlechte" Muster (wie 321 oder 2143) vermeidet, dann ist die Liste der Handreichungen so gut sortiert, dass man sie in nur wenige Stapel packen kann.
• Das bedeutet automatisch: Es kann keine lange absteigende Leiter (das verbotene Muster δk) geben!

4. Die Ergebnisse: Die Formeln

Nachdem sie die Struktur der erlaubten Kreise verstanden hatten (sie sahen aus wie bestimmte Bauklötze, die man nur in einer Reihenfolge stapeln darf), konnten sie die genaue Anzahl berechnen.

Sie fanden Formeln für drei Fälle:

1. Wenn die absteigende Leiter nur 3 Schritte lang sein darf (δ3):
   Die Anzahl der erlaubten Kreise wächst quadratisch. Es ist wie eine Pyramide aus Steinen.
   Formel: Ca. die Hälfte von n zum Quadrat.

2. Wenn die Leiter 4 Schritte lang sein darf (δ4):
   Hier wird es etwas komplexer, aber die Anzahl wächst exponentiell (wie bei einer sich verdoppelnden Zelle), minus ein paar Ausnahmen.
   Formel: Eine Mischung aus Potenzen von 2 und geraden Zahlen.

3. Wenn die Leiter 5 oder mehr Schritte lang sein darf (δk für k ≥ 5):
   Das ist das Schönste an der Entdeckung: Sobald die Regel „keine 5er-Leiter" gilt, ist sie für diese speziellen Kreise automatisch erfüllt, solange die anderen Regeln eingehalten werden!
   Das bedeutet: Für alle k ab 5 ist die Antwort immer dieselbe. Die Struktur des Kreises ist so streng, dass eine 5er-Leiter gar nicht erst entstehen kann.
   Formel: Eine bekannte Zahlengruppe (OEIS A088921), die sich aus einer einfachen Rechnung ergibt: $2^n + 1 - 2n - \binom{n}{3}$.

Zusammenfassung in einem Bild

Stellen Sie sich vor, Sie bauen Türme aus Spielkarten.

• Die alten Forscher sagten: „Wir wissen, wie viele Türme man bauen kann, wenn man keine 3er-Leiter und keine 4er-Leiter hat."
• Das neue Paper sagt: „Wir haben herausgefunden, wie es mit der 4er-Leiter aussieht, und das Wichtigste: Wenn man keine 5er-Leiter haben will, braucht man sich gar keine Sorgen zu machen! Die Art und Weise, wie die Karten im Kreis angeordnet sein müssen, verhindert die 5er-Leiter von selbst."

Sie haben also nicht nur ein fehlendes Puzzleteil gefunden, sondern auch gezeigt, dass ab einer gewissen Größe die Regeln sich selbst tragen. Das ist ein großer Schritt in der Welt der Kombinatorik!

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers auf Deutsch:

Technische Zusammenfassung: Vermeidung von Mustern in zyklischen Permutationen

Titel des Themas: Bestimmung der Anzahl zyklischer Permutationen, die das absteigende Muster $\delta_k$ in der Einzeilenschreibweise und das Muster $1432$ in allen Zyklusformen vermeiden.

1. Problemstellung und Hintergrund

Das Papier adressiert ein offenes Problem aus der Kombinatorik der Permutationsmuster, das von Archer et al. in früheren Arbeiten aufgeworfen wurde. Es geht um die gleichzeitige Einschränkung zyklischer Permutationen $\pi \in S_n$ unter zwei Bedingungen:

1. Einzeilenschreibweise (One-line notation): Die Permutation muss das absteigende Muster $\delta_k = k(k-1)\dots 21$ vermeiden.
2. Zyklusform (Cycle form): Alle zyklischen Rotationen der Standardzyklusform $C(\pi) = (1, c_2, \dots, c_n)$ müssen ein gegebenes Muster $\tau$ der Länge 4 vermeiden.

Bisher wurden die Fälle $\tau = 1324$ und $\tau = 1342$ gelöst. Der Fall $\tau = 1432$ blieb offen. Das Ziel dieses Papers ist es, diesen letzten Fall für alle $k \ge 3$ und $n \ge 5$ zu lösen und explizite Formeln für die Anzahl $a^\circ_n(\delta_k; 1432)$ herzuleiten.

2. Methodik und theoretischer Rahmen

Die Autoren verwenden eine strukturelle Analyse der Permutationen, kombiniert mit klassischen Ergebnissen der Ordnungstheorie:

• Reduktion auf Standardzyklusformen: Ein zentrales Ergebnis (Proposition 2.1) zeigt, dass alle zyklischen Rotationen von $C(\pi)$ das Muster $1432$vermeiden, wenn und nur wenn die Standardzyklusform$C(\pi)$ selbst die Muster 321 und 2143 vermeidet. Dies reduziert das Problem auf die Analyse von Permutationen, die in ihrer Zyklusdarstellung diese beiden spezifischen Muster vermeiden.
• Dilworths Theorem: Für die Bedingung der Vermeidung von $\delta_k$ in der Einzeilenschreibweise wird Dilworths Theorem angewendet. Dies besagt, dass die maximale Größe einer Antikette in einer partiell geordneten Menge (Poset) gleich der minimalen Anzahl von Ketten ist, die die Menge überdecken.
  • Eine Antikette der Größe $k$ im Poset $S_\pi$ (definiert durch $i \le_\pi j \iff i \le j \land \pi_i \le \pi_j$) entspricht einer absteigenden Teilfolge der Länge $k$.
  • Wenn der Poset durch $k-1$ Ketten überdeckt werden kann, vermeidet $\pi$ das Muster $\delta_k$.
• Strukturelle Charakterisierung: Für den Fall $j=c_2$ (das zweite Element in der Standardzyklusform) werden strenge Bedingungen für die Anordnung der Elemente abgeleitet (Lemma 2.2), um die Vermeidung von 321 und 2143 zu gewährleisten. Dies führt zu spezifischen Mustern in der Zyklusform, die dann auf die Einzeilenschreibweise übertragen werden.
• Rekursive Konstruktionen und Bijektionen: Es werden Bijektionen zwischen Mengen von Permutationen unterschiedlicher Größe $n$ und $n-1$ konstruiert (z. B. durch Entfernen oder Einfügen des Elements $n$ oder $2$), um Rekursionsformeln aufzustellen.

3. Hauptergebnisse (Theoreme)

Die Autoren leiten explizite Formeln für die Anzahl $a^\circ_n(\delta_k; 1432)$ für $n \ge 5$ her, unterteilt nach dem Wert von $k$:

• Fall $k=3$ (Vermeidung von $\delta_3 = 321$):
  Die Anzahl der Permutationen ist gegeben durch:
  $$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
  Dies entspricht der OEIS-Folge A061925.

• Fall $k=4$ (Vermeidung von $\delta_4 = 4321$):
  Die Anzahl ist gegeben durch:
  $$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$

• Fall $k \ge 5$ (Vermeidung von $\delta_k$ für $k \ge 5$):
  Ein entscheidendes Ergebnis (Lemma 4.1) zeigt, dass für $k \ge 5$ die Bedingung der Vermeidung von $\delta_k$ in der Einzeilenschreibweise redundant wird, wenn die Zyklusform 321 und 2143 vermeidet. Die Anzahl ist also identisch mit der Gesamtzahl der zyklischen Permutationen, deren Standardzyklusform 321 und 2143 vermeidet:
  $$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
  Dies entspricht der OEIS-Folge A088921.

4. Signifikanz und Beitrag

• Lösung eines offenen Problems: Das Papier schließt die von Archer et al. gestellte offene Frage für den Fall $\tau = 1432$ vollständig ab.
• Verbindung von Mustervermeidung und Ordnungstheorie: Die Arbeit demonstriert effektiv die Anwendung von Dilworths Theorem zur Analyse von Mustervermeidung in Permutationen, insbesondere im Kontext zyklischer Strukturen.
• Strukturelle Einsichten: Die Herleitung der strukturellen Eigenschaften von Permutationen, die sowohl 321 als auch 2143 in der Zyklusform vermeiden, liefert tiefe Einblicke in die kombinatorische Struktur dieser Mengen.
• Überraschende Redundanz: Der Nachweis, dass für $k \ge 5$ die Einschränkung auf die Einzeilenschreibweise automatisch erfüllt ist, wenn die Zyklusform bestimmte Muster vermeidet, ist ein bemerkenswertes theoretisches Ergebnis, das die Komplexität des Problems für höhere $k$ drastisch reduziert.

Zusammenfassend liefert das Papier eine vollständige Enumeration für eine Klasse von zyklischen Permutationen mit gemischten Mustereinschränkungen und erweitert das Verständnis der Wechselwirkung zwischen Einzeilenschreibweise und Zyklusdarstellung in der Permutationskombinatorik.