Median-Extremes Alternation

Resumen Técnico: Permutaciones de Alternancia Mediana-Extremos (MEA)

1. Planteamiento del Problema

El artículo introduce y estudia una nueva familia determinista de permutaciones, denominadas Permutaciones de Alternancia Mediana-Extremos (MEA). El problema central es analizar la estructura combinatoria de las permutaciones generadas por un proceso de extracción alternado sobre el conjunto ordenado $[n] = \{1, 2, \dots, n\}$.

Aunque la regla de construcción es computacionalmente trivial, el autor postula que las permutaciones resultantes exhiben una estructura combinatoria "rígida" y no trivial, con propiedades estadísticas exactas que no son evidentes a primera vista. El objetivo es formalizar esta construcción y derivar sus primeras propiedades estructurales fundamentales.

2. Metodología y Definición

La construcción del permutación $\pi_n$ sigue un algoritmo iterativo que alterna dos operaciones sobre una lista de valores restantes (inicialmente ordenada):

1. Paso de Mediana: Se elimina el elemento mediano (o los dos centrales si la longitud es par) de la lista actual y se añade a la permutación resultante.
   • Si la longitud es $2k+1$, se toma el elemento único del medio.
   • Si la longitud es $2k$, se toman los dos elementos centrales en orden de izquierda a derecha.
2. Paso de Extremos: Se eliminan el valor mínimo y el valor máximo restantes de la lista y se añaden a la permutación (primero el mínimo, luego el máximo).

El proceso comienza con un paso de mediana y alterna entre pasos de mediana y extremos hasta agotar la lista. La secuencia de valores extraídos forma la permutación $\pi_n$.

Ejemplos iniciales:

• $\pi_1 = [1]$
• $\pi_3 = [2, 1, 3]$
• $\pi_5 = [3, 1, 5, 2, 4]$

3. Contribuciones Clave y Resultados Principales

El artículo establece seis resultados teóricos fundamentales:

A. Descripción Recursiva Exacta (Proposición 3.1)
La estructura de $\pi_n$ se descompone recursivamente basándose en la paridad de $n$. Cada permutación consiste en un prefijo corto dependiente de la paridad, seguido de una copia de una permutación MEA más pequeña ($\pi_{n-2}$ o $\pi_{n-4}$) con un desplazamiento de rango (re-etiquetado).

• Caso impar ($n=2m+1$): $\pi_{2m+1} = [m+1, 1, 2m+1] \parallel T_{2m+1}$, donde $T$ es una versión re-etiquetada de $\pi_{2m-2}$.
• Caso par ($n=2m$): $\pi_{2m} = [m, m+1, 1, 2m] \parallel T_{2m}$, donde $T$ es una versión re-etiquetada de $\pi_{2m-4}$.
  Esta recursividad es el motor de prueba para todos los resultados posteriores.

B. Estructura Alternante (Teorema 4.1)
Se demuestra que toda permutación MEA es una permutación alternante, y su tipo depende exclusivamente de la paridad de $n$:

• Si $n$ es impar, $\pi_n$ es de tipo bajada-subida (down-up): $\pi_n(1) > \pi_n(2) < \pi_n(3) > \dots$
• Si $n$ es par, $\pi_n$ es de tipo subida-bajada (up-down): $\pi_n(1) < \pi_n(2) > \pi_n(3) < \dots$

C. Conjunto de Descensos (Corolario 4.2)
Como consecuencia directa de la estructura alternante, el conjunto de descensos $Des(\pi_n)$ está completamente determinado:

• Si $n$ es impar: $Des(\pi_n) = \{1, 3, 5, \dots, n-2\}$.
• Si $n$ es par: $Des(\pi_n) = \{2, 4, 6, \dots, n-2\}$.

D. Número de Inversiones (Teorema 5.1)
Se deriva una fórmula exacta para el número de inversiones $inv(\pi_n)$, que coincide con la secuencia de "cuartos cuadrados" (OEIS A002620):
$$inv(\pi_n) = \left\lfloor \frac{(n-1)^2}{4} \right\rfloor$$
Esto se descompone en:

• $inv(\pi_{2m+1}) = m^2$
• $inv(\pi_{2m}) = m(m-1)$

E. Signo de la Permutación (Corolario 5.2)
Basado en la fórmula de inversiones, se caracteriza el signo de $\pi_n$:
$$sgn(\pi_n) = (-1)^{\lfloor (n-1)^2/4 \rfloor}$$
El resultado clave es que $\pi_n$ es una permutación impar si y solo si $n \equiv 3 \pmod 4$. En todos los demás casos ($n \equiv 0, 1, 2 \pmod 4$), la permutación es par.

F. Descripción Recursiva de la Inversa (Proposición 6.1)
El artículo proporciona una descripción recursiva exacta para la permutación inversa $\pi_n^{-1}$, invirtiendo los mapas de re-etiquetado utilizados en la construcción directa. Esto permite calcular la posición de cualquier valor $j$ en la permutación inversa sin necesidad de generar toda la secuencia.

4. Significado e Impacto

• Rigidez Estructural: El hallazgo más notable es que una regla de extracción simple y determinista genera una familia de permutaciones con una estructura tan rígida que permite fórmulas cerradas para estadísticas complejas como el número de inversiones y el conjunto de descensos.
• Conexión con Secuencias Conocidas: La conexión con la secuencia de cuartos cuadrados (A002620) sitúa a las permutaciones MEA en un contexto combinatorio conocido, sugiriendo posibles relaciones profundas con otras construcciones de permutaciones alternantes.
• Herramienta para Futuras Investigaciones: El artículo establece una base sólida para preguntas abiertas, como la búsqueda de una fórmula no recursiva directa, el análisis de la estructura de ciclos, el orden bajo iteración y la interpretación de los grafos de inversión asociados.

En conclusión, el trabajo de Carr no solo define una nueva familia de permutaciones, sino que demuestra que poseen propiedades algebraicas y combinatorias elegantes y predecibles, desafiando la intuición inicial sobre la complejidad de los procesos de extracción alternada.