Quel est le rôle de l'analyse combinatoire ?
L'analyse combinatoire est une branche des mathématiques qui étudie comment compter les objets.
Elle fournit des méthodes de dénombrements particulièrement utiles en théorie des probabilités.C'est quoi la combinatoire ?
combinatoire
1.
Disposition d'éléments qui se combinent entre eux selon un certain ordre. 2.
Branche des mathématiques qui étudie les configurations d'éléments discrets et les opérations faites sur ces configurations.Comment calculer une combinatoire ?
La notion de combinaison est essentielle en statistiques et probabilités.
On l'écrit de moins en moins souvent Ckn C n k et de plus en plus (nk) .
La formule de calcul est (nk)=nk (n−k)- Une combinaison est une sélection de �� éléments choisis sans répétition parmi un ensemble de �� éléments pour laquelle l'ordre n'a pas d'importance.
La principale différence entre une combinaison et un arrangement est que l'ordre n'a pas d'importance.
Pour un arrangement, l'ordre est important.
COMBINATOIRE ET DÉNOMBREMENT
13 Combinatoire et probabilités
Combinatoire énumérative
Analyse combinatoire
Cours de DEUG Probabilités et Statistiques
Combinatoire & Probabilités Jean-Philippe Javet
Chapitre 1: Analyse combinatoire
Analyse combinatoire et probabilités
Analyse des principes du génie logiciel au niveau
Analyse combinatoireMathematiques Generales BUniversite de GeneveSylvain Sardy6 mars 20081Le but de l'analyse combinatoire (techniques de denombrement) est d'ap-prendre a compter le nombre d'elements d'un ensemble ni de grande cardinalite.Notation : la cardinalite d'un ensemble, noteecard() =jj= #, est lenombre d'elements contenus dans l'ensemble.Analyse combinatoire21.
Principe de multiplicationPermet de compter le nombre de resultats d'experiences qui peuvent sedecomposer en une succession de sous-experiences.Principe : suppose qu'une experience est la succession demsous-experiences.Si laieme experience aniresultats possibles pouri= 1;:::;n, alors le nombretotal de resultats possibles de l'experience globale estn= mi=1ni=n1n2:::nm:Analyse combinatoire3Exemple : Vous achetez une valise a code 4 chires.
Combien de possibilitesavez-vous de choisir un code?Reponse :m= 4avecn1= 10,n2= 10,n3= 10,n4= 10, donc le nombretotal de code possible est10101010 = 104.Exemple : les plaques mineralogiques aux U.S.A. sont formees de 3 lettres,suivies de 3 chires.Quel est le nomb rede plaques m ineralogiquesp ossibles?Quel est le nomb rede plaques qui commencent pa rla lettre U ?Analyse combinatoire42.
PermutationsDenition : unep ermutationde nelementsdistincts e1;:::;enest unrearrangemento rdonnesans r epetitionde ces nelements.Exemple : "a", "b" et "c" sont trois elements.
Les arrangements possiblessontabc;acb;bac;bca;cab;cba:Le nombre d'arrangements est donc 6.Notation : La fonction `factorielle' est la fonction de domaineN=f0;1;2;:::gqui a toutn2 Nassocien! =n(n1):::321.Ainsi0! = 1,1! = 1,2! = 2,3! = 6,:::,10! = 306280800.Analyse combinatoire5Le nombre de permutations denelementsdistincts est n!.Demonstration : par application du principe de multiplication a une experienceanetapes :1 ere etape: n1=nchoix possibles.2 eme etape: n2= (n1)choix possibles.{nieme etape :nn= 1choix possible.Exemple : 4 Americains, 5 Suisses et 7 japonais doivent s'asseoir sur un m^emebanc, et doivent rester groupes par nationalite.
Combien y a-t-il de dispositionspossibles?Reponse :3!4!5!7!.Analyse combinatoire6Denition : Una rrangementest une p ermutationde kelements pris parminelementsdistincts ( k6n).
Les elements sont prissans r epetitionet sontordonnesNotation : le nombre de permutations dekparminest noteAn;k.Exemple : les arrangements de 2 elements pris dansf1;2;3;4gsontf1;2g;f1;3g;f1;4g;f2;1g;f2;3g;f2;4g;f3;1g;f3;2g;f3;4g;f4;1g;f4;2g;f4;3g:Il y en a 12.Peut-on trouver une formule pour compter le nombre d'arrangements?Analyse combinatoire7Il s'agit encore du principe de multiplication a une experience aketapes :1 ere etape: n1=nchoix possibles.2 eme etape: n2= (n1)choix possibles.{kieme etape :nk= (nk+ 1)choix possible.Donc :An;k=n(n1)(nk+ 1)=n(n1)(nk+ 1)(nk)(nk1)21(nk)(nk1)21:Le nombre d'arrangements est :An;k=n!(nk)!:Analyse combinatoire8Exemple : Combien de mots de 3 lettresdistinct esp euvent^ etrefo rmesdansun alphabet de 26 lettres?Reponse :A26;3= (26)(25)(24) = 150600.Exemple : Combien de mots de 3 lettres peuvent ^etre formes dans un alphabetde 26 lettres?Reponse :263= 170576, naturellement plus de possibilite qu'avec les arrange-ments.Analyse combinatoire93.
Combinaisons et coecients binomiauxDenition : Uncombinaisonde kelements pris dans un ensemble anelementsdistincts est un sous-ensemble akelements de cet ensemble.
Les elements sontprissan sr epetitionet ne sont paso rdonnesNotation : le nombre de combinaisons dekparminest noteCn;kounkqui est appele coecient binomial.Exemple : les combinaisons de 2 elements pris dansf1;2;3;4gsontf1;2g;f1;3g;f1;4g;f2;3g;f2;4g;f3;4g:Il y en a 6.Peut-on trouver une formule pour compter le nombre de combinaisons?Analyse combinatoire10Dans un sous-ensemble, les elements ne sont pas ordonnes, au contraire d'unarrangement.Par consequence, a chaque sous-ensemble correspondk!arrangements, donc :Cn;k=An;kk!n!k!(nk)!:Exemple : on a 15 medicaments et on veut tester leur compatibilite en groupede 4.
Combien y a-t-il de groupes possibles?Reponse :C15;4=15!4!11!= 10365possibilites.Analyse combinatoire11Proprietes :{Cn;k=Cn;nkF ormulede r ecurrenceCn;k=Cn1;k1+Cn1;k.Demonstration : Soit=fw1;:::;wng.
Le nombreCn;kest le nombrede sous-ensembles dede cardinalitek.Soitkcet ensemble de sous-ensembles; il se decompose en l'union de deux ensembles disjoints :k=k;w1=a[k;w16=aOrjkj=jk;w1=aj+jk;w16=aj jk;w1=aTk;w16=aj.Doncjkj=Cn1;k1+Cn1;k0.Le tr ianglede P ascalest une cons equencede la f ormulede r ecurrence: Analyse combinatoire1200101120212230313233etc11 11 2 11 3 3 11 4 6 4 1 Analyse combinatoire13Combien y a-t-il de sous-ensembles d'un ensemble de ca rdinaliten?fe1,e2,:::,engouinonouinon:::ouinonsoit un total de2nsous-ensembles.Le b in^omede Newton : (x1+x2)n=Pnk=0nkxk1xnk2.Analyse combinatoire144.
Coecients multinomiauxLe but est de decouper un ensemble denelements enrsous-ensembles detaillesn1;n2;:::;nr, tels quen1+n2+:::+nr=n, et de determiner le nombrede decoupages possibles.Exemple : L'ensemblef1;2;3;4gen 3 sous-ensembles de tailles 2, 1 et 1.f(1;2);3;4g;f(1;2);4;3g;f(1;3);2;4g;f(1;3);4;2g;f(1;4);2;3g;f(1;4);3;2g;f(2;3);1;4g;f(2;3);4;1g;f(2;4);1;3g;f(2;4);3;1g;f(3;4);1;2g;f(3;4);2;1g:Il y en a 12.Peut-on trouver une formule pour compter le nombre de decoupage?Analyse combinatoire15On applique le principe de multiplication :il y a Cn;n1choix pour le premier sous-ensembleil y a Cnn1;n2choix pour le deuxieme sous-ensembleil y a Cnn1:::nr1;nrchoix pour lerieme sous-ensembleSoit au total :Cn;n1Cnn1;n2Cnn1:::nr1;nrn!n1!(nn1)!(nn1)!n2!(nn1n2)!(n(n1 nr1))!nr!(n(n1 nr))!n!n1!n2!nr!=:nn1;n2;;nr:Analyse combinatoire16Proprietes :Quand r= 2, on retrouve le coecient binomial puisquenk;nk=nk=nnkTh eorememultinomial(x1++xr)n=Xn1;:::;nr:Pri=1ni=nnn1;n2;;nrxn11xn22xnrr:Analyse combinatoire17Exemple : Quatre joueurs Georges, Jacques, Tony et Angela recoivent 13cartes d'un jeu de 52.
Combien y a-t-il de repartitions possibles des cartesentre ces 4 joueurs?Reponse :5213;13;13;1352!(13!)45:361028.Exemple : Une usine delocalise et envoie les employes d'un bureau d'etudede 23 personnes dans un bureau de 13 personnes en Chine, et deux bureauxde 5 pesonnes en Pologne et Irlande.
Combien de groupes peuvent ^etreformes?Reponse :2313;5;5.Analyse combinatoire184.ApplicationsP1 : Quatre couples doivent ^etre assis dans une rangee de 8 chaises.Combien y a-t-il de facon de le faire si :Il n'y a pas de contraintes.R :8! = 400320Les hommes doivent rester ensemble et les femmes au ssi.R :2(4!)2= 10152Les hommes doivent rester ensemble.R :5(4!)2= 20880Chaque couple ma riedoit rester ensemble.R :24(4!) = 384Analyse combinatoire19P2 : Combien de mots dierents (qui ont un sens ou non) peut-on formeravec les lettres des mots suivants?v elospapierbananeminimum Analyse combinatoire20P3 : on verra que, pour des evenements elementaires equiprobables, laprobabilited'un evenementGest donnee par :P(G) =Nombre de cas favorables pour Gnombre de cas possiblesExemple : on lance une piece de monnaie equitable deux fois de suite.
Quelleest la probabilite que deux resultats soient identiques?Analyse combinatoire21R : L'univers (ensemble des cas possibles) de l'experience est=f(P;P);(P;F);(F;P);(F;F)g:Doncjj= 4.L'ensemble "les deux resultats sont identiques" estG=f(P;P);(F;F)g;de cardinalitejGj= 2.Donc la probabilite que deux resultats soient identiques estP(G) =jGjjj=24= 0:5Analyse combinatoire22Exemple : Il y anpersonnes dans une classe.
Quelle est la probabilite del'evenementG="au moins deux personnes ont le m^eme anniversaire"?R : L'univers est=f1;2;:::;365gnde cardinalitejj= 365n.Plut^ot que de travailler avec l'ensembleG, travaillons avec soncomplementaireGc="lesnanniversaires sont distincts".Cet ensemble a pour cardinalitejGcj=A365;n, doncP(Gc) =A365;n365n;et par consequentP(G) = 1P(Gc) = 1A365;n365n.Q : Cette formule marche-t-elle pourn >365?Q : A partir de quelle valeur dencette probabilite est superieure a 0.5?Analyse combinatoire23Exemple : On repetenfois le lancer de deux des.
Calculer la probabiliteque le 6 apparaisse au moins une fois.Quelle valeur donner anpour que cetteprobabilite atteigne 1/2?La probabilite que le 6 n'apparaisse pas est52=62pour un jet.Par le principe de multiplication, la probabilite que le 6 n'apparaisse pas dansnjets est(52=62)n.Donc la probabilite que le 6 apparaisse au moins une fois dansnjets est1(5=6)2n:Pour que cette probabilite soit superieure a 1/2, il faut quen>?.Analyse combinatoire