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

Este artigo apresenta uma prova simples de que a recorrência $a_k(n)$ conta as palavras $k$-regulares sobre $[n]$ que evitam os padrões $\{121, 123, 132, 213\}$, complementa o resultado demonstrando que $b_k(n)$ conta as palavras que evitam $\{122, 213\}$, e conjectura que o quadrado do número de Fibonacci corresponde ao conjunto de palavras que evitam os padrões vinculares $\{\underline{121}, 123, 132, 213\}$.

O essencial

Imagine que você tem um conjunto de blocos de construção. Você tem números de 1 até $n$, e a regra do jogo é que cada número deve aparecer exatamente $k$ vezes na sua construção. Se $k=2$, você tem dois "1", dois "2", dois "3", e assim por diante.

Esses são os Palavras k-Regulares (ou "k-regular words"). O objetivo dos autores deste artigo é descobrir quantas maneiras diferentes existem de montar essas torres de blocos, desde que você não crie certos padrões proibidos.

Pense nos "padrões proibidos" como regras de trânsito ou leis da física para seus blocos. Se você montar uma sequência que se parece com um acidente de trânsito (um padrão específico), a construção é demolida e não conta.

Aqui está o resumo da história, traduzido para uma linguagem simples:

1. A Grande Descoberta: Duas Famílias de Sequências

Os autores descobriram que, dependendo de quais "acidentes de trânsito" (padrões) você proíbe, o número de construções possíveis segue duas famílias famosas de números matemáticos: a Sequência de Fibonacci e a Sequência de Jacobsthal.

• A Regra da Família 1 (Fibonacci-k):
  Imagine que você proíbe quatro tipos de acidentes específicos (como "1-2-1", "1-2-3", etc.).

  • Se você fizer isso, o número de torres que consegue construir segue uma fórmula onde o próximo número é o anterior mais $k$ vezes o número de antes do anterior.
  • Analogia: É como se cada nova peça que você adiciona pudesse vir de uma única fonte antiga, ou de $k$ fontes antigas diferentes.
  • Quando $k=1$, isso é a clássica Sequência de Fibonacci (1, 1, 2, 3, 5, 8...).
  • Quando $k=2$, vira a Sequência de Jacobsthal (1, 1, 3, 5, 11, 21...).

• A Regra da Família 2 (k-Fibonacci):
  Agora, imagine que você muda as regras e proíbe apenas dois tipos de acidentes diferentes (como "1-2-2" e "2-1-3").

  • Surpreendentemente, o número de torres agora segue uma fórmula onde o próximo número é $k$ vezes o anterior, mais o número de antes do anterior.
  • Analogia: Aqui, a influência do passado é multiplicada por $k$ antes de somar ao presente.
  • Isso cria uma nova versão da sequência de Fibonacci que depende do valor de $k$.

2. O "Pulo do Gato" (A Prova)

Os autores não apenas adivinharam isso; eles provaram como funciona usando uma técnica de desmontagem.

Imagine que você tem uma torre gigante feita com os números até $n$. Para contar quantas torres existem, eles olham para o topo da torre:

• Cenário A: O topo é feito de todos os $n$'s juntos (ex: ...333). Se você tirar esses 3's, o que sobra é uma torre menor feita com números até $n-1$.
• Cenário B: O topo é uma mistura específica de $n$'s e $(n-1)$'s. Se você tirar essa parte, o que sobra é uma torre ainda menor, feita com números até $n-2$.

Ao mostrar que toda torre válida se encaixa em um desses dois cenários, eles conseguem criar uma fórmula de contagem (uma equação de recorrência) que é exatamente a mesma das sequências de Fibonacci e Jacobsthal. É como dizer: "Para saber quantas torres de 10 andares existem, basta somar as torres de 9 andares com $k$ vezes as torres de 8 andares".

3. O Bônus: O Quadrado da Fibonacci

No final do artigo, eles fazem algo ainda mais legal. Eles pegam a regra da Família 1 e tornam uma das proibições "mais rígida".

