On a question about pattern avoidance of cyclic permutations

Este artículo resuelve el caso abierto sobre la evitación de patrones en permutaciones cíclicas para $\tau=1432$ al derivar fórmulas explícitas mediante el análisis de la estructura de las formas cíclicas y la aplicación del teorema de Dilworth.

Lo esencial

¡Hola! Imagina que las matemáticas de este artículo son como un juego de organizar una fiesta muy estricta donde los invitados son números del 1 al n.

Los autores de este papel (Zuo-Ru Zhang y Hongkuan Zhao) están resolviendo un misterio que otros matemáticos habían dejado sin terminar. Vamos a desglosarlo con analogías sencillas.

1. Los Invitados y las Dos Reglas de la Fiesta

Imagina que tienes una lista de invitados (una permutación). Tienes que organizarlos de dos maneras diferentes, y en ambas formas, deben cumplir reglas estrictas para no ser expulsados de la fiesta.

• La Regla de la "Lista de Asistencia" (Notación de una línea):
  Imagina que los invitados entran a la sala en fila. La regla es que no pueden formarse grupos de k personas que bajen de altura como una escalera.

  • Si k=3, no pueden haber 3 personas altas, seguidas de una mediana, seguidas de una baja (ej: 5, 3, 1).
  • Si k=4, no pueden haber 4 personas bajando en orden (ej: 8, 6, 4, 2).
  • Si k es muy grande (5 o más), la regla se vuelve tan fácil de cumplir que casi todos los invitados la pasan.

• La Regla del "Círculo de Danza" (Forma de ciclo):
  Ahora, imagina que los invitados se toman de las manos formando un círculo gigante. Puedes empezar a contar desde cualquier persona, pero el círculo es el mismo.
  La regla aquí es: En ningún momento del círculo, si miras a 4 personas en orden, deben formar un patrón específico y desordenado llamado "1432".

  • El patrón "1432" es como si vieras a alguien pequeño, luego a un gigante, luego a alguien mediano y luego a otro mediano-bajo, en ese orden específico. ¡Está prohibido!

El Problema:
Antes de este artículo, los matemáticos ya habían resuelto qué pasaba si el patrón prohibido en el círculo era "1324" o "1342". Pero el caso del patrón "1432" era un misterio sin resolver. Nadie sabía cuántas formas había de organizar la fiesta para que cumpliera ambas reglas a la vez.

2. La Solución: El Detective y el Teorema de Dilworth

Los autores actúan como detectives que descubren un secreto oculto en la estructura del círculo.

• El Secreto (Proposición 2.1): Descubrieron que para que el círculo nunca tenga el patrón prohibido "1432", el círculo debe evitar dos cosas más simples:

  1. No puede tener una "escalera de bajada" de 3 personas (321).
  2. No puede tener un patrón específico de 4 personas (2143).
     Analogía: Es como decir: "Para que no haya un robo en la casa (1432), la puerta principal no puede estar abierta (321) y la ventana no puede estar rota (2143)". Si evitas esas dos cosas, el robo es imposible.

• La Herramienta Mágica (Teorema de Dilworth):
  Para la regla de la "Lista de Asistencia" (evitar la escalera de bajada), usan una herramienta matemática llamada el Teorema de Dilworth.

  • Analogía: Imagina que quieres evitar que haya una fila de 3 personas bajando de altura. El teorema te dice que si puedes dividir a todos los invitados en 2 grupos donde, dentro de cada grupo, todos están ordenados de menor a mayor (como escaleras subiendo), entonces es imposible que encuentres una fila de 3 bajando.
  • Los autores usan esto para contar cuántas formas hay de organizar a los invitados sin romper la regla de la escalera.

3. Los Resultados: Las Fórmulas Mágicas

Después de mucho análisis y contando caso por caso (dependiendo de quién es el segundo invitado en entrar al círculo), llegaron a la respuesta final. Ahora tienen una "receta" exacta para saber cuántas fiestas válidas existen para cualquier número de invitados (n), siempre que n sea al menos 5.

Aquí están las tres recetas que encontraron, dependiendo de qué tan estricta sea la regla de la "Lista de Asistencia" (el valor de k):

