|
|||||||||||||||||||||||||||||||||||||||
|
Dérangements et sous-factorielles En combinatoire, la notion
de sous-factorielle permet de dénombrer les dérangements: permutations
particulières telles qu'aucun des éléments initiaux ne se retrouve à sa place
initiale. En maths on dit: permutation
sans point fixe.
La quantité
de dérangements est notée D(n) ou a(n) ou encore
!n (sous-factorielle de
n). Cette valeur est intimement liée à la constante e = 2, 718 Exemple de
dérangement: à la sortie d'une réception, aucun des messieurs n'a son chapeau
sur la tête. |
|
|
|
|
Exemple
Définition
pour n > 0, sinon !n = 1 – n (Ex: !0 = 1, !(-1) = 0; !(-2) = -1). La sous-factorielle
de n est égale au produit de la factorielle de n par la somme pour toutes les
valeurs prises par k de 0 à n de (-1) à la puissance k divisée par
factorielle k. Le (-1)k
au numérateur engendre la somme avec les signes alternés. Exemple de calcul de cette somme
Notez que: 0! = 1 et
(-1)0 = 1. De sorte que les deux premiers termes de la parenthèse
s'annulent. Table des premières valeurs
Curiosité 148 349 = !1 + !4 + !8 + !3 +
!4 + !9 Voir DicoNombre 148 349 |
|
Voir Table jusqu'à !200
|
|
||
|
|
Première instruction a
est la sous-factorielle de n Deuxième instruction Calcul
de la séquence des nombres
sous-factorielles de n pour n de 0 à 20). Le point-virgule indique que les
valeurs doivent être affichées. Résultat Toutes
les sous-factorielles des nombres de 0 à 20. Notez la valeur de !0 = 1. |
|
Voir Programmation
|
|
||
|
Relations avec les valeurs précédentes
Surprenant relation avec e
Entier le plus proche (arrondis) de factorielle n sur
e = 2,718… ou partie entière (plancher) de
factorielle n sur 2 plus 1/2. Premier Le seul nombre
premier les sous-factorielles est 2. Rapport limite
|
Exemples avec la première formule
Avec les autres !4 = 3 x (!3 + !2) = 3 x
(2 + 1) = 9 !4 = [4!/e] = [24 /
2,718] = [8,8] = 9 Probabilité d'un dérangement La probabilité
qu'une permutation choisie uniformément
parmi toutes les
permutations soit un
dérangement est
asymptotiquement égale à 1/e. |
|
|
|
||
|
Définition Nombres
de dérangements (anglais:
derangement numbers or Montfort
numbers). Permutation
des éléments d'un ensemble telle qu'aucun élément ne se retrouve dans sa
position initiale. Soit n un
nombre entier naturel non nul et E un ensemble de cardinal n. On appelle
dérangement de E toute permutation de E ne laissant aucun élément de E
invariant. On dit aussi: permutation sans point fixe. Dénombrement (voir tableau) Le
tableau montre les 24 permutations de quatre éléments (24 = 4!). En couleur
ocre les éléments qui occupent la même place qu'au départ. Encadrés en bleu
(lignes sans ocre), les 9 permutations "dérangées"; aucun élément
n'est à la place initiale. Notez
que les nombres en place (points fixes) apparaissent 6 = 3! fois dans chaque
colonne. Exemples d'applications 1. Nombre de manières de placer les lettres dans les
enveloppes de sorte que chaque lettre se trouve dans la mauvaise enveloppe
(adresses toutes différentes). Probabilité = 1/e = 0,367…
2. Deux jeux de cartes mélangés:
probabilité qu'aucune correspondance n'existe, en sortant les cartes deux par
deux = 1/e = 0,367… 3. Cas des chapeaux à la sortie
d'une réception: aucun n'est sur la tête de son propriétaire. 4. Cas des élèves qui notent les autres
sans se noter soi-même. 5. Cas de polyominos de certaines dimensions. Historique Problème étudié en premier par Pierre de Montfort
en 1708 et résolu par lui et, simultanément, par Nicholas Bernoulli en
1713. Euler
(1707-1783) calcule les premiers termes et établit les formules de
récurrences. |
Permutations de quatre éléments
|
|
Voir
Combinatoire - Index
|
|
||
|
De n
= 1 à 3 Cas des enveloppes et des lettres dont
aucun n'est à sa place. Avec deux envois (n = 2), deux possibilités (P = 2) pour
mettre les lettres dans les enveloppes dont une seule de se tromper (D = 1).
La probabilité de se tromper est p = 1/2. Avec n = 3, deux possibilités de se
tromper pour 6 permutations des
lettres dans les enveloppes. La probabilité est p = 2/6 = 1/3. Pour
n = 5 Nous savons que D5 = 44.
Voyons comment le calculer (voir
tableau). Première colonne Pas de 1, bien entendu. Quatre cas possibles: 2, 3, 4 et 5. Autant de possibilités pour chacun
d'eux. D5 = 4 x C Si première colonne = 2 Deux situations à distinguer: les 1 et
2 sont simplement inversés sur leur position, ou pas. Si première colonne = 2 et deuxième = 1 Les trois autres (3, 4 et 5) doivent
être dérangés sur les 3 colonnes (3, 4 et 5). C'est un dérangement d'ordre 3,
et D3 = 2. Si première colonne = 2 et deuxième = (3, 4 ou 5) L'astuce
est de considérer le 1 à placer comme un pseudo-2. En effet, le 1 a déjà été
placé en position 2 et ne doit plus s'y trouver, c'est donc un faux 2,
noté 12 dans le tableau. Alors, les quatre valeurs (12,
3, 4 et 5) doivent être dérangées sur les 4 colonnes (2, 3, 4 et 5). C'est un
dérangement d'ordre 4, et D4 = 9. Total pour colonne = 2, 3,
4 puis 5 C'est quatre fois la valeur trouvée: D5 = 4 x (D3 + D2)
= 4 x (2 + 9) = 44 Généralisation Le même raisonnement peut se tenir non
plus pour n = 5, mais pour n quelconque et l'on obtiendrait: Dn = (n – 1) x (Dn-1 + Dn-2) |
Cas n = 1, 2 et 3 – Exemple des
enveloppes
Cas n = 5 avec le 2 en première
colonne – Tableau et mise en évidence de deux
situations
|
|
|
Écrivons la relation sous une autre
forme qui met en évidence une relation
de récurrence. |
|
|
|
En descendant en valeur de n: |
|
|
|
En revenant aux dérangements. Ou en reprenant la notation des
sous-factorielles. |
|
|
|
|
||
|
Avec
l'exemple de quatre éléments, A1 est le sous-ensemble des
permutations conservant le 1 en sa position; A2 conserve le 2 en
sa position; idem pour A3 et A4. |
Par exemple, les permutations notées d et e appartiennent uniquement au sous-ensemble A1; par contre, la première permutation a appartient aux quatre sous-ensembles. |
|
|
|
||
|
Ensemble
"coloré" = réunion des
quatre sous-ensembles |
Là,
il existe au moins un élément fixe (conservant sa position initiale) |
|
|
Sa
négation (ou toutes les permutations – celles "colorées" = |
Toutes
les permutations sans point fixe. |
|
|
Formulation: la
quantité de dérangements est égale au cardinal de l'ensemble inverse (bar) de l'union de tous les sous-ensembles du type A1,
ceux qui conservent les éléments à leur place. |
Suite du calcul sur Wikiuniversité
>>> |
|
|
|
||
|
Théorème La quantité
de dérangements d'un ensemble comprenant n éléments est: |
|
|
|
Chapeaux Cas de
l'énigme des 10 chapeaux; calcul de la probabilité qu'aucun ne soit remis à
son propriétaire à la sortie de la cérémonie. |
|
|
|
Limite Cas d'un
nombre infini de chapeaux |
|
|
|
|
|
|
Subfactorial or rencontres numbers, or derangements: number of
permutations of n elements with no fixed points. Subfactorial n (!n or a(n))
is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p
(taken to be n if there are no ascents) is even. Source du texte : OEIS A000166 |
|
|
Suite |
|
|
Voir |
|
|
Site |
|
|
Cette page |
