Dearrangiamenti pari e dispari

[Studente Anonimo]

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

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

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

Dimostrare che [tex]E(n)-O(n) = (-1)^{n-1}(n-1)[/tex].

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

[Pappappero1]

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

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...

[Studente Anonimo]

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