Remerciez-le!

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

Universit´ e cheikh Anta Diop de Dakar Facult´ e des Sciences et Techniques Dep

Universit´ e cheikh Anta Diop de Dakar Facult´ e des Sciences et Techniques Departement de Math´ ematiques et Informatique Cours de Proba-Stats 1 Abdoulaye Maiga abdoulaye.maiga888@gmail.com Table des mati` eres Introduction 2 I Probabilit´ e 3 1 Analyse Combinatoire 4 I Rappel sur la th´ eorie des ensembles . . . . . . . . . . . . . . . . . . . . . . 5 I.1 Rappel : CARDINALITE . . . . . . . . . . . . . . . . . . . . . . . 5 II DENOMBREMENNT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 II.1 Les arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 II.2 Les permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 II.3 Les combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 III PROPRI´ ET´ ES DES COMBINAISON . . . . . . . . . . . . . . . . . . . . . 10 2 Premi` ere partie Probabilit´ e 3 Chapitre 1 Analyse Combinatoire INTRODUCTION Un systeme de communication est compose de n entennes identiques alignees. Ce sys- teme ne pourra alors capter de signal incident(il sera qualiﬁe de fonctionnel) qu’aussi longtemps que deux entennes consecutives ne seront pas defectueuses. Autrement dit le systeme est qualiﬁe de fonctionnel s’il ya pas deux entennes consecutives defectueuses. Question : si on decouvre m dans n entennes sont defectueuses, quel est la probabilite que ce systeme soit fonctionnel ? Exemple : Pour n=4 et m=2 Les diﬀerentes conﬁgurations sont : 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 Solution La probabilite est :prob=3/6=1/2 On pourrait de maniere similaire calculer la probabilite que le systeme fonctionne pour des valeurs quelconque de m et n. PROBLEMATIQUE Il faudrait calculer le nombre de conﬁguration qui maintiennent le systeme fonctionnel et le diviser par les conﬁgurations possibles. IL est souhaitable de disposer les methodes eﬃcaces pour denombrer tes diﬀerentes situations pouvant se presenter. Par convention on appelle analyse combinatoire la theorie mathematique de denombre- ment 4 1. Analyse Combinatoire I Rappel sur la th´ eorie des ensembles I.1 Rappel : CARDINALITE Un ensemble est dit ﬁni s’il contient 0 ou n ´ el´ ements. D´ eﬁnition 1 (ensemble ﬁni). Un ensemble est dit d´ enombrable s’il est en bijection avec N (ces ´ el´ ements peut ˆ etre indexes par des entiers). D´ eﬁnition 2 (ensemble d´ enombrable). Un ensemble est dit au plus d´ enombrable s’il est ﬁni ou d´ enombrable. D´ eﬁnition 3. Soit E un ensemble ﬁni. Le cardinal de E , note CardpEq ou |E| est le nombre de E. D´ eﬁnition 4. EXEMPLE : E “ t1, 2, 3, 4u, cardpEq “ 4. Soient E un ensemble ﬁni et A,B et C 3 parties de E. 1. A Ă E ñ CardpAq ď CardpEq ; 2. CardpA Y Bq “ CardpAq ` CardpBq ´ CardpA X Bq ; En particulier si A X B “ m alors CardpA Y Bq “ CardpAq ` CardpBq ; 3. CardpA{Bq “ CardpAq ´ CardpA X Bq ; 4. CardpA ˚ Bq “ CardpAq ˚ CardpBq ; Et de mani` ere g´ en´ erale Cardp n ź i“1 Aiq “ n ź i“1 CardpAiq Proposition 1. 5 Abdoulaye Maiga abdoulaye.maiga888@gmail.com 1. Analyse Combinatoire $ ’ ’ ’ ’ ’ ’ & ’ ’ ’ ’ ’ ’ % CardpYn i“1Aiq “ řn i“1 CardpAiq ´ ř 1ďiăjďn CardpAi X Ajq ` ř 1ďiăjălďn CardpAi X Aj X Alq . . . `p´1qn`1CardpXn i“1Aiq En particulier pour n=3, on a : CardpA1 Y A2 Y A3q “ CardpA1q ` CardpA2q ` CardpA3q ´ CardpA1 X A2q ´ cardpA1 X A3q ´ CardpA2 X A3q ` CardpA1 X A2 X A3q Proposition 2 (FORMULE DE POINCAR´ E OU DES CRIBLES). II DENOMBREMENNT Beaucoup de probl` emes de d´ enombrement se ram` enent aux nombres de mani` eres de ranger p objets choisis parmi n. Il est important avant tout d´ enombrement, de savoir si l’ordre est important ou non, s’il y’a possibilit´ e qu’un ´ el´ ement se r´ ep` ete et tous les objets sont pris ou non. Selon le cas, la mani` ere de compter change compl` etement. Ainsi on appellera : groupement sans r´ ep´ etition : le rangement qui ne renferme que des objets distincts et groupement avec r´ ep´ etition dans le cas contraire. Selon l’ordre est important on aura aﬀaire a : — des combinaisons si l’ordre n’est pas important — des arrangements et des permutations si l’ordre compte Dans les probl` emes de d´ enombrement, on a recours aux deux principes fondamentaux : le principe de multiplication et le principe d’addition 1. LE PRINCIPE DE MULTIPLICATION Si une proc´ edure quelconque peut ˆ etre eﬀectu´ ee de n1 fa¸ cons diﬀ´ erentes, puis qu’une autre proc´ edure peut ˆ etre eﬀectu´ ee de n2 fa¸ cons diﬀ´ erentes, et ainsi de suite et qu’enﬁn qu’une k-ieme proc´ edure peut ˆ etre eﬀectu´ ee de nk fa¸ cons diﬀ´ erentes alors le nombres de fa¸ cons d’ex´ ecuter ces proc´ edures dans l’ordre est ´ egal au produit n1 ˚ n2 ˚ ... ˚ nk EXEMPLE On a trois villes A,B et C, il y’a trois chemins entre A et B et 5 chemins entre B et C QUESTION : il y’a combien de chemins entre A et C ? 6 Abdoulaye Maiga abdoulaye.maiga888@gmail.com 1. Analyse Combinatoire REPONSE : il y’a 5*3=15 d’apr` es le principes de multiplication 2. LE PRINCIPE D’ADDITION Si une exp´ erience A peut ˆ etre r´ ealis´ ee de n fa¸ cons distinctes et si une exp´ erience B peut ˆ etre r´ ealis´ ee de m fa¸ cons distinctes : *Si A et B ne se r´ ealisent pas simultan´ ement, alors il y’a m+n fa¸ cons distinctes de r´ ealiser A ou B. * Si A et B se r´ ealise simultan´ ement, alors il y’a m+n-p fa¸ cons distinctes de r´ ealiser A ou B, ou p est le nombres de r´ ealisation communes. II.1 Les arrangements On appelle arrangement sans r´ ep´ etition (ou arrangement tout court) de p- ´ el´ ements parmi n, une suite ordonn´ ee de p-´ el´ ements distincts. D´ eﬁnition 5 (ARRANGEMENTS SANS R´ EP´ ETITION). Un ´ el´ ement ne ﬁgure qu’une seule fois dans un arrangement sans r´ ep´ etition. Dans le langage des tirages ¸ ca correspond au tirage sans remise avec ordre 1 ď p ď n@n, p P N˚ Remarque 1. Le nombre de p-arrangement (sans r´ ep´ etition) d’un ensemble de cardinal n est ´ egale a : Ap n “ n! pn ´ pq! “ npn ´ 1q...pn ´ p ` 1q Th´ eor` eme 1. EXEMPLE : Dans une urne contenant 20 boules distinctes, on tire 6 boules l’une apr` es l’autres sans les remettre dans l’urne. Quel est le nombre de tirage possible ? Il s’agit d’un arrangement de 6 boules parmi 20. Le nombre de tirages possibles est donc ´ egal ` a An 20 7 Abdoulaye Maiga abdoulaye.maiga888@gmail.com 1. Analyse Combinatoire Soit E=te1, e2, ..., enu un ensemble de cardinale n et p un entier. On appelle arrangement avec r´ ep´ etition d’ordre p ou (p-liste) de E , toute suite ordonn´ ee de p ´ el´ ements de E pas forcement distincts. D´ eﬁnition 6 (ARRANGEMENTS Avec R´ EP´ ETITION : p-liste). Dans le langage des tirages ¸ ca correspond aux tirages sans remises, p peut ˆ etre ě n Remarque 2. Le nombre de p-liste d’un ensemble de cardinal n est ´ egale a np Th´ eor` eme 2. EXEMPLE :Dans une urne contenant 20 boules distinguables, on tire 6 boules l’une apr` es l’autre en les remettants dans l’urne apr` es chaque tirages. Quel est le nombre de tirage possible ? Il y’a 206 tirages II.2 Les permutations Une permutation sans r´ ep´ etition (ou permutation simple ou tout simplement per- mutation) de n ´ el´ ements de E est une suite ordonn´ ee n ´ el´ ements de E distincts. C’est donc un arrangement sans r´ ep´ etition de n ´ el´ ements dans n. D´ eﬁnition 7 (PERMUTATION SANS r´ ep´ etition). Le nombre de permutations de n ´ el´ ements est ´ egal ` a n! Th´ eor` eme 3. EXEMPLE : Dans uploads/Management/ cours-de-proba-stats.pdf