Chapitre 1 : Analyse Combinatoire · Nombre de combinaisons Combinaisons avec répétitions...

Chapitre 1 : Analyse Combinatoire

L2 éco-gestion, option AEM

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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