 Analyse

 Probabilités / Statistique

 Algèbre linéaire

Chapitre 1 — Analyse combinatoire

 1. Introduction

 2. Arrangements

o 2.1. Définition

o 2.2. Arrangements avec répétitions

o 2.3.1 Arrangements sans répétition

 3. Permutations

o 3.1. Permutations sans répétition

o 3.2. Permutations avec répétitions

 4. Combinaisons

o 4.1. Définition

o 4.2. Combinaisons sans remise

o 4.3. Combinaisons avec remise

o 4.4. Propriétés des combinaisons

o 4.4.3 Formule du binôme de Newton

1. Introduction
L’analyse combinatoire est une branche des mathématiques qui étudie comment compter les objets.
Elle fournit des méthodes de dénombrements particulièrement utiles en théorie des probabilités.
Les probabilités dites combinatoires utilisent constamment les formules de l’analyse combinatoire
développées dans ce chapitre. Un exemple des applications intéressantes de cette dernière est la
démonstration du développement du binôme de Newtonutilisé dans le calcul des probabilités
d’une loi binomiale.

2. Arrangements

2.1. Définition

Etant donné un ensemble E de n objets, on appelle arrangements de p objets toutes suites

ordonnées de p objets pris parmi les n objets. Le nombre d’arrangements de p objets pris parmi n est
noté : Apn���.

Remarque : On a nécessairement 1≥p≥n1≥�≥� et n,p∈N�,�∈� Si n<p�<�, alors Apn���

Deux arrangements de p� objets sont donc distincts s’ils diffèrent par la nature des objets qui les
composent ou par leur ordre dans la suite.

Exemples :

1. Une séquence d’ADN est constituée d’un enchaînement de 4 nucléotides [A (Adénine), C

(Cytosine), G (Guanine) et T (Thymine)]. Il existe différents arrangements possibles de deux
nucléotides ou dinucléotides avec p�=2 et n�=4.

2. Le nombre de mots de 5 lettres (avec ou sans signification) formés avec les 26 lettres de
l’alphabet correspond au nombre d’arrangements possibles avec p�=5 et n�=26.

3. Le tiercé dans l’ordre lors d’une course de 20 chevaux constitue un des arrangements
possibles avec p�=3 et n�=20.

Dans les exemples précédents, l’ordre des éléments dans la suite est essentiel. Ainsi pour le deuxième
exemple, le mot NICHE est différent du mot CHIEN.

Mais dans les deux premiers exemples, une base ou une lettre de l’alphabet peut se retrouver
plusieurs fois alors que dans le troisième exemple, les trois chevaux à l’arrivée sont
forcément différents. Il faut donc distinguer le nombre d’arrangements avec répétition et le nombre
d’arrangements sans répétition (arrangements au sens strict).

2.2. Arrangements avec répétitions

Lorsqu’un objet peut être observé plusieurs fois dans un arrangement, le nombre d’arrangement
avec répétition de p� objets pris parmi n�, est alors :
Apn=npavec1≥p≥n���=������1≥�≥�

Voici pourquoi :

Pour le premier objet tiré, il existe n� manières de ranger l’objet parmi n�.

Pour le second objet tiré, il existe également n� possibilités d’arrangements car le premier objet fait
de nouveau parti des n� objets. On parle de tirage avec remise.

Ainsi pour les p� objets tirés, il y aura n×n×n×n×…×n�×�×�×�×…×� (p� fois) arrangements
possibles, soit Apn=n×n×n×....×n=np���=�×�×�×....×�=��
Exemples :

1. Concernant l’exemple de la séquence d’ADN, le nombre de dinucléotides attendus si l’on fait

l’hypothèse qu’une base peut être observée plusieurs fois dans la séquence (ce qui
correspond effectivement à la réalité) est donc : A24�42 = 4242 = 16 dinucléotides
possibles

Les 16 dinucléotides identifiables dans une séquence d’ADN sont :

2.3.1 Arrangements sans répétition

Lorsque chaque objet ne peut être observé qu’une seule fois dans un arrangement, le nombre
d’arrangements sans répétition de p objets pris parmi n� est alors : Apn=n!
(n−p)! avec 1≥p≥n���=�!(�−�)! avec 1≥�≥�

