[PDF] [PDF] 13 Combinatoire et probabilités - Cours

View - Download [PDF] 13 Combinatoire et probabilités - Cours

Previous PDF

Next PDF

1.3. COMBINATOIRE ET PROBABILIT´ES33

1.3 Combinatoire et probabilit´es

Lacombinatoire(ouanalyse combinatoire) est l"´etude des ensembles finis du point de

vue du nombre de leurs ´el´ements. Elle porte sur le d´enombrement de configurations d"objets

satisfaisant 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 origine

dans 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 que A∩B=∅. Alors l"ensembleA?Bcontientm+n´el´ements.

Principe de multiplication :

Soit deux ensemblesAetBcontenant respectivementmetn´el´ements. Alors l"ensemble

A×Bcontientm·n´el´ements.

Il va de soi que chacun de ces principes peut se g´en´eraliser `a un nombre fini quelconque d"ensembles. Ainsi, dans le cas du premier, siA1 ,A 2 ,...,A k forment une partition de l"ensembleE, alors #E=#A 1 +#A2 +···+#A k Le 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= {a 1 ,a 2 ,...,a m }, alorsA×Bpeut se partitionner enmensemblesE 1 ,E 2 ,...,E m ,o`u Ei ={(a i ,b):b?B}. ChaqueE i comprenantn´el´ements, on a #(A×B)=#E 1 +#E 2 +···+#E m =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,

