On a question about pattern avoidance of cyclic permutations

Este artigo resolve a questão em aberto sobre a evitação de padrões em permutações cíclicas, fornecendo fórmulas explícitas para o caso em que o padrão $\tau$ é $1432$, complementando assim os resultados anteriores de Archer et al.

O essencial

Imagine que você tem um grupo de amigos, numerados de 1 a $n$, e você quer organizá-los em uma roda gigante (um ciclo). Todos se dão as mãos e formam um círculo. Como é um círculo, não importa quem começa; se você girar a roda, a ordem relativa das pessoas continua a mesma.

Os matemáticos Zuo-Ru Zhang e Hongkuan Zhao escreveram um artigo para resolver um quebra-cabeça sobre como organizar essas rodas de amigos de forma que nenhuma delas tenha "padrões proibidos".

Aqui está a explicação do que eles fizeram, usando uma linguagem simples e analogias do dia a dia:

1. O Cenário: Duas Regras de Jogo

Para que uma roda de amigos seja considerada "válida" neste estudo, ela precisa obedecer a duas regras estritas:

• Regra 1 (A Lista de Presença): Se você tirar as pessoas da roda e colocá-las em uma fila reta (uma "notação de linha única"), essa fila não pode ter um grupo de amigos descendo uma escada muito longa.
  • Exemplo: Se a regra for "não pode ter 3 pessoas descendo", você não pode ter a sequência 5, 4, 3 na fila.
• Regra 2 (A Roda Giratória): A roda pode girar de qualquer jeito. Em qualquer posição em que a roda pare, você não pode encontrar um padrão específico e complicado chamado 1432.
  • O que é o 1432? Imagine que você olha para quatro pessoas na roda. Se a primeira é pequena, a segunda é a maior de todas, a terceira é a segunda maior e a quarta é a terceira maior (uma subida brusca seguida de uma descida suave), isso é proibido. É como se a roda tivesse um "nó" que não pode ser desfeito.

2. O Problema que Eles Resolveram

Antes deste artigo, outros pesquisadores já tinham resolvido o problema para dois tipos de "nós" proibidos na roda, mas um deles permanecia um mistério: o padrão 1432.

Era como se eles tivessem desvendado dois segredos de um cofre, mas a última fechadura (o 1432) estava travada. O objetivo deste artigo era destravar essa fechadura e contar exatamente quantas rodas válidas existem para qualquer número de amigos ($n$).

3. A Ferramenta Mágica: O Teorema de Dilworth

Para resolver isso, os autores usaram uma ferramenta poderosa da matemática chamada Teorema de Dilworth.

• A Analogia da Escada e da Pilha: Imagine que você tem uma pilha de caixas de tamanhos diferentes. O teorema diz que, se você não consegue encontrar uma pilha de caixas que fiquem uma em cima da outra em ordem decrescente (uma "escada" de tamanho $k$), então você consegue organizar todas as caixas em um número limitado de "prateleiras" (cadeias) onde elas ficam em ordem crescente.
• Na prática: Eles usaram isso para provar que, se a roda não tiver o padrão proibido 1432, ela tem uma estrutura tão organizada que é impossível formar certas "escadas" de descida na lista de presença. Isso simplificou o problema drasticamente.

4. A Descoberta Principal: A Estrutura da Roda

Ao analisar o padrão 1432, eles descobriram uma regra secreta sobre como os amigos devem se sentar na roda para que ela seja válida:

• O amigo número 1 sempre começa a roda.
• O amigo número 2 tem que estar em uma posição específica.
• Os amigos entre o 1 e o 2, e os amigos depois do 2, precisam seguir uma ordem muito rígida (quase como se estivessem em fila indiana, subindo ou descendo de forma controlada).

Essa descoberta transformou um problema caótico em uma fórmula matemática limpa.

5. Os Resultados (As Fórmulas)

Depois de muita dedução, eles chegaram a fórmulas simples que dizem exatamente quantas rodas válidas existem, dependendo de quantos amigos ($n$) você tem e de quão longa é a "escada proibida" na lista de presença ($k$):

• Caso 1 (Escada curta de 3): Se a proibição na fila for apenas 3 pessoas descendo, o número de rodas válidas cresce de forma quadrática (como o número de quadrados em um tabuleiro).
• Caso 2 (Escada de 4): Se a proibição for 4 pessoas descendo, o número de rodas válidas cresce quase exponencialmente (como dobrar a quantidade de vezes), mas com alguns ajustes.
• Caso 3 (Escada longa de 5 ou mais): Aqui está a surpresa! Se você proibir escadas de 5 ou mais pessoas descendo, a regra da lista de presença se torna redundante. Ou seja, se a roda obedecer à regra do "nó 1432", ela automaticamente não terá escadas longas demais. O número de rodas válidas é dado por uma fórmula elegante que envolve potências de 2 e combinações.

Resumo Final

Em termos simples, Zhang e Zhao pegaram um problema de "contar rodas de amigos" que parecia impossível de resolver para um padrão específico (1432). Eles usaram uma lógica de organização (Teorema de Dilworth) para provar que, se a roda estiver bem organizada, ela não pode ter certas desordens na fila.

Com isso, eles conseguiram escrever a "receita exata" (fórmula matemática) para contar quantas dessas rodas perfeitas existem, fechando um capítulo importante na teoria das combinações e padrões. É como se eles tivessem encontrado a chave mestra para abrir a última porta de um labirinto matemático.

Resumo técnico

Resumo Técnico: Evitação de Padrões em Permutações Cíclicas

1. O Problema

