Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Licence 2-S3 SI-MASS Année 2013 Cours de Probabilités Pierre DUSART 2 Chapitre1

Licence 2-S3 SI-MASS Année 2013 Cours de Probabilités Pierre DUSART 2 Chapitre1 Éléments d’analyse combinatoire 1.1 Quelques déﬁnitions Disposition sans répétition : c’est une disposition où un élément peut apparaître 0 ou 1 fois. Disposition avec répétition : un élément peut ﬁgurer plus d’une fois. Disposition ordonnée : l’ordre d’obtention d’un élément est important. Ex. les éléments constituant la plaque minéralogique d’un véhicule. Disposition non-ordonnée : l’ordre d’obtention d’un élément n’est pas important, on n’en tient pas compte dans la caractérisation de la disposition. Ex. Les numéros issus d’un tirage du loto. Exemple 1 : On considère un ensemble à deux éléments {a, b}. Avec deux tirages sans répétition, on peut obtenir {a, b} ou {b, a} ; Avec deux tirages avec répétition, on peut obtenir {a, a}, {a, b}, {b, a} ou {b, b}. Cela correspond à un tirage avec remise. Exemple 2 : Prenons un jeu de dé à 6 faces (éléments discernables) numérotées par Ω= {1; 2; 3; 4; 5; 6}. Après 3 jets, nous obtenons la réalisation A = (2; 5; 1) ; nous réitérons les jets et nous obtenons B = (5; 1; 2). A et B sont équivalents si nous considérons que les dispositions sont non-ordonnées. En revanche, ils ne sont pas équivalents si nous sommes dans le cadre d’une disposition ordonnée. La valeur Factorielle(n), notée n! est déﬁnie par n! = 1 · 2 · · · n = Qn i=1 i. Par convention 0! = 1. Nous pouvons également utiliser une déﬁnition récursive n! = n · (n −1)! 1.2 Arrangement avec répétition Soit Ωun ensemble composé de n éléments : card(Ω) = n. Nous constituons un échantillon E de taille p (card(E) = p) à partir des éléments de Ω. Si nous avons à choisir p éléments parmi n dans une disposition ordonnée (les places sont distinctes) et avec répétition (on peut choisir le même élément plusieurs fois), on dit qu’on a un arrangement de p éléments parmi n. Le nombre d’arrangement avec répétition est np. N.B. Dans ce cas, il est possible que p > n. Réaliser un arrangement avec répétition des éléments de Ω, c’est aussi déﬁnir une application d’un ensemble E à p éléments dans Ω. L’ensemble des applications de E dans Ωsera noté ΩE et on a #(ΩE) = (#Ω)#E. 4 CHAPITRE 1. ÉLÉMENTS D’ANALYSE COMBINATOIRE 1.3 Arrangement sans répétition Soit Ωun ensemble avec card(Ω) = n. On constitue un échantillon de taille p (p ≤n), la disposition est ordonnée et sans répétition. On dit qu’on a un arrangement sans répétition de p éléments parmi n. Le nombre de p−arrangements d’un ensemble à n éléments est : Ap n = n! (n −p)!. Réaliser un arrangement sans répétition des éléments de Ω, c’est déterminer un p−uplet (x1, . . . , xp) d’éléments de Ωdeux à deux distincts. C’est aussi déﬁnir une application injective d’un ensemble E à p éléments dans Ωà n éléments. 1.4 Permutation sans répétition C’est un arrangement sans répétition de n éléments parmi n. Pn = An n = n! (n −n)! = n! Réaliser une permutation des éléments de Ω, c’est réaliser un tirage exhaustif sans remise des éléments de Ωen tenant compte de l’ordre du tirage. C’est aussi déﬁnir une bijection de ensemble Ωsur lui-même. L’ensemble des permutations d’un ensemble à n éléments s’appelle le groupe symétrique d’ordre n et se note Sn. On a #Sn = n!. 1.5 Permutation avec répétition On appelle permutation avec répétition de p éléments où n sont distincts (n ≤p), une disposition ordonnée de l’ensemble de ces p éléments où le premier ﬁgure p1 fois, le second p2 fois, etc., tel que p1 + p2 + · · · + pn = p. Le nombre de permutation avec répétitions est p! p1!p2!···pn! Démonstration : (Voir préalablement la déﬁnition d’une Combinaison sans répétition) Pour construire un p-uplet correspondant à une combinaison contenant p1 fois x1, p2 fois x2, ..., pn fois xn, il suﬃt : – de choisir les p1 emplacements des x1, parmi p1 + p2 + ... + pn places disponibles, – de choisir les p2 emplacements des x2, parmi les p2 + ... + pn places restantes, – etc. – de choisir les pn emplacements des xn, parmi les pn places restantes. Au total, il y a Cp1 p1+p2+···+pn · Cp2 p2+···+pn · · · Cpn pn = p! p1!p2! · · · pn! Exemple [Nombre d’anagrammes du mot MATHÉMATIQUE] : nous voyons qu’en échangeant les deux lettres A, le mot reste identique, et par contre en transposant les lettres É et E nous obtenons un mot diﬀérent. (M :2 ;A :2 ;T :2 ;H :1 ;É :1 ;I :1 ;Q :1 ;U :1 ;E :1) : #Anagrammes = 12!/(2!2!2!) Exemple 2 : Nombre de quartets binaires de poids de Hamming égal à 2 ; Il y en a 6 =4 !/(2 !2 !) : (0011),(0101),(0110),(1001),(1010),(1100). Cours Probabilités / Pierre DUSART 5 1.6 Combinaison sans répétition On considère un ensemble Ωconstitué de n éléments tous discernables. On forme un échantillon de taille p. Si la disposition est non-ordonnée et sans répétition, on dit que l’on a une combinaison sans répétition de p éléments parmi n. Le nombre de ces combinaisons se note Cp n ou n p . Cp n = n! p!(n −p)! Propriétés : 1. C0 n = Cn n = 1 2. Cp n = Cn−p n (complémentaire) 3. Cp n = Cp n−1 + Cp−1 n−1 (triangle de Pascal) 4. Cp n = Ap n p! Preuve que Cp n = Cp n−1 + Cp−1 n−1 : Cp n−1 + Cp−1 n−1 = (n −1)! p!(n −p −1)! + (n −1)! (p −1)!(n −p)! = (n −1)! · (n −p) p!(n −p)! + p · (n −1)! p!(n −p)! = n · (n −1)! p!(n −p)! = Cp n Proposition 1.6.1 (Formule du binôme) (a + b)n = n X p=0 Cp n · ap · bn−p. Exercice : preuve de la formule du binôme par récurrence sur n Preuve : (a + b)n+1 = (a + b)(a + b)n = (a + b) n X p=0 Cp n · ap · bn−p = n X p=0 Cp n · ap+1 · bn−p + n X p=0 Cp n · ap · bn+1−p = n+1 X p′=1 Cp′−1 n · ap′ · bn+1−p′ + n X p=0 Cp n · ap · bn+1−p = n X p=1 Cp−1 n · ap · bn+1−p + Cn nan+1b0 ! + C0 na0bn+1 + n X p=1 Cp n · ap · bn+1−p ! = an+1 + n X p=1 (Cp−1 n + Cp n | {z } Cp n+1 ) · ap · bn+1−p + bn+1 (a + b)n+1 = n+1 X p=0 Cp n+1 · ap · bn+1−p. 6 CHAPITRE 1. ÉLÉMENTS D’ANALYSE COMBINATOIRE 1.7 Combinaison avec répétition C’est une disposition non-ordonnée de p éléments, à choisir parmi n éléments discernables, avec répétition. Le nombre de combinaisons avec répétitions de n objets pris p à p est : Kp n = Cp n+p−1 Exemple : [jeu de domino] Les pièces sont constituées en disposant côte à côte deux éléments de l’ensemble {blanc, 1, 2, 3, 4, 5, 6}. Si nous retournons un domino, nous changeons l’ordre des deux éléments, mais le domino reste identique (C’est donc une disposition non-ordonnée). Nous avons une combinaison avec répétition de 2 éléments pris parmi les 7, et au total il y a K2 7 = 28 dominos dans un jeu. Toute p−combinaison avec répétition peut s’écrire : x1 : k1 fois, . . . , xn : kn fois avec 0 ≤ki ≤p et Pn i=1 ki = p. On peut ainsi mettre en bijection l’ensemble des p−combinaisons avec répétition des n éléments de E avec les applications f : E →N telles que x1 7− →f(x1) = k1 · · · xn 7− →f(xn) = kn vériﬁant n X i=1 f(xi) = p Exemple : Dans un jeu de dominos, un domino est une 2-combinaison avec répétition de l’ensemble E = {blanc, 1, 2, 3, 4, 5, 6}. Chaque domino peut être représenté par une application de E dans {0, 1, 2} qui associe à chaque élément de E le nombre de fois où l’élément apparaît sur le domino. Ainsi le domino [blanc,blanc], est représenté par l’application f déﬁnie par f(blanc) = 2, f(1) = 0, f(2) = 0, f(3) = 0, f(4) = 0, f(5) = 0, f(6) = 0 et le domino [blanc, 1] par l’application f déﬁnie par f(blanc) = 1, f(1) = 1, f(2) = 0, f(3) = 0, f(4) = 0, f(5) = 0, f(6) = 0. On peut aussi mettre cet ensemble en bijection avec l’ensemble des manières de placer p objets dans n boîtes : boîte 1 · · · i · · · n x1 · · · xi · · · xn k1 · · · ki · · · kn Mais placer p objets dans n boîtes c’est aussi se donner n uploads/Religion/ cours-proba-2013.pdf