Voici pourquoi : Pour le premier objet tiré, il y a n� manières de ranger l’objet parmi n�.

Pour le second objet tiré, il n’existe plus que n-1 manières de ranger l’objet car le premier objet ne
peut plus être pris en compte. On parle de tirage sans remise.

Ainsi pour les p� objets tirés parmi n�, si 1≥p≥n1≥�≥�, il y aura : Apn=n(n−1)(n−2)....
(n−p+1)���=�(�−1)(�−2)....(�−�+1) (p� produits)

de plus Apn=n(n−1)(n−2)....(n−p+1)(n−p)×....×2×1(n−p)×....×2×1���=�(�−1)(�−2)....(�−�+1)
(�−�)×....×2×1(�−�)×....×2×1

d’où Apn=n!(n−p)!���=�!(�−�)!

Rappel : Si n∈N∗�∈�∗ , on appelle factorielle n�, notée n!�! , le produit des n� premiers
entiers : 1×2×3×.....×p×(p+1)×...×(n−1)×n=n!1×2×3×.....×�×(�+1)×...×(�−1)×�=�!

0!=10!=1 par convention car 0!0! n’est en principe pas définie.

Dès que n� dépasse la dizaine, n!�! se compte en millions. Il est bon de connaître la formule
d’approximation suivante (« formule de Stirling »):

n!≈(ne)n2πn−−−√�!≈(��)�2��

Exemple:

Concernant l’exemple de la séquence d’ADN, le nombre de dinucléotides attendu dans une séquence
si l’on fait l’hypothèse qu’une base n’est observée qu’une seule fois est donc : A24�42 = 4!(4−2)!4!
(4−2)! = 12 dinucléotides possibles

Sous cette contrainte, les 12 dinucléotides possibles sont :

Ceci correspond aux 16 arrangements possibles avec répétition (Apn=np���=��) auxquels sont
soustraits les 4 dinucléotides (n�) résultant de l’association d’une même base.

3. Permutations

3.1. Permutations sans répétition

Etant donné un ensemble E� de n� objets, on appelle permutations de n� objets distincts toutes

suites ordonnées de n� objets ou tout arrangement n� à n� de ces objets. Le nombre de
permutations de n� objets est noté : Pn=n!��=�!

La permutation de n� objets constitue un cas particulier d’arrangement sans

répétition de p� objets pris parmi n� lorsque p=n�=�

Ainsi le nombre de permutations de n� objets est : Ann=n!(n−n)!=n!���=�!(�−�)!=�!

Exemple:

Le nombre de manières de placer 8 convives autour d’une table est : P8=8!�8=8! 40 320 possibilités

3.2. Permutations avec répétitions

Dans le cas où il existerait plusieurs répétitions k� d’un même objet parmi les n� objets, le nombre
de permutations possibles des n� objets doit être rapporté aux nombres de permutations
des k� objets identiques.

Le nombre de permutations de n� objets est alors : Pn=n!k!��=�!�!

En effet, les permutations de k� objets identiques sont toutes identiques et ne comptent que pour
une seule permutation.

Exemple:

Considérons le mot « CELLULE ». Le nombre de mots possibles (avec ou sans signification) que l’on
peut écrire en permutant ces 7 lettres est : P7=7!2!3!�7=7!2!3! = 420 mots possibles

en considérant deux groupes de lettres identiques : L (3 fois) et E (2 fois).

4. Combinaisons

4.1. Définition

Si l’on reprend l’exemple de la séquence d’ADN, à la différence des arrangements où les dinucléotides
AC et CA formaient deux arrangements distincts, ces derniers ne formeront qu’une seule
combinaison. Pour les combinaisons, on ne parle plus de suite ni de série puisque la notion d’ordre
des objets n’est plus prise en compte. On parle alors de tirages avec ou sans remise.

4.2. Combinaisons sans remise

Étant donné un ensemble E� de n� objets, on appelle combinaisons de p� objets tout

ensemble de p� objets pris parmi les n� objets sans remise.

Le nombre de combinaisons de p� objets pris parmi n� est noté : Cpn���

Remarque : On a nécessairement 1≥p≥n1≥�≥� et n,p∈N∗�,�∈�∗ Si n<p�<�,

