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

Dit artikel bewijst dat het aantal $k$-reguliere woorden over $[n]$ dat bepaalde patronen vermijdt, correspondeert met twee specifieke $k$-ary Fibonacci-achtige recurrenties, en formuleert een conjectuur dat het kwadraat van de Fibonacci-getallen gelijk is aan het aantal woorden dat een verankerd patroon vermijdt.

De kern

Stel je voor dat je een enorme bibliotheek hebt, maar in plaats van boeken, zitten er in de kasten woorden gemaakt van cijfers. Deze woorden hebben een heel speciale regel: elk cijfer van 1 tot $n$ moet precies $k$ keer voorkomen.

Als $k=1$, heb je een gewone rijtje met elk cijfer één keer (een permutatie).
Als $k=2$, heb je twee 1'en, twee 2'en, twee 3'en, enzovoort.
Als $k=3$, heb je drie van elk.

De auteurs van dit paper, Emily, Elizabeth, Cody en Aaron, zijn op zoek gegaan naar een specifiek type "verboden patroon" in deze woorden. Ze wilden weten: Hoeveel woorden zijn er die geen van deze verboden patronen bevatten?

Het antwoord op die vraag leidt tot een van de beroemdste rijen getallen in de wiskunde: de Fibonacci-rij. Maar dan in een heel nieuw, gekleurd jasje.

Hier is de uitleg, vertaald naar alledaagse taal:

1. De Basis: De "Fibonacci-Regel"

De Fibonacci-rij is die bekende rij: 1, 1, 2, 3, 5, 8, 13... waar elk getal de som is van de twee ervoor.
In dit paper kijken ze naar twee varianten van deze rij, waarbij ze een extra knop ($k$) toevoegen:

• Variant A (De "Fibonacci-k" rij): Je telt het vorige getal op bij $k$ keer het getal daarvoor.
  • Voorbeeld: Als $k=2$, krijg je de Jacobsthal-rij (1, 1, 3, 5, 11...).
• Variant B (De "k-Fibonacci" rij): Je telt $k$ keer het vorige getal op bij het getal daarvoor.
  • Voorbeeld: Als $k=2$, krijg je de bekende Pell-rij (1, 1, 3, 7, 17...).

2. De "Verboden Patroon" (De Politie van de Bibliotheek)

Stel je voor dat je woorden bouwt met blokken. Er zijn bepaalde blokkencombinaties die de "politie" (de wiskundige regels) niet toestaat.

• Het eerste experiment: Ze verbieden de patronen 121, 123, 132 en 213.

  • Wat betekent dit? Je mag niet eerst een klein getal, dan een groot, dan weer een klein hebben (121). Je mag ook niet in oplopende volgorde gaan (123).
  • Het resultaat: Als je kijkt naar woorden met $k$ kopieën van elk getal die deze verboden patronen vermijden, blijkt dat het exact het aantal is dat wordt gegeven door Variant A (de Fibonacci-k rij).
  • De analogie: Het is alsof je een toren bouwt met blokken. Als je de regels strikt volgt, blijkt dat het aantal mogelijke torens precies overeenkomt met die speciale getallenrij.

• Het tweede experiment: Ze veranderen de regels. Nu verbieden ze alleen 122 en 213.

  • Wat betekent dit? Je mag niet twee keer hetzelfde getal hebben met daarvoor een kleiner getal (122).
  • Het resultaat: Als je deze nieuwe regels toepast, krijg je precies het aantal woorden dat overeenkomt met Variant B (de k-Fibonacci rij).

3. De "Magische" Combinatie: Fibonacci in het Kwadraat

Het meest spannende deel komt op het einde. De auteurs vragen zich af: "Wat gebeurt er als we de regels nog strenger maken?"

Stel je voor dat je niet alleen verbiedt dat 121 ergens in je woord staat, maar dat je eist dat als 1 en 2 en 1 voorkomen, ze direct achter elkaar moeten staan (als een onlosmakelijk blokje). Dit noemen ze een "vinculair patroon".

