Outil pour calculer des sous-factorielles. La sous-factorielle !n est le nombre de dérangements, soit le nombre de permutations possibles de n objets distincts de manière à ce qu'aucun objet ne se trouve à sa place originale.
Sous-factorielle - dCode
Catégorie(s) : Arithmétique
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
Sous-factorielle
Réponses aux Questions (FAQ)
Qu'est-ce qu'une sous-factorielle ? (Définition)
La sous-factorielle, notée $ !n $, est une fonction mathématique qui décompte le nombre de dérangements d'un ensemble à $ n $ éléments.
Les dérangements sont les permutations auxquelles sont enlevés les points fixes (qu'aucun élément ne se trouve à sa place originale).
Comment calculer une sous-factorielle ?
La sous-factorielle de $ n $ se calcule par cette formule : $$ !n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $$
Exemple : $$ \begin{align} !4 &= 4! ( \frac{(-1)^0}{0!} + \frac{(-1)^1}{1!} + \frac{(-1)^2}{2!} + \frac{(-1)^3}{3!} + \frac{(-1)^4}{4!} ) \\ &= 4! \times ( 1/1 - 1/1 + 1/2 - 1/6 + 1/24 ) \\ &= 24 \times 9/24 \\ &= 9 \end{align} $$
La sous-factorielle peut etre définie par récurrence : $$ !n = (n−1) (!(n−1)+!(n−2)) $$ ou via une autre relation récurrente équivalente : $$ !n = n \times !(n-1) + (-1)^n $$
Il existe aussi la formule : $$ !n = \left [ \frac {n!}{e} \right ] $$ où les crochets [] signifient un arrondi à l'entier le plus proche.
Exemple : $ 4! / e \approx 24/2.718 \approx 8.829 \Rightarrow !4 = 9 $
Comment calculer les dérangements ?
Le nombre de dérangements pour $ n $ éléments est sous-factorielle de $ n $ : $ !n $.
Exemple : Dans combien de façons peut-on réarranger les chiffres de 1234 sans qu'aucun chiffre ne reste à sa position initiale ? Les $ !4 = 9 $ dérangements de {1,2,3,4} sont {2,1,4,3}, {2,3,4,1}, {2,4,1,3}, {3,1,4,2}, {3,4,1,2}, {3,4,2,1}, {4,1,2,3}, {4,3,1,2}, et {4,3,2,1}.
Quelles sont les premières valeurs de la fonction sous-factorielle ?
Les premières valeurs pour les premiers entiers naturels sont :
| !1 = 0 |
| !2 = 1 |
| !3 = 2 |
| !4 = 9 |
| !5 = 44 |
| !6 = 265 |
| !7 = 1854 |
| !8 = 14833 |
| !9 = 133496 |
| !10 = 1334961 |
Quels sont les exercices types pour la sous-factorielle ?
— Une secrétaire place 100 lettres dans 100 enveloppes de manière totalement aléatoire la probabilité qu'aucune lettre ne soit dans la bonne enveloppe est donnée par : $ \frac{100!}{!100} \approx \frac{1}{e} \approx 0.36788 \approx 36.7\% $
— Un organisateur de banquet assigne $ n $ invités à $ n $ sièges numérotés, mais les invités ignorent leurs places assignées et chacun s'assoit au hasard. Quelle est la probabilité qu'aucun invité ne soit assis à son siège correct ? $ \frac{n!}{!n} \approx \frac{1}{e} \approx 36.7\% $
— $ k $ personnes déposent leurs chapeaux dans une boîte. Ensuite, chaque personne prend un chapeau au hasard. Quelle est la probabilité qu'aucune personne ne récupère son propre chapeau ? $ \frac{k!}{!k} \approx \frac{1}{e} \approx 36.7\% $
Comment écrire une sous-factorielle ?
La sousfactorielle, comme la factorielle, utilise le point d'exclamation comme symboles mais celui-ci est inscrit à gauche du nombre : $ !n $
Parfois la forme $ D_n $ est utilisée dans certaines sources en combinatoire (D pour dérangements).
Quelle est la précédence de l'opérateur sous-factorielle (ordre des opérations) ?
Par convention, les opérateurs suffixés sont prioritaires (le calcul passe en premier) sur les préfixés, ainsi factoriel (suffixé) est prioritaire sur sousfactorielle (préfixé)
Exemple : $ !3! = !(3!) $
Quelle est la relation entre la sous-factorielle et la factorielle ?
La proportion de dérangements parmi toutes les permutations tend vers $ \frac{1}{e} $ lorsque $ n $ devient grand, soit : $$ !n \approx n! \times e \\ n! \approx \frac{!n}{e} $$
Comment programmer la sous-factorielle dans un langage de programmation ?
L'algorithme de la sousfactorielle est donné par le pseudo-code suivant :
function subfactorial(n) {
memo = [1,0]
for (i = 2 .. n) {
memo[i] = (i - 1) * (memo[i - 1] + memo[i - 2])
}
return memo[n]
}
Complexité temporelle et spatiale : $ O(n) $
Si le langage possède déjà la fonction factorielle, alors il peut être plus rapide d'utiliser un autre algorithme.
Exemple : En Python : from math import factorial
def subfactorial(n):
return round(factorial(n) / 2.71828)
Code source
dCode se réserve la propriété du code source pour "Sous-factorielle". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Sous-factorielle", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Sous-factorielle" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Sous-factorielle" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Citation
Le copier-coller de la page "Sous-factorielle" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Sous-factorielle sur dCode.fr [site web en ligne], consulté le 26/03/2025,
- Calcul de Sous-Factorielle !N
- Générateur de Dérangements
- Qu'est-ce qu'une sous-factorielle ? (Définition)
- Comment calculer une sous-factorielle ?
- Comment calculer les dérangements ?
- Quelles sont les premières valeurs de la fonction sous-factorielle ?
- Quels sont les exercices types pour la sous-factorielle ?
- Comment écrire une sous-factorielle ?
- Quelle est la précédence de l'opérateur sous-factorielle (ordre des opérations) ?
- Quelle est la relation entre la sous-factorielle et la factorielle ?
- Comment programmer la sous-factorielle dans un langage de programmation ?
