2. ANALYSE COMBINATOIRE



CALCUL DES PROBABILITÉS

1. Univers des événements

1.1. Axiomes

1.2. Probabilités conditionnelles

1.3. Martingales

2. Analyse combinatoire

1.1. Arrangements avec répétition

1.2. Permutations simples

1.3. Permutations avec répétitions

1.4. Arrangements simples sans répétitions

1.5. Combinaisons simples

1.5.1. Binômiale

1.5.2. Formule de Pascal

3. Chaînes de Markov

"L'analyse combinatoire" est le domaine de la mathématique qui s'occupe de l'étude de l'ensemble des issues, événements ou faits (distinguables ou non tous distinguables) avec leurs arrangements (combinaisons) ordonnés ou non selon certaines contraintes données.

Définitions:

D1. Une suite d'objets (événements, issues, objets,...) est dite "ordonnée" si chaque suite composée d'un ordre particulier des objets est comptabilisée comme une configuration particulière.

D2. Une suite est donc "non ordonnée" si et seulement si nous intéresse la fréquence d'apparition des objets indépendamment de leur ordre.

D3. Des objets (d'une suite) sont dits "distincts" si leurs caractéristiques ne permettent pas de les confondre avec des autres objets.

Remarque: Nous avons choisi de mettre l'analyse combinatoire dans ce chapitre car lorsque nous calculons des probabilités, nous avons également assez souvent besoin de savoir quelle est la probabilité de tomber sur une combinaison ou un arrangement d'événements donnés sous certaines contraintes.

Il existe plusieurs types d'arrangements selon les contraintes et les propriétés des éléments arrangés. Nous allons présenter et démontrer ci-dessous les 5 cas les plus répandus à partir desquels nous pouvons trouver (habituellement) tous les autres :

2.1. ARRANGEMENTS AVEC RÉPÉTITION

Définition: Un "arrangement avec répétition" est une suite ordonnée de longueur m de n objets distincts non nécessairement tous différents dans la suite (soit avec répétition possible!).

Soient A et B deux ensembles finis de cardinaux respectifs m, n tels que trivialement il y ait m façons de choisir un objet dans A (de type a) et n façons de choisir un objet dans B (de type b).

Nous avons vu en théorie des ensemble que si A et B sont disjoints, que: 

equation   (6.34)

Nous en déduisons donc les propriétée suivantes:

P1. Si un objet ne peut être à la fois de type a et de type b et s'il y a m façons de choisir un objet de type a et n façons de choisir un objet de type b, alors il y a equation  façons de choisir un objet de type a ou de type b.

P2. Si nous pouvons choisir un objet de type a de m façons puis un objet de type b de n façons, alors il y a selon le produit cartésien de deux ensembles (cf. chapitre de Théorie Des Ensembles)  :

equation   (6.35)

de manière choisir un seul et unique objet de type a puis un objet de type b.

Avec les mêmes notations, choisir une fonction de A dans B, c'est choisir (dans le cas général) pour chaque élément de A, son unique image parmi les n éléments de B. Il y a donc n façons de choisir l'image equation du premier élément equation de A, puis aussi n façons de choisir l'image equation du deuxième, ..., puis n façons de choisir equation l'image du m-ème. Le nombre d'applications totales possibles de A dans B est donc égal au produit de m égaux à n. Ainsi, nous avons :

equation   (6.36)

equation est l'ensemble des applications de A dans B. La progression du nombre de possibilités est donc géométrique (et non "exponentielle" comme il est souvent dit à tort!).

Ce résultat mathématique est assimilable au résultat non-ordonné (un arrangement equation dont l'ordre des éléments de la suite n'est pas est pris en compte) de m tirages dans un sac contenant n boules différentes avec remise après chaque tirage.

exempleExemples:

E1. Combien de "mots" (ordonnés) de 7 lettres pouvons-nous former à partir d'un alphabet de 24 lettres distinctes (très utile pour connaître le nombre d'essais pour trouver un mot de passe par exemple)? La solution est:

equation   (6.37)

E2. Combien de groupes d'individus aurons-nous lors d'une votation sur 5 sujets et où chacun peut être soit accepté, soit rejeté? La solution (très utilisée dans les entreprises ou en Suisse) est:

equation   (6.38)

Une généralisation simple de ce dernier résultat peut consister dans l'énoncé du problème suivant :

Si nous disposons de m objets equation tels que equation peut prendre equation états différents alors le nombre de combinaisons possibles est:

equation   (6.39)

Et si nous avons equation  alors nous retombons sur :

equation   (6.40)

2.2. PERMUTATIONS SIMPLES (sans répétition)

Définition: Une "permutation simple" (appelée anciennement "substitution") de n objets distincts est une suite ordonnée (différente) de ces n objets par définition tous différents dans la suite (sans répétition).

Attention à ne pas confondre le concept de permutation et d'arrangement!

Le nombre d'arrangements de n éléments peut être calculé par récurrence : il y a n places pour un premier élément, n-1 pour un deuxième élément, ..., et il ne restera qu'une place pour le dernier élément restant.

Il est dès lors trivial que nous aurons un nombre d'arrangements donné par : 

 equation   (6.41)

Rappelons que le produit: 

equation    (6.42)

est appelé "factorielle de n" et nous la notons n! pour equation

Il y a donc pour n éléments distinguables :

equation   (6.43)

arrangements possibles. Ce type de calcul peut être par exemple utile en gestion de projets (calcul de manière différentes de de recevoir dans une chaîne de production n pièces toutes différentes commandées chez des fournisseurs externes).

exempleExemple:

