Dearrangiamenti pari e dispari

[Martino]

Un "dearrangiamento" di \( \displaystyle n \) oggetti è una permutazione \( \displaystyle \sigma \in S_n \) con la proprietà che \( \displaystyle \sigma(x) \neq x \) per ogni \( \displaystyle x \in \{1, \ldots, n\} \) .

Sia \( \displaystyle D(n) \) il numero di dearrangiamenti di \( \displaystyle S_n \) (a volte indicato anche con \( \displaystyle !n \) ). Si riesce a dimostrare che \( \displaystyle D(n) = n! \sum_{k=0}^n \frac{(-1)^k}{k!} \) (in particolare, la proporzione dei dearrangiamenti in \( \displaystyle S_n \) - cioè la probabilità che nel restituire a caso gli esami agli studenti nessuno riceva il suo - tende a \( \displaystyle 1/e \) quando \( \displaystyle n \to \infty \) ), e altre strane cose (cfr. qui).

Ogni permutazione è pari oppure dispari. Sia \( \displaystyle E(n) \) il numero di dearrangiamenti pari di \( \displaystyle S_n \) ("E" sta per "even", pari), e sia \( \displaystyle O(n) \) il numero di dearrangiamenti dispari di \( \displaystyle S_n \) ("O" sta per "odd", dispari). Naturalmente \( \displaystyle E(n)+O(n)=D(n) \) .

Dimostrare che \( \displaystyle E(n)-O(n) = (-1)^{n-1}(n-1) \) .

La fonte potrei darla subito ma include la soluzione, quindi la darò tra qualche giorno. Tale soluzione è comprensibile per chiunque abbia fatto il primo anno di università, ma non così facile da immaginare

[Pappappero]

Non è la soluzione completa, ma vorrei capire se sono sulla strada giusta perché c'è qualcosa che non mi torna...

Testo nascosto, fai click qui per vederlo

Penserei di farlo per induzione:

In $S_2$ c'è un solo elemento non banale, che è proprio un dearrangiamento dispari, e quindi la tesi vale.

Supponiamo quindi che $E(n-1)-O(n-1) = (-1)^{n-2} (n-2)$.

Sia $\sigma$ un dearrangiamento pari di $S_{n-1}$. Per ogni $i=1 ... n-1$, $(i,n)\sigma$ è un dearrangiamento dispari di $S_n$. Analogamente i dearrangiamenti dispari di $S_{n-1}$ diventano pari di $S_n$. Mostriamo che tutti i dearrangiamenti così ottenuti sono distinti:

siano $\sigma$ e $\tau$ due dearrangiamenti di $S_{n-1}$ e $i,j$ due interi in $\{ 1 ... n-1 \}$ tali che $(n,i)\sigma = (n,j)\tau$. Certamente $i=j$ perché $n$ non compare nelle permutazioni di $S_{n-1}$. Da questo si ha immediatamente che $\sigma=\tau$.

Perciò da ogni dearrangiamento di $S_{n-1}$ otteniamo $n-1$ dearrangiamenti di $S_n$, di segno opposto a quelli di $S_{n-1}$.

Ora bisogna far vedere che in questo modo li prendiamo tutti. Sia $\eta$ un dearrangiamento di $S_n$ e sia $j = (n)\eta$. Definiamo $\sigma =(n,j)\eta$. $\sigma$ fissa $n$ e perciò è una permutazione di $S_{n-1}$. Se mostriamo che $\sigma$ è un dearrangiamento basta fare i conti e dovremmo aver vinto.

Però così a occhio questo non è vero. Infatti:
$(4,5)(1,2,3)$ è un dearrangiamento di $S_5$, ma $(1,2,3)$ non è un dearrangiamento di $S_4$. Però il ragionamento fatto fino a ora mi sembrava filasse e invece a quanto pare c'è qualcosa che non va perché se fosse giusto mi verrebbero più dearrangiamenti di quelli che ci sono in realtà...

Edit:
mmm...credo di aver capito il problema del mio ragionamento...domani ci ripenso con più calma...

[Martino]

La fonte è questa (la dimostrazione a cui mi riferivo è la "proof 1").