• Het resultaat: Als je deze extra strenge regel toepast op de woorden met twee kopieën van elk getal ($k=2$), dan krijg je een nieuwe rij getallen: 1, 1, 4, 9, 25, 64...
  • Dit zijn de kwadraten van de Fibonacci-rij ($1^2, 1^2, 2^2, 3^2, 5^2, 8^2$).
  • De metafoor: Het is alsof je de Fibonacci-rij in een spiegel kijkt en het beeld vermenigvuldigt met zichzelf. De auteurs hebben bewezen dat deze specifieke, strenge blokkenregels precies dit kwadraat-effect produceren.

Waarom is dit belangrijk?

Vroeger dachten wiskundigen dat deze getallenrijen (Fibonacci, Jacobsthal, Pell) vooral in de natuur voorkwamen (zoals de spiralen van een zonnebloem of de schelp van een slak).

Deze paper toont aan dat deze getallenrijen ook diep verborgen zitten in de structuur van woorden en patronen. Het is alsof ze een nieuwe taal hebben ontdekt waarin deze getallenrijen "spreken".

Samengevat in één zin:
De auteurs hebben bewezen dat als je woorden bouwt met specifieke regels over welke cijfers je mag laten staan, het aantal mogelijke woorden precies overeenkomt met bekende getallenrijen uit de wiskunde, en dat je zelfs de beroemde Fibonacci-rij in het kwadraat kunt "ontdekken" door de regels net iets strenger te maken.

Het is een mooie ontdekking dat de wiskunde van getallen en de wiskunde van woorden (patronen) eigenlijk twee kanten van dezelfde medaille zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Pattern Avoidance for Fibonacci Sequences using k-Regular Words" in het Nederlands.

Titel: Patroonvermijding voor Fibonacci-reeksen met behulp van $k$-reguliere woorden

Auteurs: Emily Downing, Elizabeth J. Hartung, Cody Lucido en Aaron Williams.
Publicatie: Discrete Mathematics and Theoretical Computer Science, Vol. 26:1, 2025.

---

1. Probleemstelling

Het artikel onderzoekt de tellende eigenschappen van $k$-reguliere woorden. Een $k$-regulier woord over de verzameling $[n] = \{1, 2, \dots, n\}$ is een string waarin elk symbool precies $k$ keer voorkomt. De auteurs focussen op het tellen van deze woorden die specifieke patroonvermijding (pattern avoidance) eigenschappen bezitten.

Het centrale probleem is het vinden van combinatorische interpretaties voor twee families van veralgemeende Fibonacci-reeksen, gedefinieerd door een tweede parameter $k$:

1. Fibonacci-$k$ getallen ($a_k(n)$): Gedefinieerd door $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$ met basisgevallen $a_k(0)=a_k(1)=1$.
2. $k$-Fibonacci getallen ($b_k(n)$): Gedefinieerd door $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$ met basisgevallen $b_k(0)=b_k(1)=1$.

Voor $k=1$ corresponderen deze met de klassieke Fibonacci-reeks en de Jacobsthal-reeks (voor $k=2$ in de eerste definitie). De auteurs willen bewijzen dat deze reeksen exact het aantal $k$-reguliere woorden tellen dat bepaalde patronen vermijdt.

2. Methodologie

De auteurs gebruiken een combinatorische bewijsvoering gebaseerd op directe constructies en bijecties, in plaats van zware genererende functies of algebraïsche methoden die in eerdere werken (zoals die van Kuba en Panholzer) werden gebruikt.

De kern van de methodologie bestaat uit:

• Definitie van vermijdende klassen: Het definiëren van verzamelingen $Av^k_n(\pi_1, \dots, \pi_m)$ van $k$-reguliere woorden die de patronen $\pi_i$ niet bevatten.
• Recursieve decompositie: Het analyseren van de structuur van deze woorden door te kijken naar de positie van de grootste symbolen ($n$ en $n-1$).
• Lemma's over relatieve volgorde: Het bewijzen van beperkingen over welke symbolen voor welke andere symbolen kunnen voorkomen (bijv. dat het kleinste symbool dat voor $y$ kan komen, $y-1$ moet zijn).
• Standaard-partities: Voor het geval van de "Fibonacci-gewilde kwadraten" (Fibonacci-squared) introduceren ze een concept van "annex" (voorvoegsel) en "basis" (achtervoegsel) om woorden te decomponeren in kleinere, geldige woorden.
• Prefix-bomen: Voor het kwadratische resultaat wordt een specifieke boomstructuur ($T_n$) gebruikt om de mogelijke annexen van de woorden te visualiseren en te tellen.

