23
Chapitre 1 : Analyse Combinatoire L2 éco-gestion, option AEM (L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 1 / 23

Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

  • Upload
    vothuy

  • View
    224

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Chapitre 1 : Analyse Combinatoire

L2 éco-gestion, option AEM

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 1 / 23

Page 2: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Question du jourPensez-vous que dans cette assemblée, deux personnes au moins soientnées le même jour ?

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 2 / 23

Page 3: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

L’analyse combinatoire

L’analyse combinatoire est une branche des mathématiques qui étudiecomment dénombrer des objets.Pourquoi dénombrer ? Ex : comment classer 2 élèves ? 3 ? 4 ? . . .20 ?⇒ comprendre comment compter devient rapidement important.Dénombrement et mathématiques :

Théorie des probabilités : lorsque le nombre de cas possibles est fini,alors la connaissance de ce nombre est primordiale.Combinatoire géométrique : de combien de façons peut-on colorier unecarte avec k couleurs, de telle sorte que deux pays frontaliers soient decouleur différente ? Théorème des quatre couleurs.Théorie des graphes : ex nombre d’Erdös.Triangle de Pascal : comment développer (x + y)8 rapidement ?. . .

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 3 / 23

Page 4: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Plan

1 Un principe de base

2 Nombre d’arrangements

3 Nombre de permutations

4 Nombre de combinaisons

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 4 / 23

Page 5: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Plan

1 Un principe de base

2 Nombre d’arrangements

3 Nombre de permutations

4 Nombre de combinaisons

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 5 / 23

Page 6: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Un principe de base

Exemple 1Dans un magasin, j’ai le choix entre trois ordinateurs portables de mêmedimension et 2 pochettes.Combien ai-je de choix possibles ?

Le principe multiplicatifOn considère deux ensembles finis A et B. On note A×B le produitcartésien de A par B , c’est-à-dire l’ensemble des couples (x ,y) où x estdans A et y est dans B .Le cardinal de A×B est égal au produit des cardinaux de A et de B :

card(A×B) = card(A) · card(B)

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 6 / 23

Page 7: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Principe multiplicatif

Exemple 2Le mot de passe Izly (CROUS,. . .) comporte six chiffres entre 0 et 9.Combien y a-t-il de mots de passe différents ?

Exemple 3Un digicode est composé d’une lettre (A ou B) suivi de 3 chiffres. Combieny a-t-il de codes possibles ?

Exemple 4On veut garer 3 voitures sur un parking de 6 places. Combien y a-t-il depossibilités de trois places vides ? (de garer les voitures ?)

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 7 / 23

Page 8: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Plan

1 Un principe de base

2 Nombre d’arrangements

3 Nombre de permutations

4 Nombre de combinaisons

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 8 / 23

Page 9: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Arrangements

Définition d’un arrangementEtant donné un ensemble E de n objets, un arrangement de k de ces objetsest une suite ordonnée de k objets pris parmi ces n objets.

AttentionOn tient compte de l’ordre des objets.

Exemple 1Combien y a-t-il de podiums de 3 coureurs d’un 100m d’une course de 8coureurs ?(3,7,2) est un arrangement ; (2,7,3) en est un autre.

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 9 / 23

Page 10: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre d’arrangementsArrangements sans répétition

Sans répétitionDans un arrangement sans répétition, les k objets de la liste sonttous distincts.Cela correspond à un tirage sans remise et avec ordre.

Exemple 1Combien y a-t-il de podiums possibles de 3 personnes avec 10 partants ?avec 20 partants ?

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 10 / 23

Page 11: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre d’arrangementsArrangements sans répétition

PropriétéLe nombre d’arrangements sans répétition de k objets parmi n (avec0≤ k ≤ n) est donné par

Akn = n× (n−1)× ...× (n−k +1) =

n!(n−k)!

Exemple 2Combien de nombres de six chiffres peut-on former avec les chiffres les 0,1, 2, 3, 4, 5, 6 et 7, chaque chiffre n’étant présent qu’une fois, et de façonque chaque nombre commence par 7 et soit divisible par 5 ?

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 11 / 23

Page 12: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre d’arrangementsArrangements avec répétition

Avec répétitionDans le cas d’un arrangement avec répétition, les k objets de la listene sont pas nécessairement tous distincts.Cela correspond à un tirage avec remise et avec ordre.

Propriété

Le nombre d’arrangements avec répétition de k objets parmi n est nk .

ExempleCombien de nombres de 6 chiffres peut-on former avec les chiffres 1, 2 et3 ?

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 12 / 23

Page 13: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Des arrangements aux combinaisons......en passant par les permutations

Podiums sans ordreCombien y a-t-il de podiums possibles de 3 coureurs sur 10 partants simaintenant on ne tient plus compte de l’ordre d’arrivée ?

Il s’agit donc de dénombrer (entre autres) des permutations...

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 13 / 23

Page 14: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Plan

1 Un principe de base

2 Nombre d’arrangements

3 Nombre de permutations

4 Nombre de combinaisons

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 14 / 23

Page 15: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de permutationsPermutations sans répétition

Sans répétitionUne permutation sans répétition de n éléments distincts est une suiteordonnée de ces n éléments.Autrement dit, c’est un arrangement de k = n objets pris parmi nobjets.

Exemple 1Le nombre 2537 est une permutation du nombre 3752.

PropriétéLe nombre de permutations de n éléments distincts est An

n = n!.

Exemple 2Combien de nombres de 3 chiffres peut-on former avec 1, 3 et 5 ?

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 15 / 23

Page 16: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de permutationsPermutations avec répétitions

ProblèmeTrouver le nombre de mots que l’on peut former par permutation desdifférentes lettres

1 du mot VAI.2 du mot VIVA.3 du mot AVIVA.4 du mot AVIVAIT.

⇒ la solution passe par la compréhension du nombre de permutations avecrépétitions.

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 16 / 23

Page 17: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de permutationsPermutations avec répétitions

PropriétéConsidérons un ensemble de n objets divisés en p groupes d’élémentsidentiques, les groupes comprenant respectivement n1,n2, ... , et npobjets (on a donc n1+n2+ ...+np = n).Alors le nombre de permutations de cet ensemble est :

n!n1!n2!...np!

Preuve. . .

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 17 / 23

Page 18: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Plan

1 Un principe de base

2 Nombre d’arrangements

3 Nombre de permutations

4 Nombre de combinaisons

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 18 / 23

Page 19: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de combinaisons

DéfinitionUne combinaison de k objets pris dans E est un sous-ensemble de kde ces n objets.L’ordre n’intervient pas.

ExempleLe joueur de poker tire une combinaison de 5 cartes d’un jeu de 52 cartes.L’ordre des cartes ne compte pas.

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 19 / 23

Page 20: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de combinaisonsCombinaisons sans répétition

Une combinaison sans répétition correspond à un tirage sans remiseet sans ordre.

PropriétéLe nombre de combinaisons sans répétition est donné par

C kn =

(nk

)=

Akn

k!=

n!k!(n−k)!

C kn : notation francophone.(nk

): notation anglosaxone.

PreuveMême raisonnement que pour le dénombrement des permutations avecrépétitions.

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 20 / 23

Page 21: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de combinaisonsCombinaisons sans répétition

ExempleDe combien de manières peut-on choisir une délégation de 3 hommes et 2femmes pris parmi un groupe de 7 hommes et 5 femmes ?

RemarqueFormaliser et démontrer la proposition : le nombre de manières de choisir kéléments parmi n (sans ordre) correspond au nombre de manières d’enchoisir n−k parmi n.

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 21 / 23

Page 22: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Combinaisons et triangles de Pascal

Propriété

C kn = C k−1

n−1 +C kn−1, 0≤ k ≤ n

Cette formule permet de démontrer la formule du binôme de Newton :

(x + y)n =n

∑k=0

C kn xkyn−k .

Triangle de Pascal : premières lignes, détail des C kn pour n = 0,1,2,3,4 et

k = 0, . . . ,n1

1 11 2 1

1 3 3 11 4 6 4 1

Exemple (x + y)4 = 1x4+4x3y +6x2y2+4xy3+1y4

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 22 / 23

Page 23: Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions Unecombinaisonavec répétitions correspondaucasd’untiragesans ordre etavec remise. Propriété(admise)

Nombre de combinaisonsCombinaisons avec répétitions

Une combinaison avec répétitions correspond au cas d’un tirage sansordre et avec remise.

Propriété (admise)Le nombre de combinaisons avec répétition de k objets parmi n estC k

n+k−1 =(n+k−1

k

), k étant éventuellement supérieur à n.

ExempleLors d’une soirée, 3 amis munis de 3 "bons pour une boisson" se dirigentvers le bar qui peut délivrer 8 sortes de boissons dénommées ABCDEFGH.Combien de commandes peuvent-ils faire ? [AAB = ABA]

(L2 éco-gestion, option AEM) Chapitre 1 : Analyse Combinatoire 23 / 23