[PDF] Chapitre 9 : Dénombrement 14 janv. 2014 1 Cardinaux

View - Download Chapitre 9 : Dénombrement

Previous PDF

Next PDF

Chapitre 9 : Dénombrement

PTSI B Lycée Eiffel

14 janvier 2014

Toute chose est nombre.

Pythagore.

Il y a trois sortes de mathématiciens :

ceux qui savent compter et ceux qui ne savent pas compter.

Introduction

La combinatoire, science du dénombrement, sert comme son nom l"indique à compter. Il ne s"agit bien entendu pas de revenir au stade du CP et d"apprendre à compter sur ses doigts, mais

bien de définir des objets et notations mathématiques permettant de compter le nombre d"éléments

d"ensembles bien trop gros et compliqués pour être dénombrés à la main. Le dénombrement n"a

pas en soi énormément d"intérêt, mais trouvera toute son utilité ensuite en probabilités : dans le

cadre des probabilités finies, la probabilité d"un évènement se calcule en divisant le nombre de cas

favorables par le nombre total de cas possibles, ce qui suppose qu"on sache calculer les nombres de cas en question.

Objectifs du chapitre :

être capable d"analyser correctement un énoncé pour choisir le bon type d"outil de dénombre-

ment, et mener un raisonnement combinatoire clair et rigoureux manipuler sans hésitation les coefficients binomiaux

Quelques exemples de problèmes faisant intervenir les objets que nous allons étudier dans ce cours :

Un tirage de Loto consiste à tirer sept boules dans une urne en contenant49(numérotées de

1à49). Combien y a-t-il de tirages possibles?

Il y a49élèves dans la classe. Quelle est la probabilité qu"il y en ait (au moins) deux parmi

eux qui soient nés le même jour de l"année?

On veut répartir les48élèves d"une classe en16trinômes de colles. Combien y a-t-il de répar-