• Em vez de apenas proibir o padrão 1-2-1 em qualquer lugar, eles dizem: "O 1-2-1 só é proibido se os blocos estiverem grudados um no outro (consecutivos)".
• Isso muda a contagem de forma mágica: o número de torres válidas agora é exatamente o quadrado do número de torres da sequência de Fibonacci original.
• Analogia: É como se você tivesse duas filas de pessoas (duas sequências de Fibonacci) e estivesse contando quantos pares de pessoas (uma de cada fila) podem se formar sem violar as regras. O resultado é o quadrado do número original.

Por que isso importa?

Este artigo é importante porque:

1. Simplifica o complexo: Eles pegaram um problema matemático difícil que antes exigia cálculos complicados e mostraram uma prova simples e direta, como se estivessem desmontando um brinquedo de Lego.
2. Conecta mundos: Eles mostram que padrões de "evitar certos arranjos" em palavras repetidas estão diretamente ligados às sequências de números mais famosas da matemática.
3. Abre novas portas: Eles sugerem que podemos usar essas regras para criar novas sequências de números e entender melhor como a estrutura de dados (como árvores e grafos) se comporta.

Em resumo: Os autores mostraram que, se você brincar de montar torres com blocos repetidos e seguir regras específicas de "não fazer tal sequência", o número de torres que você consegue fazer não é aleatório; ele segue as regras de ouro da matemática: a Sequência de Fibonacci e suas variantes. E eles fizeram isso de um jeito tão claro que qualquer um pode entender a lógica por trás da contagem.

Resumo técnico

Resumo Técnico: Evitação de Padrões para Sequências de Fibonacci usando Palavras k-Regulares

Autores: Emily Downing, Elizabeth J. Hartung, Cody Lucido e Aaron Williams.
Publicação: Discrete Mathematics and Theoretical Computer Science, Vol. 26:1 (2025).

1. Problema e Contexto

O artigo investiga a enumeração de palavras k-regulares (palavras onde cada símbolo do conjunto $[n] = \{1, 2, \dots, n\}$ aparece exatamente $k$ vezes) que evitam certos padrões de permutação. O objetivo principal é estabelecer conexões diretas entre a evitação de padrões em palavras regulares e famílias de sequências inteiras generalizadas de Fibonacci, especificamente as sequências Fibonacci-k e k-Fibonacci.

Diferentemente de resultados clássicos que frequentemente assumem a evitação do padrão $121$(o que leva a palavras de Stirling), este trabalho explora cenários onde a evitação de$121$ não é imposta ou é modificada, permitindo a descoberta de novas correspondências combinatoriais.

2. Definições Fundamentais

O trabalho define duas famílias de sequências generalizadas:

• Fibonacci-k ($a_k(n)$): Definida pela recorrência $a_k(n) = a_k(n-1) + k \cdot a_k(n-2)$, com $a_k(0) = a_k(1) = 1$.
• k-Fibonacci ($b_k(n)$): Definida pela recorrência $b_k(n) = k \cdot b_k(n-1) + b_k(n-2)$, com $b_k(0) = b_k(1) = 1$.

O conjunto de objetos estudados é $S_n^k$, o conjunto de todas as palavras k-regulars sobre $[n]$. O subconjunto $Av_n^k(\pi_1, \dots, \pi_m)$ contém as palavras que evitam os padrões listados.

3. Metodologia

Os autores utilizam uma abordagem combinatória direta, baseada em bijeções e decomposição recursiva das palavras. A metodologia central envolve:

• Análise de Estrutura: Identificar restrições impostas pelos padrões evitados sobre a posição relativa dos símbolos maiores (especialmente $n$ e $n-1$).
• Lemas de Posicionamento: Provar que, sob certas condições de evitação, o menor símbolo que pode anteceder um símbolo $y$ é estritamente $y-1$.
• Construção Recursiva: Demonstrar que qualquer palavra válida pode ser construída inserindo prefixos específicos (envolvendo $n$ e $n-1$) em palavras válidas de tamanhos menores ($n-1$ ou $n-2$).
• Árvores de Prefixo: Para o caso das sequências quadradas de Fibonacci, os autores definem uma estrutura de árvore específica ("prefix-tree") para mapear as possíveis "anexos" (prefixos) das palavras.

