Il problema dei cappelli scambiati

Testo

A una cena $5$ invitati lasciano il proprio cappello al guardaroba. All’uscita ciascuno ne riprende uno a caso. In quanti modi può accadere che nessuno riprenda il proprio cappello (un dismovimento, o derangement)?

Soluzione

Cerchiamo il numero $D_{5}$ di permutazioni di $5$ oggetti in cui nessun elemento resta al proprio posto. Vale la formula del principio di inclusione-esclusione: $D_{n} = n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}.$ Per $n=5$: $D_{5} = 5!\left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120}\right) = 120\cdot\frac{44}{120} = \boxed{44}.$

Collegamenti

Argomenti: Combinatoria
Concetti: Permutazioni
Metodi: Principio conteggio
Competenze: Calcolo combinatorio · Ragionare per casi
Tipo di esercizio: Problema combinatorio