alors Cpn=0���=0
Exemples : (1) Le tirage au hasard de 5 cartes dans un jeu de 32 (main de poker) est une combinaison
avec p=5�=5 et n=32�=32. (2) La formation d’une délégation de 5 personnes parmi un groupe de
50 constitue une combinaison avec p=5�=5 et n=50�=50.

Pour ces deux exemples, les objets tirés sont clairement distincts.

Le nombre de combinaisons de p� objets pris parmi n� et sans remise est : Cpn=n!p!(n−p)!

���=�!�!(�−�)! notée (np)(��) avec 1≥p≥n1≥�≥�

Voici pourquoi :

Pour calculer ce nombre, on utilise le principe de la division.

• Il y a Apn��� manières de tirer p� objets parmi n� en les ordonnant soit Apn=n!(n−p)!

���=�!(�−�)!

• Une fois les p� objets tirés, il y a p!�! manières de les ordonner.

• Il y a donc Apnp!����! manières de tirer p� objets parmi n� sans les ordonner.

Cpn=Apnp!=1p!n!(n−p)!���=����!=1�!�!(�−�)!

Remarque : A la notation ancienne Cpn���, on préfère parfois la notation moderne (np)(��) .

Les nombres n� et p� constituent les coefficients binomiaux.

Exemples:

Dans le cadre de l’exemple de la séquence d’ADN, le nombre de dinucléotides attendus sans tenir
compte de l’ordre des bases dans la séquence (hypothèse justifiée dans le cas de l’ADN non codant)
est donc : C24=(42)=4!2!(4−2)!=4×32×1=�42=(42)=4!2!(4−2)!=4×32×1= 6 dinucléotides

Les 6 dinucléotides possibles sous cette hypothèse sont :

Ceci correspond aux 12 arrangements possibles sans répétitions (Apn=n!(n−p)!���=�!(�−�)!)

divisé par le nombre de permutations possibles avec 2 nucléotides (Pp=p!��=�!).

4.3. Combinaisons avec remise

Le nombre de combinaisons de p� objet parmi n� avec remise est : Cpn+p−1=(n+p−1)!p!(n−1)!

��+�−1�=(�+�−1)!�!(�−1)!

Voici pourquoi :

Soit la constitution de mots de 3 lettres à partir d’un alphabet à 5 lettres avec remise, on distingue 3
cas possibles :

• C35�53 nombre de mots de 3 lettres différentes et sans ordre

• C25×2�52×2 nombre de mots de 2 lettres différentes et une lettre redondante

• C15�51 nombre de mots de 3 lettres identiques

d’où au total : C35�53 + 2 C25�52+ C15�51 = C37=35�73=35 en utilisant la formule

des combinaisons composées ou formule de Pascal.

en
effet C35+C25=C36�53+�52=�63 et C25+C15=C26�52+�51=�62 d’où C25+C15=C26�52+�5
1=�62 soit $ C_7^3 = 35$ mots possibles de 3 lettres à partir d’un alphabet à 5 lettres.

ainsi C37=C35+3−1=Cpn+p−1�73=�5+3−13=��+�−1� avec n=5 et p=3

4.4. Propriétés des combinaisons

4.4.1. La symétrie

Le nombre de combinaisons de p� objets pris parmi n� étant Cnp=n!p!(n−p)!���=�!�!

(�−�)!, alors

1. C0n=Cnn=1��0=���=1 car C0n=Cnn=n!n!��0=���=�!�!

2. si n≥1C1n=Cn−1n=n�≥1��1=���−1=� car C1n=Cn−1n=n!(n−1)!��1=���−1=�!

(�−1)!

3. si n≥2C2n=Cn−2n==n(n−1)2�≥2��2=���−2==�(�−1)2

avec C2n=Cn−2n=n!2!n−2!=n×(n−1)(n−2)!2!n−2!��2=���−2=�!2!�−2!=�×(�−1)(�−2)!2!
�−2!

Par récurrence, on déduit des relations précédentes, la propriété de symétrie à savoir :

si 0≤p≤nCn−pp=n!p!(n−p)!0≤�≤����−�=�!�!(�−�)! ainsi Cpn=Cn−pn���=���−�

Il revient au même de donner la combinaison des p� objets choisis ou bien celle des (n−p)
(�−�) qui ne le sont pas.

4.4.2 Combinaisons composées ou Formule de Pascal

