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 Granulométrique
Cours d'Analyse et Conception des Systèmes d'Information
Analyse et Conception du Système d'Information (Merise)

Next PDF List

1.3. COMBINATOIRE ET PROBABILIT´ES331.

3) Combinatoire et probabilit´esLacombinatoire(ouanalyse combinatoire) est l"´etude des ensembles finis du point devue du nombre de leurs ´el´ements.

Elle porte sur le d´enombrement de configurations d"objetssatisfaisant des conditions donn´ees.

La combinatoire sert d"outil dans plusieurs probl`emes´el´ementaires enth´eorie des probabilit´es, domaine des math´ematiques qui trouve son originedans l"´etude des jeux de hasard.1.Deux principes de comptage.Les deux principes suivants jouent un rˆole fondamental en combinatoire.Principe d"addition :Soit deux ensemblesAetBcontenant respectivementmetn´el´ements et tels queA∩B=∅.

Alors l"ensembleA?Bcontientm+n´el´ements.Principe de multiplication :Soit deux ensemblesAetBcontenant respectivementmetn´el´ements.

Alors l"ensembleA×Bcontientm·n´el´ements.Il va de soi que chacun de ces principes peut se g´en´eraliser `a un nombre fini quelconqued"ensembles.

Ainsi, dans le cas du premier, siA1,A2, ,Akforment une partition del"ensembleE, alors#E=#A1+#A2+···+#AkLe premier principe affirme essentiellement que le tout est la somme de ses parties.Quant au second, il peut ˆetre vu comme une cons´equence de l"autre.

En effet, siA={a1,a2, ,am}, alorsA×Bpeut se partitionner enmensemblesE1,E2, ,Em,o`uEi={(ai,b):b?B}.

ChaqueEicomprenantn´el´ements, on a#(A×B)=#E1+#E2+···+#Em=n+n+···+n(mfois le termen)=m·n.Le principe additif peut se g´en´eraliser de la fa¸con suivante :Si#A=met#B=n,alors#(A?B)≤m+n(avec ´egalit´e lorsqueA∩B=∅).Exemples:(a) J"ai dans ma biblioth`eque 50 livres de math´ematiques en fran¸cais et 40 livres de math´ema-tiques en anglais (et aucun dans une autre langue).

Je peux donc y choisir un livre demath´ematiques de 50 + 40 = 90 fa¸cons diff´erentes.(b) Mon coll`egue de travail poss`ede 30 livres de math´ematiques en fran¸cais.

Sinrepr´esentele nombre de livres math´ematiques fran¸cais qui peuvent ˆetre consult´es dans nos deuxbureaux, alors 30≤n≤80, puisque un exemplaire du mˆeme livre pourrait se retrouverdans chacune de nos deux biblioth`eques.(c) En lan¸cant une pi`ece de monnaie et un d´e, on peut obtenir 2·6=12r´esultats diff´erents :(p,1),(p,2),(p,3),(p,4),(p,5),(p,6),(f,1),(f,2),(f,3),(f,4),(f,5),(f,6),o`uprepr´esente "pile" etf"face".34CHAPITRE 1.

UN COFFRE D"OUTILSLes principes de comptage pr´ec´edents sont souvent exprim´es en termes de choix :´Etant donn´e deux piles d"objets, si un objet peut ˆetre choisi dans la premi`ere demfa¸cons et aussi un objet choisi dans la seconde denfa¸cons, alors le choix d"un objetde l"une ou l"autre des piles peut se faire dem+nfa¸cons.´Etant donn´e deux piles d"objets, si un objet peut ˆetre choisi dans la premi`ere demfa¸cons et aussi un objet choisi dans la seconde denfa¸cons, alors le choix de deuxobjets, un dans chacune des piles, peut se faire dem·nfa¸cons.Exemples:(a)Montrer qu"`a partir d"un ensemble comprenantn´el´ements, on peut former2nsous-ensembles.SoitA={a1,a2, ,an}.D´eterminer un sous-ensembleXdeArevient `a se demander,pour chaquei=1,2, ,n,siai?X.