1. Si la regla es evitar escaleras de 3 (k=3):
   La cantidad de fiestas válidas es una fórmula un poco cuadrática. Es como decir: "Hay muchas formas, pero crecen un poco lento".
   (Fórmula: $\lfloor \frac{n^2+7}{2} \rfloor - 2n$)

2. Si la regla es evitar escaleras de 4 (k=4):
   Aquí la cantidad crece más rápido, como una potencia de 2 (duplicándose casi cada vez que añades un invitado), pero restándole algunas opciones que no funcionan.
   (Fórmula: $2^{n-1} - \lfloor \frac{3n-5}{2} \rfloor$)

3. Si la regla es evitar escaleras de 5 o más (k $\ge$ 5):
   ¡Aquí viene lo interesante! Descubrieron que si la regla de la lista es tan fácil (evitar 5 o más bajando), casi todos los círculos que cumplen la regla del círculo (evitar 1432) automáticamente cumplen la regla de la lista.
   La fórmula es: Total de círculos válidos menos algunos casos especiales.
   (Fórmula: $2^n + 1 - 2n - \binom{n}{3}$)

En Resumen

Este artículo es como cerrar un capítulo de un libro de misterio matemático.

• El misterio: ¿Cuántas formas hay de organizar un círculo de números que no formen el patrón "1432" y tampoco formen una escalera de bajada larga?
• La herramienta: Usaron lógica de "estructura de círculos" y un teorema sobre "dividir grupos" (Dilworth) para simplificar el problema.
• El final: ¡Lo resolvieron! Ahora tenemos fórmulas exactas para calcular la respuesta para cualquier número grande de invitados.

Es un trabajo elegante que toma un problema complejo de "patrones ocultos" y lo convierte en una receta de cocina matemática que cualquiera puede seguir (si tiene las fórmulas a mano).

Resumen técnico

Resumen Técnico del Artículo: "Pattern avoidance of cyclic permutations"

Autores: Zuo-Ru Zhang y Hongkuan Zhao (Universidad Normal de Hebei, China).
Tema: Combinatoria de permutaciones, específicamente la evitación de patrones en permutaciones cíclicas.

1. Planteamiento del Problema

El artículo aborda un problema abierto planteado recientemente por Archer et al. en el contexto de las permutaciones cíclicas bajo restricciones simultáneas de patrones. El problema se centra en contar el número de permutaciones cíclicas $\pi \in S_n$ que satisfacen dos condiciones:

1. Restricción en notación de una línea: La permutación evita el patrón decreciente $\delta_k = k(k-1)\cdots 21$.
2. Restricción en forma de ciclo: Todas las formas cíclicas (todas las rotaciones cíclicas de la forma de ciclo estándar $C(\pi)$) evitan un patrón $\tau$ de longitud 4.

Archer et al. habían resuelto los casos para $\tau = 1324$ y $\tau = 1342$, pero dejaron abierto el caso para $\tau = 1432$. El objetivo de este trabajo es proporcionar una solución cerrada (fórmulas explícitas) para este caso pendiente.

2. Metodología

Los autores emplean una combinación de análisis estructural de las formas de ciclo, teoría de orden parcial y teoremas clásicos de combinatoria:

• Análisis de la Forma de Ciclo Estándar: Utilizan la representación única de una permutación cíclica que comienza con el elemento 1, denotada como $C(\pi) = (1, c_2, \dots, c_n)$.
• Caracterización de la Evitación de 1432: Demuestran (Proposición 2.1) que todas las rotaciones cíclicas evitan el patrón 1432 si y solo si la forma de ciclo estándar $C(\pi)$ evita simultáneamente los patrones 321 y 2143. Esto reduce el problema de evitar 1432 en todas las rotaciones a evitar dos patrones específicos en una sola estructura fija.
• Teorema de Dilworth: Para manejar la restricción de evitación del patrón decreciente $\delta_k$ en la notación de una línea, los autores utilizan el Teorema de Dilworth. Este teorema establece que en un conjunto parcialmente ordenado (poset), el tamaño máximo de una antichain (conjunto de elementos incomparables) es igual al número mínimo de cadenas necesarias para cubrir el conjunto.
  • En este contexto, una antichain de tamaño $k$ en el poset asociado a la permutación corresponde a una subsecuencia decreciente de longitud $k$ en la notación de una línea.
  • Por lo tanto, si el poset puede ser cubierto por $k-1$ cadenas, la permutación evita $\delta_k$.