(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 de math´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´esente

le nombre de livres math´ematiques fran¸cais qui peuvent ˆetre consult´es dans nos deux dans 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"OUTILS

Les 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 dem fa¸cons et aussi un objet choisi dans la seconde denfa¸cons, alors le choix d"un objet de 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 dem fa¸cons et aussi un objet choisi dans la seconde denfa¸cons, alors le choix de deux objets, 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 former2 n sous- ensembles.

SoitA={a

1 ,a 2 ,...,a n }.D´eterminer un sous-ensembleXdeArevient `a se demander, pour chaquei=1,2,...,n,sia i ?X. Mais pour chaque ´el´ementa i deA, on a deux possibilit´es:oubienonmeta i dansX, ou bien on ne l"y met pas. Et comme on r´ep`ete un tel choixnfois, on a donc

2×2×···×2

nfois =2 n sous-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 une fl`eche vers le bas indique qu"on ne le prend pas. a a bb c c c cb cc c c b (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) etbpour chacun des autres chiffres, le nombre total de tels entiers est (b-1)·b k-1 (c)Trouver le nombre de nombres impairs dont le d´eveloppement d´ecimal comprend quatre chiffres distincts. On s"int´eresse aux nombres impairs allant de 1000 `a 9999 dont les chiffres sont tous diff´erents. On a donc quatre choix `a faire. Il est plus commode de commencer par le chiffre des unit´es, pour lequel il y a 5 possibilit´es : 1,3,5,7 ou 9. Comme le chiffre des unit´es de mille ne peut ˆetre 0, il reste 8 choix possibles apr`es le choix du chiffre des

1.3. COMBINATOIRE ET PROBABILIT´ES35

unit´es. Le chiffre des centaines peut alors ˆetre choisi de 8 fa¸cons, quels que soient les deux

premiers choix, puis celui des dizaines de 7 fa¸cons. Il y a donc en tout 5·8·8·7 = 2240 nombres r´epondant aux conditions du probl`eme. (d)Trouver le nombre de nombres de 1 `a 1000 dont le d´eveloppement d´ecimal comprend une seule fois le chiffre 3. SoitE, l"ensemble de tous les nombres r´epondant `a la question et consid´erons la partition E=E 1 ?E 2 ?E 3 ,o`u, pourj=1,2,3,E j d´esigne l"ensemble form´e des nombres de Es"´ecrivant avecjchiffres (il n"y a pas de nombre `a 4 chiffres dansE). Clairement #E 1 = 1. Les nombres dansE 2 sont de deux types : (i) ceux dont le chiffre des unit´es est 3, sauf 33 (il y en a 8); (ii) ceux dont le chiffre des dizaines est 3, sauf 33 (il y en a 9). On a donc #E 2 = 8 + 9 = 17. De mˆeme,E 3 comprend des nombres ayant un 3 soit dans la position des unit´es (il y en a 8·9), soit dans celle des dizaines (8·9), soit dans celle des centaines (9·9), de sorte que #E 3 = 72 + 72 + 81 = 225. On a donc #E=#E 1 +#E 2 +#E 3 = 1 + 17 + 225 = 243. (e)Trouver le nombre de nombres dont le d´eveloppement d´ecimal comprend trois fois le chiffre 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 le

chiffre 8 et 4 pour le chiffre 9, les 3 autres ´etant toutes occup´ees par le chiffre 7. Il y a

donc 5·4 = 20 nombres du type demand´e. (f)Trouver le nombre de nombres dont le d´eveloppement d´ecimal comprend trois fois le chiffre 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 fois moins 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 un classement ordonn´eder´el´ements choisis parmi cesn, chaque ´el´ement ne pouvant

servir qu"une seule fois. Il s"agit donc d"une liste ordonn´ee et sans r´ep´etitions. On parle

aussi d"arrangement denobjets prisr`a la fois.Ond´esigne parP(n,r) le nombre de r-permutations denobjets.

Exemple:

P(8,5) = 8·7·6·5·4 = 6720. Cela revient `a faire une liste ordonn´ee de 5 objets choisis parmi

8, 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 positif (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 dans

36CHAPITRE 1. UN COFFRE D"OUTILS

un certain ordre. On a

Exemples:

(a)De combien de fa¸cons peut-on asseoir 10 personnes (i) `a une table d"honneur sur une estrade; (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 9 fa¸cons d"occuper le si`ege `a sa gauche, 8 pour le si`ege suivant, etc. Il y a donc en tout

9! = 362 880 dispositions possibles.

(b)De combien de fa¸cons peut-on asseoir 10 personnes autour d"une table circulaire, s"il y a 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. Faisant asseoirA, 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 de Eest un sous-ensemble deEcontenantr´el´ements. Le nombre der-combinaisons de nobjets se d´esigne par la notationC(n,r)ou n r . (Ce dernier symbole s"appelle un coefficient binomial, car il intervient dans le d´eveloppement du binˆome (x+y) n - voir plus bas.)

Exemple:

4 3 = 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 que n r =0sir>net que 0 r =0sir>0.

On a aussi, pour tout natureln,

n 0 =1, n 1 =net n n =1. La propri´et´e de base des coefficients binomiaux est la suivante : n r

D´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´ements

selon un certain ordre. Or la premi`ere de ces tˆaches peut s"accomplir de n r fa¸cons, et la seconde 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 : n r =n! r!(n-r)!.

1.3. COMBINATOIRE ET PROBABILIT´ES37

Exemples:

(a)On donne dans le plan 25 points tels qu"il n"y en a pas trois d"entre eux qui soient colin´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 donc 25
2 =25!

2!23!= 300.

De mˆeme, le nombre de triangles est

25
3 =25!

3!22!= 2300.

(b)D´eterminer le nombre de mots denlettres comprenant exactementrfois la lettreaque l"on peut ´ecrire avec les deux seules lettresaetb. Cela revient `a choisirrpositions, parmi lesn,o`u on inscrira una; cela peut donc se faire de n r fa¸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´es avec l"alphabet usuel. Les trois positions occup´ees par les voyelles peuvent ˆetre choisies de 8 3 mani`eres. Mais alors les positions des voyelles peuvent ˆetre remplies de 6 3 fa¸cons, et celles des consonnes de 20 5 fa¸cons. Il y a donc en tout 8 3 6 3 20 5 = 38 707 200 000 mots possibles. (d)Montrer que le produit derentiers positifs cons´ecutifs est toujours divisible par le produit desrpremiers entiers positifs. AppelantNle plus grand desrentiers en cause, leur produit estN×(N-1)×···× (N-r+1)=P(N,r). OrP(N,r)=r! N r . Et puisque N r est un entier, il suit que r!|N×(N-1)×···×(N-r+ 1). (e)Montrer que sipest un premier, alorsp| p r pourr=1,2,...,p-1. Comme p r p! r!(p-r)! est un entier, il faut donc que le num´erateurp! soit un multiple du d´enominateur. Maispet le d´enominateur ´etant relativement premiers, cela signifie que (p-1)! r!(p-r)! est un entier. Voici quelques propri´et´es des coefficients binomiaux. Chacune peut se d´emontrer soit par un argument combinatoire bas´e sur l"interpr´etation de n r ,soitparunargument alg´ebrique en termes de la factorielle. (i) n r n n-r (ii) n r =n r· n-1 r-1

38CHAPITRE 1. UN COFFRE D"OUTILS

(iii) n r n-1 r n-1 r-1 (iv) n k k r n r n-r k-r (v) r r r+1 rquotesdbs_dbs29.pdfusesText_35

[PDF] exercice corrigé arrangement combinaison permutation pdf

[PDF] combien de tasse de macaroni par personne

[PDF] 1 tasse de pate cuite calorie

[PDF] portion de pates pour 1 personne

[PDF] portion pates pour 2 personnes

[PDF] 1 tasse de pate en gramme

[PDF] equivalence poids pates crues et cuites

[PDF] quantité de macaroni pour 4 personnes

[PDF] portion macaroni cru par personne

[PDF] la vision des couleurs 1ere s

[PDF] quelles sont les cellules sensibles aux couleurs

[PDF] quels capteurs sont responsables de la perception des couleurs

[PDF] tp image numérique ts correction

[PDF] caractéristique d'une image numérique

[PDF] codage d'une image