Calculateur de Dérangement (Sous-factorielle)

Bienvenue sur le Calculateur de dérangement (sous-factorielle), un outil de combinatoire complet qui calcule le nombre de dérangements pour n'importe quel ensemble de n éléments. Un dérangement est une permutation où aucun élément n'apparaît à sa position d'origine, notée !n ou D(n). Que vous étudiiez la combinatoire, que vous résolviez le problème classique du vestiaire ou que vous exploriez la théorie des probabilités, ce calculateur fournit des solutions détaillées étape par étape avec des visualisations interactives.

Qu'est-ce qu'un dérangement ?

Un dérangement (également appelé sous-factorielle) est une permutation des éléments d'un ensemble où aucun élément n'apparaît à sa position d'origine. Le nombre de dérangements de n éléments s'écrit !n (avec le point d'exclamation avant le n) ou D(n).

Par exemple, considérons trois objets aux positions {1, 2, 3}. Il existe 3! = 6 permutations au total, mais seulement 2 sont des dérangements :

• (2, 3, 1) — l'objet 1 va à la position 2, l'objet 2 va à la position 3, l'objet 3 va à la position 1
• (3, 1, 2) — l'objet 1 va à la position 3, l'objet 2 va à la position 1, l'objet 3 va à la position 2

Ainsi !3 = 2.

Formules de dérangement

Formule d'inclusion-exclusion

La formule la plus fondamentale dérive du principe d'inclusion-exclusion :

Formule récursive

Les dérangements peuvent également être calculés par récurrence :

avec les cas de base : !0 = 1, !1 = 0.

Formule de l'entier le plus proche

Pour \(n \geq 1\), la sous-factorielle est égale à l'entier le plus proche de \(n!/e\) :

Le problème des rencontres (Hat-Check Problem)

L'application la plus célèbre des dérangements est le problème des rencontres (ou problème du vestiaire) : si n invités déposent leurs chapeaux et que les chapeaux sont rendus au hasard, quelle est la probabilité que personne ne récupère son propre chapeau ?

La réponse est \(!n / n!\), qui converge remarquablement vite vers \(1/e \approx 0,3679\). Cela signifie qu'environ 36,8 % de toutes les permutations aléatoires sont des dérangements, quel que soit le nombre d'objets.

Comment utiliser ce calculateur

1. Entrez n : Saisissez le nombre d'éléments (0 à 170). Utilisez les boutons d'exemples rapides pour essayer des valeurs courantes.
2. Calculer : Cliquez sur "Calculer !n" pour calculer le nombre de dérangements.
3. Consulter les résultats : Voyez !n, n!, la probabilité de dérangement et le ratio par rapport à 1/e.
4. Explorer l'animation : Pour les petites valeurs de n, interagissez avec l'animation visuelle pour voir comment fonctionnent les dérangements.
5. Étudier les étapes : Examinez le détail de l'inclusion-exclusion et le tableau des dérangements.

Les 15 premiers nombres de dérangement

Applications des dérangements

Secret Santa / Échange de cadeaux

Lors de l'organisation d'un échange de cadeaux Secret Santa, chaque participant tire un nom. Un tirage réussi où personne ne tire son propre nom est un dérangement. Pour un groupe de 10 personnes, il existe 1 334 961 arrangements valides sur un total de 3 628 800.

Cryptographie et théorie des codes

Les dérangements apparaissent dans l'analyse des chiffres de substitution et des codes correcteurs d'erreurs. Le concept de "point non fixe" est fondamental pour comprendre la force d'un chiffrement et le cryptage basé sur les permutations.

Mélange de cartes et jeux

Dans les jeux de cartes, les dérangements mesurent la probabilité qu'aucune carte ne revienne à sa position d'origine après le mélange. Ceci est utile pour analyser la qualité du mélange et l'équité du jeu.

Théorie des probabilités

Les dérangements constituent un exemple élégant du principe d'inclusion-exclusion et illustrent comment les probabilités peuvent converger vers des limites simples (1/e dans ce cas).

Propriétés clés

• Le ratio \(!n/n!\) converge vers \(1/e \approx 0,367879\) quand \(n \to \infty\)
• La convergence est extrêmement rapide — déjà précise à 6 décimales pour n = 10
• \(!n\) satisfait la récurrence : \(!n = n \cdot !(n-1) + (-1)^n\)
• La fonction génératrice exponentielle est \(e^{-x}/(1-x)\)
• \(!0 = 1\) (la permutation vide est trivialement un dérangement)

Foire aux questions

Qu'est-ce qu'un dérangement ?

Un dérangement est une permutation d'un ensemble où aucun élément n'apparaît à sa position d'origine. Par exemple, si les objets sont étiquetés {1, 2, 3}, la permutation (2, 3, 1) est un dérangement car aucun objet n'est à sa place initiale. Le nombre de dérangements de n objets est noté !n (sous-factorielle n).

Quelle est la formule de la sous-factorielle !n ?

La sous-factorielle !n peut être calculée à l'aide de la formule d'inclusion-exclusion : \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Elle peut également être calculée par récurrence : \(!n = (n-1)(!(n-1) + !(n-2))\), avec !0 = 1 et !1 = 0. Une autre formule utile est \(!n = \text{round}(n! / e)\) pour \(n \geq 1\).

Quelle est la probabilité qu'une permutation aléatoire soit un dérangement ?

La probabilité qu'une permutation aléatoire de n objets soit un dérangement approche \(1/e \approx 0,3679\) à mesure que n augmente. Même pour de petites valeurs de n, cette approximation est remarquablement précise. Pour n = 5, la probabilité exacte est 44/120 ≈ 0,3667, déjà très proche de 1/e.

Qu'est-ce que le problème des rencontres ?

Le problème des rencontres (également connu sous le nom de problème du vestiaire) est un puzzle de probabilité classique : si n personnes déposent leurs chapeaux dans un restaurant et que les chapeaux sont rendus au hasard, quelle est la probabilité que personne ne récupère son propre chapeau ? La réponse est le nombre de dérangements !n divisé par le total des permutations n!, ce qui approche \(1/e \approx 36,79\%\).

Quelle est la relation entre les dérangements et la factorielle ?

Les dérangements (!n) et les factorielles (n!) sont étroitement liés : \(!n = n! \times \sum(-1)^k/k!\) pour k allant de 0 à n. Le ratio !n/n! donne la probabilité d'un dérangement, convergeant vers 1/e. De plus, !n est l'entier le plus proche de n!/e pour \(n \geq 1\), faisant de n!/e une approximation très utile.

Ressources additionnelles

• Dérangement - Wikipédia
• Principe d'inclusion-exclusion - Wikipédia
• OEIS A000166 - Suite de la sous-factorielle