Median-Extremes Alternation

Titolo: Permutazioni di Alternanza Mediana-Estremi: Risultati Strutturali Iniziali

Autore: David Carr
Data: Marzo 2026
Argomento: Combinatoria, Teoria delle Permutazioni

---

1. Il Problema e la Definizione

Il lavoro introduce una nuova famiglia deterministica di permutazioni, denominata Permutazioni di Alternanza Mediana-Estremi (MEA), generate da un processo di estrazione alternato su un insieme ordinato $[n] = \{1, 2, \dots, n\}$.

Il processo costruttivo è definito come segue:

1. Si parte dalla lista ordinata $(1, 2, \dots, n)$.
2. Si esegue un passo mediano: si rimuovono gli elementi centrali della lista corrente (l'unico elemento centrale se la lunghezza è dispari, i due centrali se la lunghezza è pari) e si aggiungono alla permutazione risultante.
3. Si esegue un passo estremo: si rimuovono il valore minimo e il valore massimo rimanenti nella lista e si aggiungono alla permutazione.
4. Si alternano i passi mediano ed estremo fino a esaurimento della lista.

L'output è una permutazione $\pi_n \in S_n$. Nonostante la regola di costruzione sia computazionalmente semplice, il documento dimostra che le permutazioni risultanti possiedono una struttura combinatoria rigida e inaspettata.

2. Metodologia

L'approccio metodologico si basa su una decomposizione ricorsiva basata sulla parità di $n$. L'autore non si limita a osservare le proprietà empiriche, ma costruisce una prova induttiva rigorosa sfruttando la struttura ricorsiva intrinseca del processo di generazione.

La strategia chiave consiste nel:

• Identificare un prefisso fisso (dipendente dalla parità di $n$) che viene estratto nei primi due passi (mediano ed estremo).
• Dimostrare che il resto della permutazione è isomorfo a una permutazione MEA di ordine inferiore ($\pi_{n-2}$ o $\pi_{n-4}$), soggetta a una specifica ricomposizione dei ranghi (rank-shifting).
• Utilizzare questa struttura ricorsiva per derivare formule esatte per statistiche combinatorie come il numero di inversioni, il set di discese e il segno della permutazione.

3. Contributi Chiave e Risultati Principali

Il documento stabilisce sei risultati fondamentali:

A. Descrizione Ricorsiva Esatta (Proposizione 3.1)

Ogni permutazione $\pi_n$ è composta da un prefisso corto e da una copia di una permutazione MEA più piccola con i ranghi traslati.

• Caso dispari ($n=2m+1$): $\pi_{2m+1} = [m+1, 1, 2m+1] \parallel T_{2m+1}$, dove $T_{2m+1}$ è derivata da $\pi_{2m-2}$.
• Caso pari ($n=2m$): $\pi_{2m} = [m, m+1, 1, 2m] \parallel T_{2m}$, dove $T_{2m}$ è derivata da $\pi_{2m-4}$.

B. Struttura Alternata (Teorema 4.1)

È dimostrato che ogni $\pi_n$ è una permutazione alternata. Il tipo di alternanza è determinato esclusivamente dalla parità di $n$:

• Se $n$ è dispari, $\pi_n$ è di tipo down-up ($\pi(1) > \pi(2) < \pi(3) > \dots$).
• Se $n$ è pari, $\pi_n$ è di tipo up-down ($\pi(1) < \pi(2) > \pi(3) < \dots$).

C. Set di Discese (Corollario 4.2)

Il set di discese ($Des(\pi_n)$) è completamente determinato:

• Per $n$ dispari: $\{1, 3, 5, \dots, n-2\}$.
• Per $n$ pari: $\{2, 4, 6, \dots, n-2\}$.
  La cardinalità del set di discese è $\lfloor \frac{n-1}{2} \rfloor$.

D. Numero di Inversioni e Formula Esatta (Teorema 5.1)

Viene fornita una formula chiusa per il numero di inversioni $inv(\pi_n)$, che corrisponde alla sequenza dei "quarti di quadrato" (OEIS A002620):
$$inv(\pi_n) = \left\lfloor \frac{(n-1)^2}{4} \right\rfloor$$
In forma esplicita per parità:

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

E. Caratterizzazione del Segno (Corollario 5.2)

Il segno della permutazione è dato da $sgn(\pi_n) = (-1)^{inv(\pi_n)}$.
Il documento dimostra che $\pi_n$ è una permutazione dispari (segno $-1$) se e solo se:
$$n \equiv 3 \pmod 4$$
In tutti gli altri casi ($n \equiv 0, 1, 2 \pmod 4$), la permutazione è pari.

F. Descrizione Ricorsiva dell'Inversa (Proposizione 6.1)

L'autore fornisce una descrizione ricorsiva esatta anche per la permutazione inversa $\pi_n^{-1}$, derivata invertendo le mappe di ricomposizione dei ranghi utilizzate nella costruzione diretta.

4. Significato e Implicazioni

• Struttura Rigida: Il risultato principale è che una regola di estrazione apparentemente semplice e deterministica genera una famiglia di permutazioni con proprietà combinatorie estremamente regolari e prevedibili.
• Connessione con Sequenze Note: Il numero di inversioni coincide con la sequenza dei quarti di quadrato, collegando questa nuova costruzione a concetti classici della teoria dei numeri e della combinatoria.
• Nuovo Oggetto di Studio: La famiglia MEA si inserisce naturalmente nel panorama delle permutazioni alternanti, offrendo un nuovo esempio con proprietà esatte note per tutte le statistiche standard.
• Aperture Future: Il documento delinea diverse direzioni per ricerche future, tra cui:
  • Trovare una formula non ricorsiva diretta per $\pi_n$ e $\pi_n^{-1}$.
  • Analizzare la struttura dei cicli e l'ordine di iterazione.
  • Studiare i grafi delle inversioni associati a questa famiglia.

Conclusione

Il lavoro di Carr isola con successo una costruzione deterministica che produce permutazioni alternanti con una struttura ricorsiva precisa. La capacità di derivare formule esatte per il numero di inversioni, il set di discese e il segno, basandosi esclusivamente sulla parità di $n$, rende le permutazioni MEA un oggetto matematico significativo per lo studio combinatorio delle permutazioni alternanti.