3. Belangrijkste Bijdragen en Resultaten

Het artikel presenteert drie hoofdstellingen:

Stelling 1: Fibonacci-$k$ woorden

De auteurs geven een eenvoudig en direct bewijs dat het aantal $k$-reguliere woorden over $[n]$ dat de patronen $\{121, 123, 132, 213\}$ vermijdt, gelijk is aan de Fibonacci-$k$ getallen $a_k(n)$.

• Formule: $|Av^k_n(121, 123, 132, 213)| = a_k(n)$ voor alle $k \ge 1$.
• Context: Dit resultaat was eerder bewezen door Kuba en Panholzer (2012) in de bredere context van Stirling-permutaties. De auteurs tonen aan dat hun directe combinatorische benadering eenvoudiger is en de structuur van de strings duidelijker maakt.
• Speciale gevallen: Voor $k=1$ levert dit het klassieke resultaat van Simion en Schmidt op (Fibonacci-reeks). Voor $k=2$ levert dit de Jacobsthal-reeks op.

Stelling 2: $k$-Fibonacci woorden

De auteurs bewijzen een nieuw resultaat voor de tweede familie van reeksen. Het aantal $k$-reguliere woorden over $[n]$ dat de patronen $\{122, 213\}$ vermijdt, is gelijk aan de $k$-Fibonacci getallen $b_k(n)$.

• Formule: $|Av^k_n(122, 213)| = b_k(n)$ voor alle $k \ge 2$.
• Opmerking: Dit resultaat geldt alleen voor $k \ge 2$. Voor $k=1$ corresponderen deze woorden met de Catalan-getallen, die een andere recursie volgen.
• Voorbeeld: Voor $k=2$ (2-reguliere woorden) en de patronen $\{122, 213\}$, is de tellende reeks $1, 1, 3, 7, 17, \dots$(A001333), wat de Pell-achtige$k$-Fibonacci reeks is.

Stelling 3: Fibonacci-gewilde kwadraten (Fibonacci-squared)

De auteurs onderzoeken wat er gebeurt als het patroon $121$in Stelling 1 wordt "vincularized" (d.w.z. de symbolen moeten opeenvolgend zijn). Ze bewijzen dat het aantal$2$-reguliere woorden dat de patronen${121, 123, 132, 213}$vermijdt, waarbij$121$ als een opeenvolgend patroon (consecutive pattern) wordt behandeld, gelijk is aan het kwadraat van de Fibonacci-getallen.

• Formule: $|Av^2_n(121, 123, 132, 213)| = (F_{n+1})^2 = c(n)$.
• Bewijs: Ze gebruiken een nieuwe recursie voor de rij $c(n)$ en een decompositie via een prefix-boom ($T_n$) om te laten zien hoe de woorden kunnen worden opgebouwd uit kleinere blokken.
• Resultaat: De rij is $1, 1, 4, 9, 25, 64, \dots$ (A007598).

4. Significance en Toekomstperspectief

• Vereenvoudiging: De paper biedt een veel toegankelijkere, combinatorische bewijsvoering voor bestaande resultaten (Stelling 1) en vult deze aan met nieuwe inzichten (Stelling 2 en 3).
• Verbinding tussen concepten: Het artikel verbindt succesvol de theorie van patroonvermijding in reguliere woorden met bekende integer-reeksen (Fibonacci, Jacobsthal, Pell, Catalan).
• Uitbreiding van het domein: De auteurs benadrukken dat de meeste eerdere resultaten in dit domein impliciet aannamen dat het patroon $121$werd vermeden (Stirling-permutaties). Door dit te laten vallen, ontdekten ze nieuwe families zoals de$k$-Fibonacci woorden.
• Conjecture: In de conclusie wordt een conjectuur gepresenteerd voor het tellen van $r$-reguliere woorden die de patronen $\{123, 121\}$ of $\{132, 212\}$ vermijden, wat een nieuwe richting aangeeft voor toekomstig onderzoek in patroonvermijding bij multi-patronen.

Samenvattend biedt dit artikel een gestructureerde en elegante combinatorische analyse van hoe $k$-reguliere woorden kunnen worden gebruikt om verschillende generalisaties van de Fibonacci-reeks te tellen, waarbij zowel klassieke patronen als geavanceerde vinculaire patronen worden gebruikt.