Catégorie : mathématiques

Bonsoir,

Je commence ce blog par un questionnement mathématique.

J’ai eu besoin au cours d’un travail de classer des films (film 1, film 2, film 3 etc.).
Ensuite dans une phase d’apprentissage, l’ordinateur choisissait les films dans un ordre aléatoire. Je n’avais pas beaucoup de films mais j’ai remarqué que souvent l’ordre choisi par l’ordinateur pour les films et mon classement coïncidait pour zéro ou un seul film.

ça m’a amené à me poser la question suivante: si on prend des nombres de 1 à n et qu’on les « mélangent » (ça s’appelle une permutation), quels sont le nombre et la proportion de permutations qui auront 0, 1, 2 ou n points fixes?

Par exemple, si on prend les nombres de 1 à 3,
– il y a une permutation à 3 points fixes (1,2,3) -> (1,2,3), – c’est l’identité.
– il y a 0 permutations à 2 points fixes,
– il y a 3 permutations à 1 point fixe,
(1,2,3)->(1,3,2)
(1,2,3)->(3,2,1)
(1,2,3)->(2,1,3)
– il y a 2 permutations à 0 points fixes – ce sont des « dérangements ».
(1,2,3)->(3,1,2)
(1,2,3)->(2,3,1)

Au total, il y a 1+3+2 = 6 permutations avec 3 nombres.

Je voulais vérifier mathématiquement la propriété intuitive que si on un grand ensemble de nombre de 1 à n (n grand), la configuration la plus probable pour une permutation est qu’il n’y ait pas de point fixe. Une permutation qui n’a pas de point fixe est appelée dérangement.

En fait, la proportion de dérangements parmi toutes les permutations possibles est asymptotiquement (quand n devient grand), de environ 36.8% (1/e où e est le nombre d’Euler). La proportion de permutations avec 1 seul point fixe est asymptotiquement la même.

J’ai mis en pièce jointe un document avec des démonstrations pour calculer le nombre de dérangements par deux méthodes.
Vous trouverez aussi plus d’information et des démonstrations en faisant une recherche sur ce thème dans les forums de http://www.les-mathematiques.net

pièce jointe: invariantsPermutations