Mais pour chaque ´el´ementaideA, on a deuxpossibilit´es:oubienonmetaidansX, ou bien on ne l"y met pas.

Et comme on r´ep`eteun tel choixnfois, on a donc2×2×···×2nfois=2nsous-ensembles pouvant ˆetre form´es.L"arbre suivant illustre le processus pour le cas d"un ensembleA={a,b,c}`a trois´el´ements.

Pour chaquex?A, une fl`eche vers le haut indique qu"on prendx, et unefl`eche vers le bas indique qu"on ne le prend pas.aabbccccbccccb(b)Trouver le nombre d"entiers positifs dont le d´eveloppement en basebcomprendkchiffres.Comme il y ab-1 possibilit´es pour le chiffre de gauche (0 ne peut y figurer) etbpourchacun des autres chiffres, le nombre total de tels entiers est (b-1)·bk-1(c)Trouver le nombre de nombres impairs dont le d´eveloppement d´ecimal comprend quatrechiffres distincts.On s"int´eresse aux nombres impairs allant de 1000 `a 9999 dont les chiffres sont tousdiff´erents.

On a donc quatre choix `a faire.

Il est plus commode de commencer par lechiffre des unit´es, pour lequel il y a 5 possibilit´es : 1,3,5,7 ou 9.

Comme le chiffre desunit´es de mille ne peut ˆetre 0, il reste 8 choix possibles apr`es le choix du chiffre des1.3.

COMBINATOIRE ET PROBABILIT´ES35unit´es.

Le chiffre des centaines peut alors ˆetre choisi de 8 fa¸cons, quels que soient les deuxpremiers choix, puis celui des dizaines de 7 fa¸cons.

Il y a donc en tout 5·8·8·7 = 2240nombres r´epondant aux conditions du probl`eme.(d)Trouver le nombre de nombres de 1 `a 1000 dont le d´eveloppement d´ecimal comprendune seule fois le chiffre 3.SoitE, l"ensemble de tous les nombres r´epondant `a la question et consid´erons la partitionE=E1?E2?E3,o`u, pourj=1,2,3,Ejd´esigne l"ensemble form´e des nombres deEs"´ecrivant avecjchiffres (il n"y a pas de nombre `a 4 chiffres dansE).

Clairement#E1= 1.

Les nombres dansE2sont de deux types : (i) ceux dont le chiffre des unit´esest 3, sauf 33 (il y en a 8); (ii) ceux dont le chiffre des dizaines est 3, sauf 33 (il y ena 9).

On a donc #E2= 8 + 9 = 17.

De mˆeme,E3comprend des nombres ayant un 3soit dans la position des unit´es (il y en a 8·9), soit dans celle des dizaines (8·9), soitdans celle des centaines (9·9), de sorte que #E3= 72 + 72 + 81 = 225.

On a donc#E=#E1+#E2+#E3= 1 + 17 + 225 = 243.(e)Trouver le nombre de nombres dont le d´eveloppement d´ecimal comprend trois fois lechiffre 7, une fois le chiffre 8 et une fois le chiffre 9.Comme on s"int´eresse `a des nombres `a 5 chiffres, il y a 5 positions possibles pour lechiffre 8 et 4 pour le chiffre 9, les 3 autres ´etant toutes occup´ees par le chiffre 7.

Il y adonc 5·4 = 20 nombres du type demand´e.(f)Trouver le nombre de nombres dont le d´eveloppement d´ecimal comprend trois fois lechiffre 7 et deux fois le chiffre 8.On s"int´eresse `a nouveau `a des nombres `a 5 chiffres, mais il y a maintenant deux foismoins de possibilit´es que dans l"exemple (e).

On trouve ainsi 10 nombres du type de-mand´e.2.Permutations d"un ensemble.Soitrun entier positif.

Uner-permutationd"un ensembleE`an´el´ements est unclassement ordonn´eder´el´ements choisis parmi cesn, chaque ´el´ement ne pouvantservir qu"une seule fois.

Il s"agit donc d"une liste ordonn´ee et sans r´ep´etitions.

On parleaussi d"arrangement denobjets prisr`a la fois.Ond´esigne parP(n,r) le nombre der-permutations denobjets.Exemple:P(8,5) = 8·7·6·5·4 = 6720.