• Descomposición por Casos: Descomponen el conjunto de permutaciones según el valor del segundo elemento en la forma de ciclo estándar ($j = c_2$), estableciendo recurrencias y bijecciones para contar los casos válidos.

3. Contribuciones Clave y Resultados Principales

El artículo deriva fórmulas explícitas para $a^\circ_n(\delta_k; 1432)$, que representa el número de permutaciones cíclicas de longitud $n$ que evitan $\delta_k$ en notación de una línea y 1432 en todas sus formas de ciclo. Los resultados se dividen según el valor de $k$:

Caso $k=3$ (Evitación de $\delta_3 = 321$)

Para $n \ge 5$, el número de tales permutaciones es:
$$a^\circ_n(\delta_3; 1432) = \left\lfloor \frac{n^2 + 7}{2} \right\rfloor - 2n$$
Este resultado corresponde a la secuencia OEIS A061925. La demostración implica un análisis detallado de la posición del elemento 2 y la estructura de las cadenas en el poset asociado.

Caso $k=4$ (Evitación de $\delta_4 = 4321$)

Para $n \ge 5$, la fórmula es:
$$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \left\lfloor \frac{3n - 5}{2} \right\rfloor$$
La demostración utiliza recurrencias basadas en la inserción del elemento $n$ y el conteo de configuraciones válidas donde las cadenas del poset cubren los elementos sin formar subsecuencias decrecientes de longitud 4.

Caso $k \ge 5$ (Evitación de $\delta_k$ para $k \ge 5$)

Un hallazgo crucial es que para $k \ge 5$, la restricción de evitación de $\delta_k$ en la notación de una línea se vuelve redundante.

• Lema 4.1: Demuestran que si la forma de ciclo estándar evita 321 y 2143, entonces la notación de una línea automáticamente evita $\delta_5$ (y por ende cualquier $\delta_k$ con $k \ge 5$). Esto se prueba utilizando el Teorema de Erdős–Szekeres y un análisis exhaustivo de las permutaciones posibles de longitud 5.
• Resultado: Para $n \ge 5$ y $k \ge 5$:
  $$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$$
  Este resultado coincide con la secuencia OEIS A088921, que cuenta el número total de permutaciones cíclicas cuyas formas de ciclo evitan 321 y 2143, independientemente de la restricción de notación de una línea (ya que esta última está implícitamente satisfecha).

4. Significado e Impacto

• Resolución de un Problema Abierto: El artículo cierra definitivamente la investigación iniciada por Archer et al. sobre la evitación de patrones en permutaciones cíclicas para el caso $\tau = 1432$.
• Conexión Teórica: Establece una conexión profunda entre la evitación de patrones en notación de ciclo y la estructura de orden parcial de la permutación, demostrando cómo el Teorema de Dilworth puede aplicarse eficazmente para contar permutaciones con restricciones de subsecuencias decrecientes.
• Simplificación para $k \ge 5$: El descubrimiento de que la restricción de notación de una línea se vuelve redundante para $k \ge 5$ es un resultado estructural importante que simplifica la clasificación de estos conjuntos de permutaciones, unificando la enumeración con resultados previos sobre permutaciones cíclicas que evitan 321 y 2143.
• Herramientas Combinatorias: Proporciona un marco metodológico (uso de bijecciones, análisis de cadenas en posets y reducción de casos) que puede ser aplicable a otros problemas de evitación de patrones en estructuras cíclicas.

En resumen, el trabajo no solo proporciona las fórmulas de conteo faltantes, sino que también revela propiedades estructurales fundamentales sobre cómo las restricciones de patrones en la forma de ciclo influyen en las propiedades de orden de la permutación completa.