4. Principais Contribuições e Resultados

O artigo apresenta três teoremas principais:

Teorema 1: Enumeração das Palavras Fibonacci-k

• Resultado: O número de palavras k-regulars sobre $[n]$ que evitam o conjunto de padrões $\{121, 123, 132, 213\}$ é dado por $a_k(n)$.
• Contribuição: Embora este resultado fosse conhecido no contexto de permutações de Stirling restritas (prova de Kuba e Panholzer, 2012), os autores fornecem uma prova simples e direta usando decomposição recursiva, sem a necessidade de funções geradoras complexas ou expansões de frações parciais.
• Casos Especiais:
  • $k=1$: Recupera o resultado clássico de Simion e Schmidt sobre permutações evitando $\{123, 132, 213\}$ (número de Fibonacci).
  • $k=2$: Recupera a sequência de Jacobsthal.

Teorema 2: Enumeração das Palavras k-Fibonacci

• Resultado: O número de palavras k-regulars sobre $[n]$ que evitam o conjunto de padrões $\{122, 213\}$ é dado por $b_k(n)$, para $k \ge 2$.
• Contribuição: Este é um resultado novo. Os autores mostram que a evitação de $\{122, 213\}$ (que não evita $121$, permitindo palavras não-Stirling) gera a sequência k-Fibonacci.
• Observação: Para $k=1$, o resultado não se aplica diretamente, pois as palavras 1-regulars evitando $213$são contadas pelos números de Catalan, não por uma recorrência de dois termos simples como a de Fibonacci. A transição ocorre apenas para$k \ge 2$.

Teorema 5: Números Quadrados de Fibonacci e Padrões Vinculares

• Resultado: O número de palavras 2-regulars sobre $[n]$ que evitam $\{121, 123, 132, 213\}$, onde o padrão $121$é tratado como um **padrão vincular completo** (ou seja, os símbolos devem ser consecutivos na palavra), é dado por$c(n) = a_1(n)^2$ (os quadrados dos números de Fibonacci).
• Contribuição: Demonstra que "vincularizar" o padrão de Stirling na sequência de Jacobsthal transforma a contagem na sequência de Fibonacci ao quadrado (OEIS A007598).
• Método: A prova utiliza uma nova recorrência de três termos para a sequência de Fibonacci ao quadrado e uma decomposição baseada em uma "árvore de prefixo" ($T_n$) que codifica os anexos possíveis das palavras.

5. Significância e Impacto

1. Simplificação de Provas Existentes: O trabalho oferece uma prova mais acessível e combinatorial para um resultado conhecido (Teorema 1), tornando a estrutura das palavras evitadoras mais transparente do que as abordagens analíticas anteriores.
2. Novas Conexões Combinatórias: Estabelece uma ligação direta entre a evitação de padrões em palavras regulares (não apenas permutações) e sequências de Fibonacci generalizadas, expandindo o escopo da teoria de evitação de padrões.
3. Generalização de Resultados Clássicos: Mostra como resultados clássicos de Simion-Schmidt (Fibonacci) e Knuth (Catalan) emergem como casos limites ($k=1$) ou variações de suas generalizações k-árias.
4. Exploração de Padrões Não-Clássicos: O Teorema 5 introduz o uso de padrões vinculares (consecutivos) em palavras regulares, abrindo caminho para novas investigações sobre como a restrição de adjacência altera as classes de equivalência de Wilf.
5. Tabela de Resultados: O artigo compila e organiza diversos resultados conhecidos e novos em tabelas (Tabelas 1-5), servindo como um recurso valioso para pesquisadores que estudam a evitação de padrões em palavras regulares e permutações generalizadas.

Em suma, o artigo consolida a teoria de evitação de padrões em palavras k-regulars, fornecendo provas elegantes para generalizações de Fibonacci e descobrindo novas correspondências para sequências como Jacobsthal e Fibonacci ao quadrado.