Combien de "mots" (ordonnés) de 7 lettres distinctes sans répétition pouvons-nous former ?

equation   (6.44)

Ce résultat nous amène à l'assimiler au résultat ordonné (un arrangement equation dont l'ordre des éléments de la suite est pris en compte) du tirage de toutes les boules différentes d'un sac contenant n boules distinguables sans remise.

2.3. PERMUTATIONS AVEC RÉPÉTITION

Définition : Lorsque nous considérons le nombre de permutations ordonnées (différentes) d'une suite de n objets distincts tous nécessairement non différents dans une quantité donnée dans la suite nous parlons de "permutation avec répétition".

Remarque: Il ne faut pas confondre cette dernière définition avec "l'arrangement avec répétition"!

Lorsque certains éléments éléments ne sont pas distinguables dans une suite d'objets (ils sont répétitifs dans la suite), alors le nombre d'arrangements (permutations) que nous pouvons constituer se réduit alors assez trivialement à un nombre plus petit que si tous les éléments étaient distinguables.

Soit equation le nombre d'objets du type i, avec:

equation   (6.45)

alors, nous notons :

equation   (6.46)

avec equation le nombre d'arrangements possibles (pour l'instant inconnu) avec répétition (un ou plusieurs éléments répétitifs dans une suite d'éléments sont non distinguables par permutation).

Si chacune des equation places occupées par des éléments identiques était occupée par des éléments différents, le nombre de permutations serait alors à multiplier par chacun des equation (cas précédent). 

Il vient alors que nous retombons sur la factorielle telle que :

equation   (6.47)

alors:

equation   (6.48)

Si les n objets sont tous différentes dans la suite, nous avons alors :

equation   (6.49)

et nous nous retrouvons bien avec une permutation simple (sans répétition) telle que :

equation   (6.50)

Il convient de remarquer que les permutations avec répétition sont en plus petit nombre que celles sans répétition (évident puisque nous ne prenons pas en compte les permutations des éléments identiques entre eux!).

exempleExemple:

Combien de "mots" (ordonnés) pouvons-nous former avec les lettres du mot "mississippi" :

equation   (6.51)

Ce résultat nous amène à l'assimiler au résultat ordonné (un arrangement equationdont l'ordre des éléments de la suite est pris en compte) du tirage de n boules non toutes distinguables d'un sac contenant equation boules avec remise limitée pour chaque boule.

2.4. ARRANGEMENTS SIMPLES SANS RÉPÉTITION

Définition: Un "arrangement simple sans répétition" est une suite ordonnée de p objets tous distincts pris parmi n objets distincts avec equation.

Nous nous proposons donc maintenant de dénombrer les arrangements possibles de p objets parmi n. Nous noterons equation le nombre des ces arrangements.

Il est aisé de calculer equation et de vérifier que equation. Effectivement, il existe n façons de choisir le premier objet et (n-1) façons de choisir le deuxième lorsque nous avons déjà le premier.

Pour déterminer equation, nous raisonnons alors par récurrence. Nous supposons equation connu et nous en déduisons :

 equation   (6.52)

Dès lors: 

equation   (6.53)

alors:

equation  (6.54)

d'où :

equation   (6.55)

Ce résultat nous amène à l'assimiler au résultat ordonné (un arrangement equationdont l'ordre des éléments de la suite est pris en compte) du tirage de p boules d'un sac contenant  n boules différentes sans remise.

exempleExemple:

Soit les 24 lettres de l'alphabet, combien de "mots" (ordonnés) de 7 lettres distinctes pouvons-nous former ?

equation   (6.56)

Le lecteur aura peut-être remarqué que si nous prenons equation nous nous retrouvons avec :

equation   (6.57)

Donc une permutation simple est donc un arrangement simple sans répétition avec equation!

2.5. COMBINAISONS SIMPLES

Définition: Une "combinaison simple" ou "choix" est une suite non-ordonnée (dont l'ordre ne nous intéresse pas!) de p éléments tous différents (pas nécessairement dans le sens visuel du terme!) choisis parmi n objets distincts et est par définition notée equation et appelée la "binomiale". 

Si nous permutons les éléments de chaque arrangement simple de p éléments parmi n, nous obtenons toutes les permutations simples et nous savons qu'il y en a p! d'où en utilisant la convention d'écriture du site :

equation   (6.58)

C'est une relation très souvent utilisée dans les jeux de hasard mais également dans l'industrie via la loi hypergéométrique (cf. chapitre de Techniques De Gestion).

Remarques:

R1. Nous avons nécessairement par définition equation

R2. Selon les auteurs nous inversons l'indice ou le suffixe de C il faut donc être prudent!

exempleExemple:

Soit un alphabet de 24 lettres, combien avons-nous de choix de prendre 7 lettres parmi les 24 sans prendre en compte l'ordre dans lequel sont triées les lettres :

equation   (6.59)

La même valeur peut être obtenue avec la fonction COMBIN( ) de MS Excel.

Ce résultat nous amène à l'assimiler au résultat non ordonné (un arrangement equation dont l'ordre des éléments de la suite n'est pas pris en compte) du tirage de p boules d'un sac contenant n boules différentes sans remise.

Il existe, relativement à la binomiale, une autre relation très souvent utilisée dans de nombreux cas d'études ou également de manière plus globale en physique ou analyse fonctionnelle. Il s'agit de la "formule de Pascal" :

equation   (6.60)

Démonstration:

equation   (6.61)

Or equation donc :

equation   (6.62)

et de même equation :

equation   (6.63)

Ainsi :

equation   (6.64)

equationC.Q.F.D.


page suivante : 3. Chaînes de Markov