Calcolatore di Derangement (Sottofattoriale)

Benvenuti nel Calcolatore di Derangement (Sottofattoriale), uno strumento combinatorio completo che calcola il numero di derangement per qualsiasi insieme di n elementi. Un derangement è una permutazione in cui nessun elemento appare nella sua posizione originale, indicato con !n o D(n). Che tu stia studiando la combinatoria, risolvendo il classico problema del guardaroba o esplorando la teoria della probabilità, questo calcolatore fornisce soluzioni dettagliate passo-passo con visualizzazioni interattive.

Cos'è un Derangement?

Un derangement (chiamato anche disarrangiamento o sottofattoriale) è una permutazione degli elementi di un insieme in cui nessun elemento appare nella sua posizione originale. Il numero di derangement di n elementi si scrive come !n (con il punto esclamativo prima della n) o D(n).

Ad esempio, considera tre elementi nelle posizioni {1, 2, 3}. Ci sono 3! = 6 permutazioni totali, ma solo 2 sono derangement:

• (2, 3, 1) — l'elemento 1 va alla posizione 2, l'elemento 2 va alla posizione 3, l'elemento 3 va alla posizione 1
• (3, 1, 2) — l'elemento 1 va alla posizione 3, l'elemento 2 va alla posizione 1, l'elemento 3 va alla posizione 2

Quindi !3 = 2.

Formule per il Derangement

Formula di Inclusione-Esclusione

La formula più fondamentale deriva dal principio di inclusione-esclusione:

Formula Ricorsiva

I derangement possono anche essere calcolati ricorsivamente:

con i casi base: !0 = 1, !1 = 0.

Formula dell'Intero più Vicino

Per \(n \geq 1\), il sottofattoriale è uguale all'intero più vicino a \(n!/e\):

Il Problema del Guardaroba

L'applicazione più famosa dei derangement è il problema del guardaroba (problème des rencontres): se n ospiti lasciano i propri cappelli e i cappelli vengono restituiti casualmente, qual è la probabilità che nessun ospite riceva il proprio cappello?

La risposta è \(!n / n!\), che converge molto rapidamente a \(1/e \approx 0.3679\). Questo significa che circa il 36,8% di tutte le permutazioni casuali sono derangement, indipendentemente dal numero di elementi.

Come Usare Questo Calcolatore

1. Inserisci n: Inserisci il numero di elementi (da 0 a 170). Usa i pulsanti di esempio rapido per provare valori comuni.
2. Calcola: Fai clic su "Calcola !n" per calcolare il numero di derangement.
3. Controlla i risultati: Visualizza !n, n!, la probabilità di derangement e il rapporto rispetto a 1/e.
4. Esplora l'animazione: Per n piccoli, interagisci con l'animazione visiva per vedere come funzionano i derangement.
5. Studia i passaggi: Esamina il dettaglio dell'inclusione-esclusione e la tabella dei derangement.

Primi 15 Numeri di Derangement

Applicazioni dei Derangement

Secret Santa / Scambio di Regali

Quando si organizza uno scambio di regali Secret Santa, ogni partecipante estrae un nome. Un'estrazione riuscita in cui nessuno pesca il proprio nome è un derangement. Per un gruppo di 10 persone, ci sono 1.334.961 combinazioni valide su 3.628.800 totali.

Crittografia e Teoria dei Codici

I derangement compaiono nell'analisi dei cifrari a sostituzione e dei codici a correzione d'errore. Il concetto di "nessun punto fisso" è fondamentale per comprendere la forza di un cifrario e la crittografia basata su permutazioni.

Mescolamento di Carte e Giochi

Nei giochi di carte, i derangement misurano la probabilità che nessuna carta torni nella sua posizione originale dopo il mescolamento. Questo è utile per analizzare la qualità del mescolamento e l'equità del gioco.

Teoria della Probabilità

I derangement forniscono un elegante esempio del principio di inclusione-esclusione e illustrano come le probabilità possano convergere a limiti semplici (1/e in questo caso).

Proprietà Chiave

• Il rapporto \(!n/n!\) converge a \(1/e \approx 0.367879\) per \(n \to \infty\)
• La convergenza è estremamente rapida — già accurata a 6 decimali per n = 10
• \(!n\) soddisfa la ricorrenza: \(!n = n \cdot !(n-1) + (-1)^n\)
• La funzione generatrice esponenziale è \(e^{-x}/(1-x)\)
• \(!0 = 1\) (la permutazione vuota è vacueramente un derangement)

Domande Frequenti

Cos'è un derangement?

Un derangement è una permutazione di un insieme in cui nessun elemento appare nella sua posizione originale. Ad esempio, se gli elementi sono etichettati {1, 2, 3}, la permutazione (2, 3, 1) è un derangement perché nessun elemento è al suo posto originale. Il numero di derangement di n elementi è indicato con !n (sottofattoriale n).

Qual è la formula per il sottofattoriale !n?

Il sottofattoriale !n può essere calcolato utilizzando la formula di inclusione-esclusione: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Può anche essere calcolato ricorsivamente: \(!n = (n-1)(!(n-1) + !(n-2))\), con !0 = 1 e !1 = 0. Un'altra formula utile è \(!n = \text{round}(n! / e)\) per \(n \geq 1\).

Qual è la probabilità che una permutazione casuale sia un derangement?

La probabilità che una permutazione casuale di n elementi sia un derangement si avvicina a \(1/e \approx 0.3679\) all'aumentare di n. Anche per n piccoli, questa approssimazione è notevolmente accurata. Per n = 5, la probabilità esatta è 44/120 ≈ 0.3667, già molto vicina a 1/e.

Cos'è il problema del guardaroba?

Il problema del guardaroba (noto anche come problème des rencontres) è un classico rompicapo di probabilità: se n persone lasciano i propri cappelli in un ristorante e i cappelli vengono restituiti casualmente, qual è la probabilità che nessuno riabbia il proprio cappello? La risposta è il numero di derangement !n diviso per le permutazioni totali n!, che tende a \(1/e \approx 36.79\%\).

Qual è la relazione tra derangement e fattoriale?

I derangement (!n) e i fattoriali (n!) sono strettamente correlati: \(!n = n! \times \sum(-1)^k/k!\) per k da 0 a n. Il rapporto !n/n! fornisce la probabilità di un derangement, convergendo a 1/e. Inoltre, !n è l'intero più vicino a n!/e per \(n \geq 1\), rendendo n!/e un'approssimazione molto utile.

Risorse Aggiuntive

• Principio di inclusione-esclusione - Wikipedia
• OEIS A000166 - Sequenza Sottofattoriale