Cela revient `a faire une liste ordonn´ee de 5 objets choisis parmi8, le premier ´el´ement de la liste pouvant ˆetre choisi de 8 fa¸cons, le second de 7 fa¸cons, etc.Une autre interpr´etation deP(8,5) est le rangement de 5 objets distincts dans 8 tiroirs :il y a 8 tiroirs possibles pour le premier objet, 7 pour le second, etc.Observons queP(n,r) = 0 lorsquer>n, puisqu"on ne peut former de liste der´el´ements distincts avec seulementn.

Par ailleursP(n,1) =npour tout entier positifn.Defa¸con g´en´erale, pourr≤n,P(n,r)=n×(n-1)×(n-2)×···×(n-r+1)=n!(n-r)!.Lorsquer=n, uner-permutation s"appelle simplement unepermutationden´el´ements.Une permutation d"un ensembleEest donc une liste des ´el´ements deEdonn´ee dans36CHAPITRE 1.

UN COFFRE D"OUTILSun certain ordre.

On aP(n,n)=n×(n-1)×···×3×2×1=n!.Exemples:(a)De combien de fa¸cons peut-on asseoir 10 personnes (i) `a une table d"honneur sur uneestrade; (ii) autour d"une table circulaire?(i) Il y a 10! = 3 628 800 fa¸cons. (ii) Faisant asseoir l"une des personnes, il y a donc 9fa¸cons d"occuper le si`ege `a sa gauche, 8 pour le si`ege suivant, etc.

Il y a donc en tout9! = 362 880 dispositions possibles.(b)De combien de fa¸cons peut-on asseoir 10 personnes autour d"une table circulaire, s"il ya deux personnes parmi celles-ci qui ne peuvent ˆetre assises cˆote `acˆote?SoitAetB, les deux personnes ne pouvant se trouver l"une `acˆot´e de l"autre.

FaisantasseoirA, il y a donc 8 fa¸cons d"occuper le si`ege `a sa gauche (carBne peut s"y trouver),et 7 fa¸cons pour le si`ege `a sa droite.

Les autres si`eges peuvent ˆetre occup´es de 7! fa¸cons,ce qui donne en tout 8·7·7! = 7·8! = 282 240 dispositions possibles.3.Combinaisons d"un ensemble.Soitrun entier naturel.

Uner-combinaisond"un ensembleE`an´el´ements est un clas-sement der´el´ements choisis parmi cesn, sans qu"on se pr´eoccupe de l"ordre et chaque´el´ement ne pouvant servir qu"une seule fois.

En d"autres mots, uner-combinaison deEest un sous-ensemble deEcontenantr´el´ements.

