Pattern Avoidance for Fibonacci Sequences using $k$-Regular Words

Dieser Artikel liefert einen einfachen Beweis dafür, dass die rekursiv definierte Folge $a_k(n)$ die Anzahl der $k$-regulären Wörter über $[n]$ zählt, die bestimmte Muster vermeiden, ergänzt dies durch eine neue Zählung für die Folge $b_k(n)$ und stellt eine Vermutung über die Quadrate der Fibonacci-Zahlen im Kontext von Stirling-Permutationen auf.

Das Wesentliche

Stellen Sie sich vor, Sie haben einen riesigen Baukasten mit bunten Bausteinen. In diesem Papier geht es darum, wie man diese Bausteine zu langen Türmen stapeln kann, ohne dass bestimmte „verbotene Muster" entstehen. Die Autoren, Emily Downing, Elizabeth Hartung, Cody Lucido und Aaron Williams, haben dabei eine spannende Entdeckung gemacht: Sie haben gezeigt, wie man diese Baustein-Türme mit einer berühmten Zahlenreihe, der Fibonacci-Folge, in Verbindung bringen kann.

Hier ist die Geschichte, einfach erklärt:

1. Das Spiel: Bausteine und verbotene Muster

Stellen Sie sich vor, Sie haben Zahlen von 1 bis $n$. Jede Zahl muss genau $k$-mal vorkommen.

• Wenn $k=1$, haben Sie eine normale Permutation (z. B. 1, 2, 3).
• Wenn $k=2$, haben Sie jede Zahl doppelt (z. B. 1, 1, 2, 2, 3, 3). Das nennen die Autoren $k$-reguläre Wörter.

Jetzt kommt die Regel: Sie dürfen bestimmte kleine Muster in Ihrer Reihe nicht haben.

• Ein Muster wie 121 bedeutet: Eine kleine Zahl, dann eine große, dann wieder die kleine (z. B. 1, 5, 1).
• Ein Muster wie 123 bedeutet: Drei Zahlen in aufsteigender Reihenfolge (z. B. 1, 5, 9).

Die Frage ist: Wie viele verschiedene Türme kann ich bauen, ohne diese verbotenen Muster zu erzeugen?

2. Die große Entdeckung: Die Fibonacci-Zauberformel

Die Fibonacci-Zahlen sind eine berühmte Zahlenreihe, bei der jede Zahl die Summe der beiden vorherigen ist (1, 1, 2, 3, 5, 8, 13...).

Die Autoren haben bewiesen, dass es zwei verschiedene Arten gibt, diese Baustein-Türme zu bauen, und beide führen zu neuen, spannenden Versionen der Fibonacci-Zahlen:

Art A: Die „Fibonacci-k"-Türme

Hier verbieten sie vier Muster: 121, 123, 132 und 213.

