Il Teorema di André

Una permutazione alternante dell'insieme $\{1, \ldots, \, n\}$, da non confondersi con una permutazione appartenente al gruppo alterno $\mathsf{A}_n$, è una permutazione $\sigma \in \mathsf{S}_n$ tale che ogni elemento $\sigma(i)$ è alternativamente minore o maggiore del precedente; in altre parole, si ha  $$\sigma(1) < \sigma(2), \quad \sigma(2) > \sigma(3), \quad \sigma(3) < \sigma(4) $$

e così via. Ad esempio, le permutazioni alternanti di $\{1, \, 2, \,  3 \}$ sono $$1, \, 3, \, 2 \quad \quad 2, \, 3, \, 1$$ e quelle di  $\{1, \, 2, \,  3, \, 4 \}$ sono  $$1, \, 3, \, 2, \, 4 \quad \quad 1, \, 4, \, 2, \, 3 \quad \quad 2, \, 3, \, 1, \, 4 \quad \quad 2, \, 4, \, 1, \, 3, \quad \quad 3, \, 4, \, 1, \, 2$$Il numero $A_n$ di permutazioni alternanti di $\{1, \ldots, n\}$ è detto $n$-esimo numero di André , in onore di Désiré André (1840-1917), o anche $n$-esimo numero zig-zag o n-esimo numero up/down. Uno dei risultati più importanti dovuti ad André è la scoperta di una funzione generatrice per tali numeri, ed è noto oggi come 

Teorema di André [A1881]. La somma della serie $$A(x) = \sum_{n=1}^{+ \infty} A_n \frac{x^n}{n!}$$ è data da $$A(x)=\tan\left( \frac{\pi}{4}+\frac{x}{2}\right)=\sec x + \tan x.$$ Dunque il suo raggio di convergenza è $\frac{\pi}{2}$, da cui si ottiene il comportamento asintotico $$A_n \sim 2 \left(\frac{2}{\pi}\right)^{n + 1} \cdot n!\,. $$

I valori di $A_n$ sono tabulati nella successione OEIS A000111, i cui primi elementi sono $$1, \, 1, \, 2, \, 5, \, 16, \, 61, \, 272, \, 1385, \, 7936, \, 50521, \, \dots$$ È bene notare che la definizione di permutazione alternante data in OEIS è lievemente diversa dalla nostra, dato che vengono ammesse anche le permutazioni tali che $$\sigma(1) > \sigma(2), \quad \sigma(2) < \sigma(3), \quad \sigma(3) > \sigma(4) $$ e così via. Con questa definizione, il numero di permutazioni alternanti è $2A_n$, e i corrispondenti valori sono tabulati in OEIS A001250.

I numeri di André hanno numerosi legami con altri famosi numeri usati in Analisi e Combinatoria. Ad esempio, se $B_k$ è il $k$-esimo numero di Bernoulli, vale la relazione $$B_{2n} =(-1)^{n-1}\frac{2n}{4^{2n}-2^{2n}} A_{2n-1}.$$ Il lettore interessato può consultare la relativa voce Wikipedia per ulteriori informazioni e riferimenti bibliografici.

Riferimenti.
[A1881] D. André: Sur les permutations alternées, Journal de Mathématiques Pures et Appliquées 7 (1881), 167-184.