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...
Dismutazioni!
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)
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)