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". Tout algorithme pour "Sous-factorielle", applet ou snippet ou script (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou toutes 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 toute base de données, ou accès API à "Sous-factorielle" ou tout autre élément ne sont pas publics (sauf licence open source explicite type Creative Commons). Idem avec le téléchargement pour un usage hors ligne sur PC, mobile, tablette, appli iPhone ou Android.
Rappel : dCode est une ressource éducative et pédagogique, accessible en ligne gratuitement et pour tous.
Citation
Le contenu de la page "Sous-factorielle" ainsi que ses résultats peuvent être copiés et réutilisés librement, y compris à des fins commerciales, à condition de mentionner dCode.fr comme source.
L'export des résultats est gratuit et se fait simplement en cliquant sur les icônes d'export ⤓ (format .csv ou .txt) ou ⧉ copier-coller.
Pour citer dCode.fr sur un autre site Internet, utiliser le lien :
Dans un article scientifique ou un livre, la citation bibliographique recommandée est : Sous-factorielle sur dCode.fr [site web en ligne], consulté le 16/04/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 ?