Le nombre der-combinaisons denobjets se d´esigne par la notationC(n,r)ounr. (Ce dernier symbole s"appelle uncoefficient binomial, car il intervient dans le d´eveloppement du binˆome (x+y)n- voirplus bas.)Exemple:43= 4, car l"ensemble{a,b,c,d}a 4 sous-ensembles `a3´el´ements :{a,b,c},{a,b,d},{a,c,d}et{b,c,d}.Il d´ecoule directement de la d´efinition quenr=0sir>net que0r=0sir>0.On a aussi, pour tout natureln,n0=1,n1=netnn=1.La propri´et´e de base des coefficients binomiaux est la suivante :Si0≤r≤n, alorsP(n,r)=r!nrD´emonstration:SoitEun ensemble `an´el´ements.

Touter-permutation deEest obtenue en effectuant succes-sivement les deux tˆaches suivantes : (i) choisirr´el´ements dansE; (ii) arranger ces ´el´ementsselon un certain ordre.

Or la premi`ere de ces tˆaches peut s"accomplir denrfa¸cons, et laseconde deP(r,r)=r! fa¸cons.Le r´esultat pr´ec´edent peut se r´e´ecrire comme suit, ce qui constitue la relation fonda-mentale pour la manipulation des coefficients binomiaux :nr=n!r!(n-r)!.1.3.

COMBINATOIRE ET PROBABILIT´ES37Exemples:(a)On donne dans le plan 25 points tels qu"il n"y en a pas trois d"entre eux qui soientcolin´eaires.

Combien de droites ces points d´eterminent-ils? Combien de triangles?Comme il n"y a pas trois points d"align´es, chaque paire de points d´etermine une droite.Le nombre de droites ainsi d´etermin´ees est donc252=25!2!23!= 300.De mˆeme, le nombre de triangles est253=25!3!22!= 2300.(b)D´eterminer le nombre de mots denlettres comprenant exactementrfois la lettreaquel"on peut ´ecrire avec les deux seules lettresaetb.Cela revient `a choisirrpositions, parmi lesn,o`u on inscrira una; cela peut donc sefaire denrfa¸cons. (Lesn-rautres positions sont forc´ement occup´ees par unb.)(c)D´eterminer le nombre de mots de 8 lettres comprenant 3 voyelles pouvant ˆetre form´esavec l"alphabet usuel.Les trois positions occup´ees par les voyelles peuvent ˆetre choisies de83mani`eres.

Maisalors les positions des voyelles peuvent ˆetre remplies de 63fa¸cons, et celles des consonnesde 205fa¸cons.

Il y a donc en tout8363205= 38 707 200 000mots possibles.(d)Montrer que le produit derentiers positifs cons´ecutifs est toujours divisible par leproduit desrpremiers entiers positifs.AppelantNle plus grand desrentiers en cause, leur produit estN×(N-1)×···×(N-r+1)=P(N,r).

OrP(N,r)=r!Nr.

Et puisqueNrest un entier, il suit quer!|N×(N-1)×···×(N-r+ 1).(e)Montrer que sipest un premier, alorsp|prpourr=1,2, ,p-1.Commeprp!r!(p-r)!est un entier, il faut donc que le num´erateurp! soit un multipledu d´enominateur.

Maispet le d´enominateur ´etant relativement premiers, cela signifieque(p-1)!r!(p-r)!est un entier.Voici quelques propri´et´es des coefficients binomiaux.

Chacune peut se d´emontrer soitpar un argument combinatoire bas´e sur l"interpr´etation denr,soitparunargumentalg´ebrique en termes de la factorielle.(i)nrnn-r(ii)nr=nr·n-1r-1pour1≤r≤n;38CHAPITRE 1.

UN COFFRE D"OUTILS(iii)nrn-1rn-1r-1pour1≤r≤n;(iv)nkkrnrn-rk-r(v)rrr+1rr+2rnrn+1r+1D´emonstration:(ii)nr=n!r!(n-r)!=nr·(n-1)!(r-1)!(n-r)!=nr·n-1r-1(iii)Soit un ensemble `an´el´ementsEdont on fixe un ´el´ementx.

On partage sesnrsous-ensembles `ar´el´ements en deux cat´egories, selon que le sous-ensemble en cause contienne ounonx.

Lorsquexest exclus, il y an-1rfa¸cons de former un sous-ensemble `ar´el´ements `apartir des ´el´ements restant.

Et sixest pr´esent, il ne reste qu"`a choisirr-1´el´ements parmilesn-1 autres, ce qui peut se faire den-1r-1fa¸cons.(iv)Choisirkpersonnes parmin, puisrchefs parmi ceskpersonnes, ´equivaut `a d"abordchoisirrchefs parmi lesnpersonnes, puisk-rautres personnes parmi lesn-rrestantes.L"identit´e (iii) permet de calculer les coefficients binomiaux "de proche en proche".

Onpeut `a cette fin les disposer selon un arrangement g´eom´etrique c´el`ebre, letriangle dePascal. (Ce tableau de nombres porte le nom du math´ematicien fran¸cais Blaise Pascal(1623-1662), mais il ´etait d´ej`a connu des math´ematiciens chinois du 13esi`ecle.) On yretrouve sur une ligne donn´ee tous les coefficientsnrpour 0≤r≤n.n\r012345678···01111212131331414641515101051616152015617172135352171818285670562881On observera la sym´etrie de chaque ligne par rapport `a son centreŽ, cons´equence de lapropri´et´e (i).

Les nombres de la formen2(colonne 2) sont les nombres triangulaires.En additionnant les nombres de la formen-10n-21n-32, (ils sont situ´es sur une"diagonale" sud-ouest nord-est), on obtient le nombre de Fibonaccifn.

Par exemple,70615243=1+6+10+4=21=f84.La formule du binˆome.1.3.

COMBINATOIRE ET PROBABILIT´ES39L"appellation "coefficient binomial" pour d´esigner le nombrenkprovient du lien quel"on peut ´etablir avec le d´eveloppement du binˆome (x+y)n(d´eveloppement aussi connusous le nom debinˆome de Newton, en l"honneur d"Isaac Newton (1642-1727)).

On a eneffet le r´esultat suivant :nkest le coefficient du termexkyn-kdans le d´eveloppementde(x+y)nEn d"autres termes, ´etant donn´e deux variables quelconquesxety(qui peuvent ˆetredes nombres r´eels), on a alors, pour chaque entier positifn,(x+y)nnk=0nkxkyn-kD´emonstration:Le d´eveloppement de (x+y)ns"obtient en effectuant le produit (x+y)(x+y)···(x+y)denfacteurs ´egaux et en regroupant les termes semblables.

Lors de cette multiplication, on choisitsoitxsoityde chacun des facteurs (x+y), de sorte qu"on obtient en tout 2ntermes, chacun´etant de la formexkyn-kpour un certaink=0,1, ,n.

Comme le termexkyn-ks"obtienten choisissantxdanskdesnfacteurs (etypar d´efaut dans lesn-kautres), le nombrede fois que ce terme apparaˆıt dans le d´eveloppement est donc donn´e parnk, le nombre dek-combinaisons de l"ensemble desnfacteurs.On peut ´etablir de nombreuses identit´es `a partir de la formule du binˆome.

En voiciquelques-unes.(i)n0n1n2nn=2n(ii)n0n1n2-···+(-1)nnn=0;(iii)kpairnkkimpairnk=2n-1D´emonstration:Pour les identit´es (i) et (ii), on pose respectivementx=y=1etx=-y= 1 dans led´eveloppement de (x+y)nVoici un argument combinatoire pour (i) : un ensemble `an´el´ements a exactement 2nsous-ensembles; or un sous-ensemble donn´e peut avoir soit 0, soit 1, soit 2, , soitn´el´ements.Exemple:La formule du binˆome permet parfois de raccourcir certains calculs.

En voici un exemple.99963= (10 000-4)3= 10 0003-3·10 0002·4+3·10 000·42-43= 1 000 000 000 000-1 200 000 000 + 480 000-64= 998 800 479 936.40CHAPITRE 1.

UN COFFRE D"OUTILS5.Le principe d"inclusion-exclusion.On a vu pr´ec´edemment que #(A?B)≤#A+#Bpour des ensemblesAetBquelconques.

Leprincipe d"inclusion-exclusionvient pr´eciser la situation en faisantintervenir le nombre d"´el´ements que peuvent avoir en commun les ensembles en cause.Dans le cas de deux ensemblesAetB,ona#(A?B)=#A+#B-#(A∩B).Autrement dit, pour compter le nombre total d"´el´ements de deux ensemblesAetB,on compte le nombre d"´el´ements deA, on lui ajoute le nombre d"´el´ements deBet onsoustrait le nombre d"´el´ements que l"on a compt´e deux fois, `a savoir ceux deA∩B.On a de mˆeme, avec trois ensemblesA,BetC,#(A?B?C)=#A+#B+#C-#(A∩B)-#(A∩C)-#(B∩C)+#(A∩B∩C).ABCLa r`egle se g´en´eralise bien sˆur au cas dekensemblesA1,A2, ,Ak: partant de lasomme #A1+#A2+···+#Ak, on soustrait et on ajoute successivement le cardinaldes intersections de ces ensembles, changeant de signe `a chaque fois qu"on op`ere surun plus grand nombre d"ensembles `a la fois.

En symboles,#(A1?A2?···?An1≤i≤n#(Ai1≤i

Combien ne sont inscrits `a aucun de ces cours?D´esignant parAetEles ensembles d"´etudiants inscrits respectivement en allemand eten espagnol, on a #(A?B)=#A+#B-#(A∩B) = 47 + 35-23 = 59.

Il y a donc8´etudiants inscrits `a aucun des deux cours.1.3.

COMBINATOIRE ET PROBABILIT´ES41(b)Donner le nombre d"entiers positifsk,avec1≤k≤1988, qui sont relativement premiersavec 1988.Comme 1988 = 22·7·71, on introduit les trois ensemblesA,BetCform´es respectivementdes entiers positifs divisibles par 2, par 7 et par 71.

On a donc #A=19882= 994,#B=19887= 284 et #C=198871= 28. Les ´el´ements deA∩Bsont les entiers divisiblespar 2·7 = 14; on a donc #(A∩B)=198814= 142. De mˆeme, #(A∩C)=1988142=14et#(B∩C)=1988497= 4. Enfin,#(A∩B∩C)=1988994= 2.

On obtient donc#(A?B?C)=#A+#B+#C-#(A∩B)-#(A∩C)-#(B∩C)+#(A∩B∩C)= 994 + 284 + 28-142-14-4+2= 1148,de sorte qu"il y a 1988-1148 = 840 entiers r´epondant `a la question.6.Les probabilit´es.La th´eorie des probabilit´es cherche `a quantifier certaines situation reli´ees `a la notionde hasard ou d"incertitude.`A cette fin, on a souvent recours `a la combinatoire afin ded´enombrer les cas pouvant survenir.Consid´erons une certaine exp´erience pouvant se r´ealiser d"un nombre fini de fa¸cons;l"ensemble de tous les r´esultats possibles constitue l"espace ´echantillonnalΩ.

Noussupposons que les r´esultats possibles sont´equiprobables, c"est-`a-dire que la fr´equencede r´ealisation de n"importe quel ´el´ement de Ω est la mˆeme.

Un exemple typique est lelancement d"un d´ehonnˆete.Un´ev´enementest un sous-ensembleE?Ω. Un ´ev´enementEayant ´et´efix´e, un r´esultat(ou cas)favorableest un ´el´ement deE.

Sous l"hypoth`ese d"´equiprobabilit´e, on d´efinit laprobabilit´eP(E)del"´ev´enementEcomme ´etant le quotient de #Epar #Ω, c"est-`a-direle nombre de cas favorables divis´e par le nombre de cas possibles.Exemples:(a) En lan¸cant un d´e honnˆete, la probabilit´e d"obtenir la face 3 est16; la probabilit´e d"obtenirune face paire est3612(b) On lance deux fois une pi`ece de 10/c.

On a alors Ω ={pp,pf,fp,ff}o`uprepr´esentele cˆot´e pile etfle cˆot´e face.

La probabilit´e d"obtenir au moins une face est34, et celled"avoir exactement une face est2412A noter que les r´esultats seraient les mˆemes si on lan¸cait simultan´ement une pi`ece de10/c et une de 25/c, ou encore deux pi`eces de 10/c.(c)On tire 5 cartes d"un jeu de 52 cartes.

D´eterminer la probabilit´e qu"elles soient toutesde la mˆeme couleur (pique, coeur, carreau ou tr`efle).Une main de 5 cartes ´etant un sous-ensemble `a5´el´ements, il y a donc525= 2 598 960mains de 5 cartes possibles.

Une main de 5 cartes d"une couleur donn´ee peut ˆetre form´eede135= 1287 fa¸cons, de sorte qu"il y a en tout 4·1287 = 5148 mains de 5 cartes de lamˆeme couleur.

On a doncP(5 cartes de la mˆeme couleur) =51482 598 960=3316 660,42CHAPITRE 1.

UN COFFRE D"OUTILSce qui est de l"ordre de 0,2%.Autre solution : Choisissons les 5 cartes l"une apr`es l"autre; cela peut donc se faire de52·51·50·49·48 = 311875200 fa¸cons.

Le choix de 5 cartes d"une couleur donn´ee peutse faire de 13·12·11·10·9 = 154 440 fa¸cons, ce qui donne 4·154 440 = 617 760 caspossibles pour