titions possibles (l"ordre des trinômes ainsi que l"ordre des élèves au sein de chaque trinôme

n"étant pas important)? 1

1 Cardinaux d"ensembles finis

Définition 1.Un ensembleEestfinis"il est en bijection avec l"ensemblef1;2;:::;ng, pour un entier natureln. Cet entiernest alors unique. Il est appelécardinalde l"ensembleE, et on le note card(E), oujEj, ou encore]E.

Remarque1.Cela correspond bien à la notion intuitive d"ensemble dont on peut compter les éléments.

En effet, une bijection deEversf1;:::;ngest simplement une façon d"étiquetter les éléments deE

avec les numéros1,2, ...,n. Proposition 1.SoitEun ensemble fini etFun sous-ensmble deE, alorsFest un ensemble fini, etjFj6jEj, avec égalité si et seulement siE=F.

Démonstration.Cette propriété, comme souvent en ce qui concerne les ensembles finis, est assez

évidente d"un point de vue intuitif, mais pas si simple à démontrer correctement. Nous nous en

tiendrons au point de vue intuitif.Proposition 2.SoientEetFdeux ensembles finis. SiEetFsont en bijection l"un avec l"autre,

ils ont même cardinal. Démonstration.Il existe par hypothèse une bijectionfdeEversF. De plus,Fétant fini, notonsn son cardinal, il existe alors une bijectiongdeFdansf1;:::;ng. L"applicationgf:E! f1;:::;ng est une composée d"applications bijectives, donc est bijective, ce qui prouve queEest de cardinal n.Proposition 3.SoientAetBdeux sous-ensembles d"un même ensemble finiE. AlorsjA[Bj= jAj+jBj jA\Bj. Démonstration.Commençons par constater que dans le cas où les deux ensemblesAetBsont disjoints, on ajA[Bj=jAj+jBj. Vous voulez une démonstration? Soitfune bijection deAdans f1;:::;ngetgune bijection deBdansf1;:::;pg,netpétant les cardinaux respectifs deAet deB. On peut alors construire une bijectionhdeA[Bversf1;:::;n+pgen posant8x2A,h(x) =f(x)et

8x2B,h(x) =g(x)+p(intuitivement, cela revient à garder pour les éléments deAla numérotation

donnée par l"applicationf, et à décaler pour les éléments deBla numérotation donnée parg, de

façon à ne pas utiliser deux fois les mêmes numéros). Une fois ce fait admis, constatons queA[B

est l"union disjointe des trois ensemblesAnB,BnAetA\B. On a donc, en utilisant le résultat que nous venons de démontrer,jA[Bj=jAnBj+jBnAj+jA\Bj. Or,Aétant union disjointe deAnB et deA\B, on a égalementjAj=jAnBj+jA\Bj, ou encorejAnBj=jAj jA\Bj. De même, jBnAj=jBj jA\Bj, donc on obtientjA[Bj=jAj jA\Bj+jBj jA\Bj+jA\Bj, ce qui donne bien la formule annoncée.Théorème 1.Formule du crible de Poincaré. SoientA1,A2, ...,Andes sous-ensembles finis d"un même ensembleE, alors j n[i=1Aij=nX k=1X

16i1<

Proposition 4.La formule de Poincaré étant assez peu lisible, voici ce que ça donne pourn= 3et

n= 4: jA[B[Cj=jAj+jBj+jCj jA\Bj jA\Cj jB\Cj+jA\B\Cj jA[B[C[Dj=jAj+jBj+jCj+jDj jA\Bj jA\Cj jA\Dj jB\Cj jB\Dj jC\

Dj+jA\B\Cj+jA\B\Dj+jA\C\Dj+jB\C\Dj jA\B\C\Dj

2

Démonstration.La preuve de la formule générale, assez technique, se fait par récurrence. On se

contentera de prouver la formule pourn= 3en partant de la proposition précédente :jA[B[Cj= j(A[B)[Cj=jA[Bj+jCj j(A[B)\Cj=jAj+jBj jA\Bj+jCj j(A\C)[(B\C)j= jAj+jBj jA\Bj+jCj jA\Cj jA\Bj+jA\C\B\Cj, ce qui donne bien la formule

annoncée.Exemple :Dans un lycée de300élèves,152savent jouer au poker,83au tarot et51au bridge. De

plus,24savent jouer à la fois au poker et au tarot,14au poker et au bridge, et8au tarot et au

bridge. Enfin,3élèves maitrisent les trois jeux de cartes. Le nombre d"élèves jouant aux cartes est

alors de152 + 83 + 5124148 + 3 = 237. Proposition 5.SoitAun sous-ensemble fini d"un ensemble finiE, alorsjAj=jEj jAj. Démonstration.C"est une conséquence de la formule pour une union :Eest union disjointe deAet deA, doncjEj=jAj+jAj.Proposition 6.SoientEetFdeux ensembles finis, alorsEFest fini, etjEFj=jEj jFj.

Démonstration.Pas de preuve rigoureuse pour celui-ci, simplement une idée de la façon dont ça

marche. Soitnle cardinal deE, ete1;e2;:::;enses éléments,ple cardinal deFetf1;:::;fpses éléments. on peut placer les éléments deEFdans un tableau de la façon suivante :e 1e 2:::e nf

1(e1;f1)(e2;f1):::(en;f1).

..f

p(e1;fp)(e2;fp):::(en;fp)Il y biennpéléments dans le tableau, donc dansEF.2 Listes, arrangements et combinaisons

Définition 2.SoitEun ensemble fini de cardinaln, etp2N. Unep-listed"éléments deE, ou p-uplet d"éléments deE, est simplement un élément deEp.

Remarque2.On peut très bien avoir plusieurs fois le même élément dans unep-liste. Par ailleurs,

l"ordre des éléments de lap-liste est important. Proposition 7.Le nombre dep-listes dans un ensemble de cardinalnvautnp.

Démonstration.C"est une conséquence de la formule de cardinal du produit vue un peu plus haut :

commejEFj=jEj jFj, on ajEpj=jEjp, ce qui prouve bien la propriété.Exemple :On tire dans une urne contenant10boules numérotées de1à10quatre boules succes-

sivement avec remise. Le nombre de tirages possibles est de104= 10 000(il y a répétition possible

à cause des remises, et l"ordre est important). Remarque3.Le nombre dep-listes d"un ensemble ànéléments est aussi le nombre d"applications de l"ensemblef1;:::;pgvers cet ensemble. En effet, se donner une telle applicationfrevient à se

donner les valeurs des imagesf(1),f(2), ...,f(p), c"est-à-dire à se donner une liste depéléments

deE. Définition 3.SoitEun ensemble ànéléments etp2N, on appellearrangementdepéléments deEunep-liste d"éléments distincts deE. Remarque4.L"ordre des éléments est toujours important, par contre on ne peut plus avoir de répétition d"élément dans un arrangement. 3 Définition 4.Soientnetpdeux entiers tels quep6n, on noteApn=n!(np)!=n(n1)(n

2):::(np+ 1).

Proposition 8.Le nombre d"arrangements depéléments dans un ensemble ànéléments vautApn.

Démonstration.Contentons-nous de l"idée intuitive : lorsqu"on construit un arrangement, on an choix pour le premier élément,n1pour le deuxième, ...,np+ 1pour lepème, soit au total

n(n1)(np+ 1) =n(n1):::(np+ 1)(np):::21n(n1):::21=n!(np)!.Exemple :On reprend la même urne que précédemment, mais on tire les quatre boules successive-

ment sans remise. Le nombre de tirages possibles est désormais deA410=10!6! = 10987 = 5 040.

Remarque5.Le nombre d"arrangements depéléments dans un ensemble ànéléments est également

le nombre d"applications injectives def1;:::;pgdansE.

Définition 5.Un arrangement denéléments dans un ensemble ànéléments est aussi appelé

permutation. Il y a doncn!permutations dans un ensemble ànéléments. Exemple :Le nombre d"anagrammes d"un mot peut se calculer à l"aide de permutations. Il faut simplement diviser le nombre total du permutations du mot park!chaque fois qu"une même lettre apparaitkfois dans le mot (ainsi, s"il y a troisEdans le mot, on divise par3!car les permutations qui se contentent d"échanger lesEentre eux ne modifient pas l"anagramme). Par exemple, le nombre d"anagrammes du mot DENOMBREMENT est

12!3!2!2!.

Remarque6.Le nombre de permutations d"un ensemble ànéléments est le nombre d"applications bijectives de cet ensemble dans lui-même.

Définition 6.Unecombinaisondepéléments dans un ensemble finiEànéléments est un sous-

ensemble àpéléments deE. Définition 7.Soientnetpdeux entiers tels quep6n, on appellecoefficient binomiald"indices netple nombren p =n!p!(np)!(qui se lit " p parmi n »).

Remarque7.On pose souventn

p = 0sip > n. Proposition 9.Le nombre de sous-ensembles àpéléments d"un ensemble ànéléments estn p Démonstration.En effet, une combinaison n"est rien d"autre qu"un arrangement dans lequel on a en-

levé l"importance de l"ordre. Autrement dit, chaque combinaison apparaitp!fois quand on dénombre

les arrangements (puisqu"il y ap!façons d"ordonner un ensemble àpéléments), donc le nombre de

combinaisons àpéléments vautAn;pp!=n p

.Exemple :Toujours dans la même urne, on tire désormais quatre boules simultanément. Le nombre

de tirages est10 4 =A4104! = 210. Remarque8.On peut encore une fois interpréter ceci à l"aide d"applications : le nombre de com-

binaisons àpéléments dans un ensemble ànéléments est le nombre d"applications strictement

croissantes def1;:::;pgdansE. En effet, se donner une application strictement croissantefest

équivalent à se donner le sous-ensembleff(1);f(2);:::;f(p)g(l"ordre étant imposé par la croissance

de l"application). 4 Un petit tableau pour résumer les cas d"utilisations de ces trois outils de dénombrement :

L"ordre n"est pas importantL"ordre est important

RépétitionsListes

interdites!coefficients binômiaux!quotient de factorielles3 Propriétés des coefficients binomiaux

Proposition 10.Quelques propriétés des coefficients binomiaux, utiles pour les calculs :

8 n>2,n

0 = 1;n 1 =n;n 2 =n(n1)2

8 k6n,n

k =n nk (propriété de symétrie).

8 16k6n,kn

k =nn1 k1

8 16k6n,n1

k +n1 k1 =n k (relation de Pascal).

Démonstration.Pour le premier point, il suffit de reprendre la définition des coefficients binomiaux :n

0 =n!0!n!= 1;n 1 =n!(n1)!=netn 2 =n!2!(n2)!=n(n1)2 La propriété de symétrie est facile aussi : n nk =n!(nk)!(n(nk))!=n!(nk)!k!=n k . Il

y a également une interprétation combinatoire de ce résultat : choisir un sous-ensemble dekéléments

dans un ensemble ànéléments est équivalent à choisir son complémentaire, qui est constitué denk

éléments, donc il y a autant de sous-ensembles àkéléments et ànkéléments dans un ensemble à

néléments.

Pour la troisième,kn

k =kn!k!(nk)!=n!(k1)!(nk)!, etnn1 k1 =n(n1)!(k1)!(n1k+ 1)!= n!(k1)!(nk)!, les deux quantités sont bien égales.

Enfin, la formule de Pascal :

n1 k +n1 k1 =(n1)!k!(n1k)!+(n1)!(k1)!(nk)! (nk)(n1)! +k(n1)!k!(nk)!=n(n1)!k!(nk)!=n k . La encore, il y a une interprétation

combinatoire. SoitEun ensemble ànéléments etxun élément fixé deE. Les sous-ensembles deE

àkéléments, au nombre den

k , se répartissent en deux catégories : ceux qui contiennentx, qui sont au nombre de n1 k1 puisqu"il restek1éléments à choisir parmi lesn1restants dansE une foisxchoisi; et ceux qui ne contiennent pasx, qui sont au nombre den1 k puisqu"il reste

cette fois-cikéléments à choisir parmi lesn1restants (on n"en a encore choisi aucun). D"où la

formule.Triangle de Pascal :La relation de Pascal permet de calculer les valeurs des coefficients binomiaux

par récurrence, en les répartissant sous forme d"un tableau triangulaire : 5 k= 0k= 1k= 2k= 3k= 4k= 5k= 6k= 7k= 8n= 01 n= 111 n= 2121 n= 31331 n= 414641 n= 515101051 n= 61615201561 n= 7172135352171 n= 818285656562871

Pour obtenir un coefficient du tableau, on fait la somme de celui qui est au-dessus de lui, et de celui

qui est à gauche de celui-ci.

Théorème 2.Formule du binôme de Newton.

Soientaetbdeux réels, etn2N, alors(a+b)n=nX

k=0 n k a kbnk.

Remarque9.On peut obtenir à partir de cette formule le développement d"une différence :(ba)n=

nX k=0 n k (1)kakbnk. En pratique, il suffit d"alterner les signes. Exemple :(a+b)6=a6+ 6a5b+ 15a4b2+ 20a3b3+ 15a2b4+ 6ab5+b6. L"ordre est inversé par

rapport à celui de la formule, mais c"est la façon habituelle d"écrire le développement. Autre exemple :

(12x)5= 152x+10(2x)210(2x)3+5(2x)4(2x)5= 110x+40x280x3+80x532x5.

Démonstration.On va procéder par récurrence sur l"entiern. Pourn= 0, la formule du binome dit

simplement que(a+b)0=0 0 a

0b0, ce qui est vrai (on a1de chaque côté). Supposons la formule

vraie au rangn, on a alors(a+b)n+1= (a+b)(a+b)n= (a+b)nX k=0 n k a kbnkpar hypothèse de

récurrence, donc en développant lea+bet en le faisant rentrer dans la somme, on obtient(a+b)n+1=

nX k=0 n k a k+1bnk+nX k=0 n k a kbn+1k. Effectuons un changement d"indice en remplaçantkpark+1 dans la première somme (on ne touche à rien dans la deuxième) :(a+b)n+1=n+1X k=1 n k1 a kbn+1k+ n X k=0 n k a kbn+1k=n n a n+1b0+nX k=1 n k1 +n k a kbn+1k+n 0 a

0bn+1(on a isolé un terme

dans chaque somme pour pouvoir regrouper les sommes). Maintenant, on reconnait la formule de

Pascal dans la somme, donc(a+b)n+1=an+1+nX

k=1 n+ 1 k a kbn+1k+bn+1. Il ne reste plus qu"à remettre les deux termes isolés dans la somme pour obtenir la formule au rangn+ 1, ce qu"on peut

faire puisqu"ils sont justement égaux aux termes manquants pourk= 0etk=n+ 1.Proposition 11.SoitEun ensemble fini de cardinaln. AlorsP(E)est fini, de cardinal2n.

Démonstration.Le cardinal deP(E)est le nombre de sous-ensembles deE. Or, on sait que, pour tout entierk, il y an k sous-ensembles deEàkéléments, ce qui fait au totalnX k=0 n k sous-ensembles. Cette somme n"est rien d"autre qu"un cas particulier de formule du binôme, poura=b= 1, donc elle vaut(1 + 1)n= 2n. 6

Une autre démonstration possible utilise le fait (démontré dans un chapître antérieur) queP(E)est

en bijection avec l"ensemble des applications deEdansf0;1g(via la fonction caractéristique). En découle quejP(E)j=jf0;1gjn= 2n.

Une troisième démonstration pour la route, par récurrence en utilisant la relation de Pascal. Le fait

que 0X k=0 0 k = 2

0est trivial. Supposons que la formule reste vraie au rangn, alorsn+1X

k=0 n+ 1 k n+1X k=0 n k +n k1 =n+1X k=0 n k +Xk=1nn k = 22n= 2n+1puisque les coefficients binomiaux

sont nuls pourk=1et pourk=n+ 1.Il est maintenant temps de répondre aux trois questions posées en début de chapitre :

C"est une application directe du cours, il y a49

7 = 85 900 584grilles différentes au Loto. Le nombre de choix possibles pour les49dates de naissance des élèves de la classe est36549 puisqu"on a365dates possibles pour chaque élève. Si on ne veutpasde répétition (donc

des élèves tous nés à des dates distinctes), il n"y a plus queA49365possibilités. Autrement

dit, la probabilité que tous les élèves soient nés à des dates différentes vaut

A49365365

40'0:034. La

probabilité qu"au moins deux élèves soient nés le même jour vaut donc environ10:034 = 0:966.

L"existence d"anniversaires simultanés est pratiquement certaine.

Pour constituer le premier trinôme, il faut choisir3élèves parmi les48élèves de la classe. Pour

le deuxième, on choisit3élèves parmi les45restants, et ainsi de suite jusqu"à avoir à prendre3

élèves parmi les3derniers pour le dernier trinôme (autant dire qu"on n"a plus le choix). Reste

à diviser tous ces choix par16!, le nombre d"ordres différents possibles qu"on peut avoir sur les

16trinômes, soit48

3 45
3 42
3 39
3 36
3 33
3 30
3 27
3 24
3 21
3 18 3 15 3 12 3 9 3 6 3 3 3 116!
répartitions possibles. Si on écrit tout sous forme de quotient de factorielles, ça se simplifie beaucoup pour laisser

48!(3!)

1616!
(qui est accessoirement un nombre gigantesque). On peut retrouver ce résultat directement :

on choisit un ordre sur les48élèves (d"où le numérateur), puis on découpe la liste ordonnée de

48élèves en16paquets de3. L"ordre dans chacun des16paquets n"a aucune importance (on

divise donc16fois de suite par3!) et l"ordre des16paquets n"a pas non plus d"importance, donc on divise encore par16!. 7quotesdbs_dbs29.pdfusesText_35

[PDF] LE PLOMB Partie I #8212 Architecture de la matière Partie II

[PDF] Eléments de statistiques

[PDF] Partie 4 - Séquence 1 Diagramme en boîte d 'une série statistique

[PDF] Etude d un cycle frigorifique avec compresseur - Eduscol

[PDF] Exercice physique

[PDF] DIAGRAMME DE L 'AIR HUMIDEpdf

[PDF] Diagrammes potentiel-pH Diagrammes potentiel - Étienne Thibierge

[PDF] Comment faire un graphique ternaire

[PDF] Dialogue - L-Pack

[PDF] Dialogue Internet et moi - Ta-Swiss

[PDF] La récursivité dans le dialogue argumentatif

[PDF] Hotel dialogue

[PDF] Exemples de dialogues

[PDF] Communiquer en anglais dans l 'hôtellerie et la restauration - Decitre

[PDF] GÉRER UNE RÉSERVATION