Probl`emes de Math´ematiques D´erangements entre ensembles finis ´Enonc´e D´erangements entre ensembles finis Pour tout entier naturel non nul n, on pose En = {1, 2, . . . , n}, et on note Sn l’ensemble des permutations de En, c’est-`a-dire l’ensemble des bijections de En dans lui-mˆeme. Pour tout f de Sn et pour tout k de En, on dit que k est un point fixe de f si f(k) = k. On dit qu’un ´el´ement f de Sn est un d´erangement de En si f ne poss`ede aucun point fixe. On note Dn le nombre de d´erangements de En. Par convention, on pose D0 = 1. On g´en´eralise cette d´efinition en disant qu’une bijection f d’un ensemble A = {a1, a2, . . . , an} sur un ensemble B = {b1, b2, . . . , bn} est un d´erangement de A sur B (ainsi ordonn´es) si pour tout indice i de {1, . . . , n}, on a f(ai) = bj avec j ̸= i. Il est clair qu’il y a alors autant de d´erangements de A sur B qu’il y en a de En dans lui-mˆeme. 1. Que valent D1 et D2 ? [ S ] 2. Montrer que pour tout entier n ≥ 0, on a : Dn+2 = (n + 1)(Dn+1 + Dn). Indication : on cherchera `a former un d´erangement quelconque f de En+2, avec n ≥ 1. Pour cela, on consid`erera k = f(n + 2) et on s’int´eressera `a f(k). [ S ] 3. En d´eduire que pour tout entier naturel n, Dn = n! n� k=0 (−1)k k! . [ S ] 4. Dans cette question, on retrouve le r´esultat de (3) mais par une autre m´ethode. Pour tout entier k ≥ 1, et pour tout q de {0, . . . , k}, on note Dk,q le nombre des permu- tations de Ek qui ont exactement q points fixes. Ainsi Dk,0 = Dk. Par convention on pose encore D0,0 = 1. (a) Montrer que 0 ≤ q ≤ k ≤ n ⇒ C k n C q k = C q n C k−q n−q . [ S ] (b) En d´eduire que, si 0 ≤ q < n, alors n� k=q (−1)kC k n C q k = 0 (et si q = n ?). [ S ] (c) Prouver que pour tout k ≥ 0, on a k! = k� r=0 Dk,r = k� q=0C q k Dq. [ S ] (d) Montrer que pour tout n ≥ 0, Dn = (−1)n n� k=0 (−1)kC k n k! [ S ] (e) Retrouver ainsi le r´esultat de la question 3. [ S ] 5. On consid`ere n boules discernables, plac´ees initialement dans n tiroirs distincts, `a raison d’une boule par tiroir. On sort les n boules, puis on les replace al´eatoirement, toujours `a raison d’une boule par tiroir. On note X la variable al´eatoire discr`ete repr´esentant le nombre de boules ayant retrouv´e leur tiroir d’origine. (a) Montrer que p(X =q) = 1 q! n−q � k=0 (−1)k k! [ S ] (b) Exprimer de mˆeme la probabilit´e de l’´ev´enement X ≥ 1. [ S ] (c) Montrer que l’esp´erance de X est ´egale `a 1. On proposera deux m´ethodes. [ S ] (d) Calculer la variance de X. [ S ] Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.