• Die Analogie: Stellen Sie sich vor, Sie bauen einen Turm. Wenn Sie eine große Zahl setzen, dürfen Sie nicht einfach irgendwas Kleines dahinter setzen, das wieder eine große Zahl „umarmt" (das wäre das 121-Muster).
• Das Ergebnis: Die Anzahl der möglichen Türme folgt einer Regel, die fast wie die normale Fibonacci-Reihe aussieht, aber mit einem kleinen „Multiplikator" $k$.
  • Formel: Neue Zahl = (Alte Zahl) + k × (Noch ältere Zahl).
  • Wenn $k=1$, erhalten wir die klassischen Fibonacci-Zahlen.
  • Wenn $k=2$, erhalten wir die Jacobsthal-Zahlen (eine Art „zweifache" Fibonacci-Reihe).
  • Wenn $k=3, 4, 5...$, erhalten wir immer neue, größere Familien von Zahlen.

Art B: Die „k-Fibonacci"-Türme

Hier verbieten sie nur zwei Muster: 122 und 213.

• Die Analogie: Hier ist die Regel etwas strenger bei der „122"-Form (eine kleine Zahl, dann zwei große gleiche Zahlen).
• Das Ergebnis: Auch hier gibt es eine Formel, aber sie funktioniert anders: Neue Zahl = k × (Alte Zahl) + (Noch ältere Zahl).
  • Das ist wie ein Turm, bei dem Sie bei jedem Schritt $k$-mal so viele Möglichkeiten haben, den nächsten Stein zu setzen, plus die alten Möglichkeiten.
  • Für $k=2$ erhalten wir eine andere bekannte Zahlenreihe (die Pell-Zahlen, aber mit einem kleinen Start-Unterschied).

3. Der besondere Trick: Die „Fibonacci-Quadrat"-Türme

Das dritte und vielleicht coolste Ergebnis betrifft die Fibonacci-Quadrat-Zahlen (1, 1, 4, 9, 25, 64...). Das sind einfach die normalen Fibonacci-Zahlen, die mit sich selbst multipliziert wurden ($1^2, 1^2, 2^2, 3^2, 5^2...$).

Die Autoren haben gezeigt, wie man diese Zahlen mit einem speziellen Baustein-Spiel erhält:

• Sie nehmen die Regeln von Art A (die vier verbotenen Muster).
• Aber sie machen eine kleine Änderung: Das Muster 121 darf nur dann verboten sein, wenn die Zahlen direkt nebeneinander stehen (wie 1-2-1). Wenn dazwischen noch etwas steht, ist es erlaubt.
• Das Ergebnis: Wenn man diese „strengen Nachbarn-Regeln" anwendet, erhält man genau die Fibonacci-Quadrat-Zahlen! Es ist, als würde man die Fibonacci-Reihe in sich selbst spiegeln.

Warum ist das wichtig?

Bisher haben Mathematiker oft nur mit normalen Zahlenreihen (Permutationen) gearbeitet. Diese Autoren zeigen, dass man mit doppelten oder dreifachen Zahlen ($k$-reguläre Wörter) eine ganze Welt neuer Muster und Zahlenreihen erschließen kann.

Zusammenfassend:
Stellen Sie sich vor, die Fibonacci-Zahlen sind ein einfacher Weg durch einen Wald. Diese Forscher haben gezeigt, dass es nicht nur einen Weg gibt, sondern ganze Wälder (für jedes $k$), in denen man sich bewegen kann. Und wenn man die Regeln für das Gehen leicht ändert (indem man auf „direkte Nachbarn" achtet), landet man plötzlich auf einem Pfad, der die Fibonacci-Zahlen in sich selbst verdoppelt (die Quadrate).

Es ist ein Beweis dafür, dass selbst in scheinbar trockenen mathematischen Regeln (wie dem Vermeiden von Zahlenmustern) eine enorme Schönheit und Struktur steckt, die man wie ein Puzzle lösen kann.

Technische Zusammenfassung

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

Titel: Pattern Avoidance for Fibonacci Sequences using k-Regular Words

Autoren: Emily Downing, Elizabeth J. Hartung, Cody Lucido, Aaron Williams
Veröffentlicht in: Discrete Mathematics and Theoretical Computer Science, Vol. 26:1, Permutation Patterns 2023.

---

1. Problemstellung und Motivation

Das Paper untersucht die kombinatorische Enumeration von k-regulären Wörtern (k-regular words) unter der Bedingung der Vermeidung bestimmter Muster (Pattern Avoidance).

• Objekte: Ein k-reguläres Wort über dem Alphabet $[n] = \{1, 2, \dots, n\}$ enthält jedes Symbol genau $k$ Mal. Die Menge aller solchen Wörter wird mit $S_n^k$ bezeichnet.
• Ziel: Die Autoren wollen zeigen, dass bestimmte Teilmengen dieser Wörter, die spezifische Muster vermeiden, durch verallgemeinerte Fibonacci-Folgen gezählt werden.
• Kontext: Während Mustervermeidung in Permutationen (1-reguläre Wörter) gut erforscht ist (z. B. Simion-Schmidt-Ergebnisse), gibt es weniger Ergebnisse für reguläre Wörter, insbesondere wenn man von der Annahme abweicht, dass das Muster $121$ (Stirling-Muster) vermieden wird.

2. Methodik

Die Autoren verwenden eine direkte kombinatorische Beweismethode, die auf rekursiven Zerlegungen und Bijektionen basiert.

• Strukturelle Analyse: Sie analysieren die Positionen der größten Symbole ($n$ und $n-1$) in den Wörtern, um zu bestimmen, wie diese Wörter aus kleineren Wörtern (mit $n-1$ oder $n-2$ Symbolen) aufgebaut werden können.
• Rekursive Konstruktion: Durch die Identifizierung zulässiger Präfixe (Annexe) und der daraus resultierenden Restwörter (Basen) leiten sie Rekursionsformeln her, die den Anzahlen der zulässigen Wörter entsprechen.
• Baum-Strukturen: Für das Ergebnis zu den "Fibonacci-quadrierten" Zahlen wird ein spezieller Präfix-Baum (prefix-tree $T_n$) definiert, dessen Pfade die möglichen Anhängsel (Annexe) kodieren.
• Vinculare Muster: Im letzten Teil wird das Konzept der vincularen Muster (consecutive patterns) eingeführt, bei denen bestimmte Symbole im Muster direkt benachbart sein müssen.

3. Wichtige Beiträge und Ergebnisse

Das Paper liefert drei Hauptergebnisse, die zwei Familien von verallgemeinerten Fibonacci-Zahlen mit Mustervermeidung in k-regulären Wörtern verbinden:

A. Fibonacci-k-Wörter (Theorem 1)

• Definition: Die Menge $Av_n^k(121, 123, 132, 213)$ enthält k-reguläre Wörter, die die Muster $121, 123, 132$und$213$ vermeiden.
• Ergebnis: Die Anzahl dieser Wörter ist gegeben durch die Fibonacci-k-Zahlen $a_k(n)$, definiert durch die Rekursion:
  $$a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$$
  mit den Startwerten $a_k(0) = a_k(1) = 1$.
• Bedeutung: Dies ist ein direkter, einfacher Beweis für ein Ergebnis, das zuvor von Kuba und Panholzer (2012) im Kontext von Stirling-Permutationen bewiesen wurde.
  • Für $k=1$ ergibt sich die klassische Fibonacci-Folge (Simion-Schmidt).
  • Für $k=2$ ergibt sich die Jacobsthal-Folge.

B. k-Fibonacci-Wörter (Theorem 2)

• Definition: Die Menge $Av_n^k(122, 213)$ enthält k-reguläre Wörter, die die Muster $122$und$213$ vermeiden.
• Ergebnis: Für $k \ge 2$ wird die Anzahl dieser Wörter durch die k-Fibonacci-Zahlen $b_k(n)$ gezählt, definiert durch:
  $$b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$$
  mit den Startwerten $b_k(0) = b_k(1) = 1$.
• Neuheit: Dies ist ein neues Ergebnis. Es zeigt, dass die Vermeidung von $122$(ein nicht-Stirling-Muster) in Kombination mit$213$ zu einer anderen Fibonacci-Variante führt.
  • Für $k=2$ ergibt sich die Folge $1, 1, 3, 7, 17, \dots$ (OEIS A001333).

C. Fibonacci-quadrierte Zahlen (Theorem 5)

• Definition: Betrachtet wird die Menge $Av_n^2(121, 123, 132, 213)$, wobei das Muster $121$als **vollständig vincularisiert** (d.h. als konsequentes Muster$121$) behandelt wird. Das bedeutet, die Symbole$1, 2, 1$ müssen direkt nebeneinander stehen.
• Ergebnis: Die Anzahl dieser Wörter entspricht den Fibonacci-quadrierten Zahlen $c(n) = a_1(n)^2$ (OEIS A007598).
• Bedeutung: Das "Vincularisieren" des Stirling-Musters in der Jacobsthal-Resultat (Theorem 1) transformiert die Folge in die Quadrate der Fibonacci-Zahlen. Der Beweis nutzt eine neue Rekursion und die Struktur des Präfix-Baums $T_n$.

4. Technische Details der Beweise

• Beweis für Theorem 1: Zeigt, dass jedes gültige Wort entweder mit $n^k$ beginnt (reduziert auf $n-1$) oder mit einem Präfix der Form $n^b (n-1)^k n^{k-b}$ (reduziert auf $n-2$). Dies führt direkt zur Rekursion $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$.
• Beweis für Theorem 2: Nutzt die Eigenschaft, dass in einem Wort ohne $122$und$213$höchstens eine Kopie eines größeren Symbols$y$rechts von einem kleineren Symbol$x$stehen darf. Dies erzwingt eine spezifische Struktur am Anfang des Wortes, die zu$b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$ führt.
• Beweis für Theorem 5: Zerlegt Wörter in ein "Annex" (Präfix) und eine "Base" (Suffix). Die Annexes entsprechen entweder vier Spezialfällen oder Pfaden in einem definierten Baum. Die Summation über diese Pfade ergibt die Rekursion für die Fibonacci-quadrierten Zahlen.

5. Signifikanz und Ausblick

• Vereinheitlichung: Das Paper verbindet verschiedene bekannte Folgen (Fibonacci, Jacobsthal, Pell, Catalan) mit Mustervermeidung in regulären Wörtern.
• Erweiterung des Feldes: Es demonstriert, dass die Theorie der Mustervermeidung über Permutationen hinaus auf reguläre Wörter (multiset Permutations) erweitert werden kann, auch ohne die Einschränkung auf Stirling-Permutationen.
• Neue Richtungen: Die Autoren schlagen vor, weitere Verallgemeinerungen zu untersuchen, z. B. mit anderen Startwerten $(b_0, b_1)$ oder Kombinationen von Standardmustern und Multi-Mustern (Muster mit wiederholten Symbolen).
• Konjektur: Das Paper stellt eine Konjektur (Conjecture 1) für die Anzahl von $r$-regulären Wörtern auf, die die Muster $\{123, 121\}$ oder $\{132, 212\}$ vermeiden, und liefert eine geschlossene Formel basierend auf Binomialkoeffizienten.

Zusammenfassend liefert das Paper elegante, direkte kombinatorische Beweise für die Zählung von regulären Wörtern unter Mustervermeidung und etabliert neue Verbindungen zwischen der Theorie der Mustervermeidung und verallgemeinerten Fibonacci-Folgen.