Dismutazioni!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
nicelbole
Messaggi: 14
Iscritto il: 16 mag 2007, 16:47

Dismutazioni!

Messaggio da nicelbole » 25 ago 2008, 14:42

Una dismutazione $ \sigma $ dell'insieme $ A\equiv\left\{1,2,...,n\right\} $ è una permutazione dell'insieme $ A $ senza punti fissi, ovvero tale che $ \sigma(x)\neq x $, per $ x\in A $.

Detto $ D(n) $ il numero di dismutazioni di un insieme di n elementi, dimostrare che
$ 1. $ $ D(n+1)=n(D(n)+D(n-1)) $
$ 2. $ $ D(n+1)=(n+1)D(n)+(-1)^{n+1} $

Li ho trovati interessanti, anche se alla fine non sono poi molto difficili...

eli9o
Messaggi: 106
Iscritto il: 14 mag 2008, 19:43

Messaggio da eli9o » 27 ago 2008, 00:48

Prima di tutto vediamo quanto vale $ D(n) $:
applicando il principio di inclusione-esclusione possiamo contare le dismutazioni dell'insieme A: l'idea è di sottrarre a tutte le possibili permutazioni quelle che hanno almeno un punto fisso , poi sommarci quelle che hanno almeno 2 punti fissi, sottrarre quelle con almeno 3, ecc.
La formula è $ D(n)= \displaystyle\sum_{k=1}^n \binom{n}{k}(n-k)!(-1)^k= n!\sum_{k=1}^n \frac{1}{k!}(-1)^k $

Parto ora dal punto 2
La quantità $ (n+1)D(n) $ equivale per la nostra formula a $ \displaystyle (n+1)!\sum_{k=1}^n \frac{1}{k!}(-1)^k $
Affinché questa quantità sia pari a $ D(n+1)=\displaystyle (n+1)!\sum_{k=1}^{n+1} \frac{1}{k!}(-1)^k $ manca solamente l'ultimo termine della sommatoria, evidentemente moltiplicato per $ (n+1)! $. Questo vale $ (n+1)! \frac{1}{(n+1)!} (-1)^{n+1}=(-1)^{n+1} $ quindi (mettendo insieme i pezzi buttati lì alla peggio) abbiamo la nostra relazione.

Per quanto riguarda il punto 1 usiamo la relazione 2 sulla tesi e rimane da dimostrare che $ (n+1)D(n)+(-1)^{n+1}=n(D(n)+D(n-1)) $ che equivale a $ D(n)+(-1)^{n+1}=nD(n-1) $. Ora, portando dall'altra parte $ (-1)^{n+1} $ cambiamo il suo segno, il che equivale a cambiare la parità del suo esponente quindi dobbiamo verificare la relazione $ D(n)=nD(n-1)+(-1)^n $ che è proprio la relazione 2 (traslata di 1)

Rispondi