O artigo aborda um problema de contagem combinatória no contexto de permutações cíclicas (permutações que consistem em um único ciclo de comprimento $n$). O foco é determinar o número de permutações cíclicas em $S_n$ que satisfazem simultaneamente duas condições de evitação de padrões:

1. Na notação de linha única (one-line notation): A permutação deve evitar o padrão decrescente $\delta_k = k(k-1)\cdots 21$.
2. Em todas as formas de ciclo (cycle forms): Todas as rotações cíclicas da forma padrão do ciclo (que começa com 1) devem evitar um padrão específico $\tau$ de comprimento 4.

O trabalho anterior de Archer et al. resolveu este problema para dois dos três casos possíveis de $\tau$ (simetria e rotação cíclica reduzem as opções a $\tau = 1324$, $\tau = 1342$ e $\tau = 1432$), deixando o caso $\tau = 1432$ como uma questão em aberto. O objetivo deste artigo é resolver especificamente o caso $\tau = 1432$ para qualquer $k \ge 3$.

2. Metodologia

Os autores utilizam uma abordagem estrutural combinatória, combinando análise de formas de ciclo, bijeções e teoremas de teoria da ordem.

• Caracterização Estrutural (Proposição 2.1):
  O ponto de partida crucial é a Proposição 2.1, que estabelece uma equivalência fundamental: Todas as formas de ciclo de uma permutação $\pi$ evitam o padrão 1432 se e somente se a forma de ciclo padrão $C(\pi)$ evita os padrões 321 e 2143.
  Isso transforma o problema de evitar 1432 em todas as rotações para um problema de evitar dois padrões fixos na forma padrão.

• Análise da Estrutura de $C(\pi)$ (Lema 2.2):
  Para permutações onde $C(\pi) = (1, j, c_3, \dots, c_n)$, os autores derivam condições necessárias e suficientes para evitar 321 e 2143. Essas condições impõem restrições rígidas sobre a ordem relativa dos elementos:

  • Os elementos $2, 3, \dots, j-1$ devem aparecer em ordem crescente.
  • Elementos maiores que $j$ entre $j$ e $j-1$ devem estar em ordem crescente.
  • Elementos maiores que $j$ após o elemento 2 devem estar em ordem crescente.

• Aplicação do Teorema de Dilworth:
  Para lidar com a condição de evitação de $\delta_k$ na notação de linha única, os autores modelam a permutação como um conjunto parcialmente ordenado (poset) $S_\pi$.

  • Uma subsequência decrescente de comprimento $k$ corresponde a uma antichain (conjunto antecadeado) de tamanho $k$ no poset.
  • Pelo Teorema de Dilworth, se o poset pode ser coberto por $k-1$ cadeias, então não existem antichains de tamanho $k$, implicando que a permutação evita $\delta_k$.
  • Para $k \ge 5$, eles provam que a restrição de evitar 321 e 2143 na forma de ciclo é suficiente para garantir automaticamente a evitação de $\delta_5$ (e consequentemente de qualquer $\delta_k$ com $k \ge 5$) na notação de linha única, tornando a restrição de linha única redundante para $k \ge 5$.

• Contagem por Casos:
  O artigo divide a contagem com base no valor do segundo elemento da forma de ciclo padrão ($j = c_2$):

  • Caso $j=2$: Estabelece-se uma bijeção com o problema de tamanho $n-1$.
  • Caso $j=3$: Análise detalhada das estruturas possíveis, resultando em fórmulas envolvendo funções de piso e potências de 2.
  • Caso $j \ge 4$: Enumeração baseada nas estruturas restritas derivadas do Lema 2.2, utilizando somatórios e identidades combinatórias.

3. Resultados Principais

Os autores derivam fórmulas explícitas para $a^\circ_n(\delta_k; 1432)$, que denota o número de tais permutações cíclicas, para $n \ge 5$:

• Teorema 1.1 (Caso $k=3$, evitar $\delta_3 = 321$):
  $$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
  Esta sequência corresponde ao OEIS A061925.

• Teorema 1.2 (Caso $k=4$, evitar $\delta_4 = 4321$):
  $$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$

• Teorema 1.3 (Caso $k \ge 5$):
  Para $k \ge 5$, a restrição de linha única torna-se redundante devido à estrutura imposta pela evitação de 321 e 2143. O número de permutações é dado por:
  $$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
  Esta sequência corresponde ao OEIS A088921.

4. Contribuições e Significância

• Resolução de uma Questão Aberta: O trabalho fecha o problema deixado em aberto por Archer et al., completando a classificação de permutações cíclicas que evitam $\delta_k$ e um padrão de comprimento 4.
• Conexão Teórica: O artigo fornece uma ponte elegante entre a evitação de padrões em notação de ciclo e notação de linha única, utilizando o Teorema de Dilworth para conectar a estrutura do ciclo à ausência de subsequências decrescentes longas.
• Fórmulas Exatas: Fornece fórmulas fechadas (não apenas recursivas) para casos que anteriormente eram conjecturais ou desconhecidos, enriquecendo a tabela de sequências OEIS relacionadas a permutações cíclicas.
• Generalização: Demonstra que para padrões decrescentes suficientemente longos ($k \ge 5$), a condição de evitação na notação de linha única é uma consequência direta da estrutura do ciclo, simplificando a análise combinatória para casos futuros.

Em suma, o papel resolve um problema específico de contagem combinatória através de uma análise estrutural profunda, utilizando ferramentas de teoria da ordem para simplificar e unificar a contagem de permutações cíclicas sob múltiplas restrições de padrões.