si 0≤p≤n−10≤�≤�−1 Cp−1n−1+Cpn−1=Cpn��−1�−1+��−1�=���

Voici pourquoi : Parmi les n� objets, on considère un objet en particulier. - Si cet objet fait partie
des p� objets tirés, il y a Cp−1n−1��−1�−1 possibilités de choisir les p−1�−1 autres objets
parmi les n−1�−1 objets restants. - Si en revanche, l’objet ne fait pas partie du tirage, il y
a Cpn−1��−1� possibilités de choisir les p� autres objets parmi les n−1�−1 objets restants.

d’où la relation Cp−1n−1+Cpn−1=Cpn��−1�−1+��−1�=���

Les termes du triangle de Pascal résultent de l’application directe de cette relation.

Pour établir le triangle de Pascal, il suffit de porter les valeurs prises par p� en colonne et celles
prises par n� en ligne (voir tableau ci-dessus). La valeur attribuée à chaque case, Cpn���, est
obtenue en faisant la somme de la valeur de la case située juste au-dessus, Cpn−1��−1� et la
valeur de la case située au-dessus et à gauche Cp−1n−1��−1�−1. Ceci correspond à l’application
de la propriété énoncée précédemment.

Le triangle de Pascal permet d’obtenir par récurrence les coefficients numériques ou coefficient
binomiaux du binôme de Newton.

4.4.3 Formule du binôme de Newton

La formule du binôme de Newton correspond à la décomposition des différents termes de la

puissance nième��è�� du binôme (a+b)(�+�).

∀(a,b)∈R,n∈N,(a+b)n=∑p=0nCpnan−pbp=∑p=0n(np)an−pbp∀(�,�)∈�,�∈�,
(�+�)�=∑�=0������−���=∑�=0�(��)��−���

Elever (a+b)(�+�) à la puissance n� revient à multiplier n� binômes identiques (a+b)(�+�). Le

résultat est une somme où chaque élément est le produit de n� facteurs de type a� ou b� choisi
chacun dans un binôme différent. Les termes sont ainsi de la forme an−pbp��−���. Chacun de
ces termes est obtenu autant de fois qu’il existe de façons de choisir les p� éléments a� parmi
les n�, c’est à dire le nombre de combinaisons Cpn���.

Compte tenu de la symétrie des combinaisons Cpn���, la formule du binôme de Newton peut
s’écrire :
(a+b)n=∑p=0nCpnan−pbp=∑q=0nCqnaqbn−qavecq=n–
p(�+�)�=∑�=0������−���=∑�=0��������−�avec�=�–�

Les coefficients binomiaux, Cpn��� ou (np)(��) qui sont les coefficients de la formule du
binôme de Newton figurent dans de nombreuses formules mathématiques, notamment pour le
calcul des probabilités de la loi binomiale. Ces coefficients peuvent être obtenus facilement à l’aide
du triangle de Pascal.

Exemple:

Le développement de (a+b)6(�+�)6 donne :

(a+b)6=∑p=06(6p)a6−pbp(�+�)6=∑�=06(6�)�6−���

(a+b)6=(60)a6+(61)a5b+(62)a4b2+(63)a3b3+(64)a2b4+(65)ab5+(66)b6(�+�)6=(60)�6+(61)�5�+
(62)�4�2+(63)�3�3+(64)�2�4+(65)��5+(66)�6

L’application du triangle de Pascal(7e ligne) donne directement les valeurs des coefficients
binomiaux :

(a+b)6=a6+6a5b+15a4b24+20a3b3+15a2b4+6ab5+b6(�+�)6=�6+6�5�+15�4�24+20�3�3+
15�2�4+6��5+�6

Remarque : Si l’on pose a=b=1�=�=1, on obtient alors, d’après la formule du binôme de Newton,

(2)n=∑p=0nCpn(2)�=∑�=0����

Or Cpn��� étant le nombre de parties à p� éléments de

l’ensemble E� contenant n� objets, ∑p=0nCpn∑�=0���� représente le nombre de parties ou
partitions de l’ensemble E� que l’on note P(Ω)�(Ω)

Si card E=ncard �=� alors card P(E)=2ncard �(�)=2� (Voir Systeme complet d’évènements)

Le cardinal d’un ensemble (cardcard) correspond au nombre d’éléments constituant cet ensemble.