Dénombrement

Médiat

Forum Futura-Science 10 septembre 2021

Réalisé en LATEX
1 Introduction

Un Dérangement

Le Dénombrement (ou Combinatoire) consiste à compter (à dénombrer) les éléments d’un ensemble fini
défini en compréhension.

1.1 Règles de calcul

Nous utiliserons plusieurs fois quelques principes simples de calcul :
Règle du Produit : Une procédure (un comptage par exemple) qui peut être accomplie sous la forme
de deux sous-procédures disjointes, chacune des sous procédures pouvant être réalisées en n1 et n2 manières,
respectivement, peut être réalisée de n1 · n2 manières.
Ce résultat reste valide pour un nombre fini se sous-procédures.

Par exemple pour fabriquer tous les nombres de 2 chiffres, il faut :

1. Choisir le chiffre des dizaines, ce qui peut se faire de 9 façons différentes (le 0 n’est pas acceptable).
2. Choisir le chiffre des unités, ce qui peut se faire de 10 façons différentes (le 0 est acceptable).
3. Ce qui donne 9 · 10 = 90 façons de construire un nombre de deux chiffres.

Règle de la Somme : Une procédure (un comptage par exemple) qui peut être accomplie soit par une
sous-procédure, soit par une autre, ces deux sous-procédures étant exclusive l’une de l’autre, ces sous procédures
pouvant être réalisées en n1 et n2 manières, respectivement, peut être réalisée de n1 + n2 manières.
Ce résultat reste valide pour un nombre fini se sous-procédures.

Par exemple pour fabriquer un nombre de 2 chiffres contenant exactement un 9, on peut

1. Choisir 9 comme chiffre des dizaines et choisir un chiffre des unités différent de 9 (ce qui peut se faire de
9 façons différentes).
2. Choisir 9 comme chiffre des unités et choisir un chiffre des dizaines différent de 9 et de 0 (ce qui peut se
faire de 8 façons différentes).
Ces deux façons de faire sont exclusives l’une de l’autre, on peut donc appliquer la Règle de la Somme,
ce qui donne 9 + 8 = 17 possibilités.
Contrexemple : pour fabriquer un nombre de 2 chiffres contenant au moins un 9, on ne peut pas appliquer
la méthode précédente, en se contentant de dire

1. Choisir 9 comme chiffre des dizaines et choisir un chiffre des unités quelconque, soit 10 possibilités
2. Choisir 9 comme chiffre des unités et choisir un chiffre des dizaines différent de 0, soit 9 possibilités.

En effet les deux sous-tâches ne sont pas exclusives (99 appartient aux deux), et donc on ne peut invoquer
la Règle de la Somme.
La première étape consiste à découper nos solutions en sous-solutions exclusives (cf. l’exemple du principe
d’Inclusion-Exclusion), par exemple, on peut :

1. Choisir 9 comme chiffre des dizaines et choisir un chiffre des unités différent de 9 (ce qui peut se faire de
9 façons différentes).
2. Choisir 9 comme chiffre des unités et choisir un chiffre des dizaines différent de 9 et de 0 (ce qui peut se
faire de 8 façons différentes).
3. Choisir 9 comme chiffre des dizaines et comme chiffre des unités (ce qui ne peut se faire que d’une seule
façon).

Ces trois sous-solutions sont bien exclusives, il est donc possible d’appliquer la Règle de la Somme, ce
qui donne 9 + 8 + 1 = 18 possibilités.

1
 Principe d’Inclusion-Exclusion : Sous ce nom on trouve des formules permettant de calculer le cardinal
d’une union d’ensembles.
Par exemple :
A∪B = A + B − A∩B
A∪B∪C = A + B + C − A∩B − B∩C − C ∩A + A∩B∩C
Et d’une façon plus générale :
n
[ X6
X =∅ \
Ai = (−1) X +1
. Ai
i=1 X⊆J1,nK i∈X

De la première relation, et en remarquant que A = (A \ B) ∪ (A ∩ B) et (A \ B) ∩ (A ∩ B) = ∅, on peut

calculer appliquer la première formule et obtenir A = (A \ B) + (A ∩ B) , d’où

A \ B = A − (A ∩ B)

Par exemple, pour compter le nombre de nombres de 2 chiffres dont au moins un 9, on peut :

1. On pose A = l’ensemble des nombres dont le chiffres des dizaines est 9 ; A = 10 (cf. supra).
2. On pose B = l’ensemble des nombres dont le chiffres des unités est 9 ; B = 9 (cf. supra).
3. A ∩ B = {99} ; A ∩ B = 1

En appliquant le principe d’Inclusion-Exclusion, on obtient :

A ∪ B = A + B − A ∩ B = 10 + 9 - 1 = 18.

Deux notions importantes sont souvent présentes dans les problèmes de dénombrement :

1. La notion de sous-ensemble.
2. La notion de liste ordonnée (ou de n-uple, ou de multiplet).

Par exemple le sous ensemble {1, 2, 3} est égal au sous-ensemble {2, 3, 1}, puisqu’un sous-ensemble n’est
défini que par les éléments qui le compose, et non l’ordre dans lequel nous les énonçons.
Au contraire le triplet (1, 2, 3) est bien différent du triplet (2, 3, 1), puisque dans ce cas, l’ordre intervient.
Par exemple une association qui cherche à désigner 3 membres pour constituer une commission de réflexion,
a besoin de définir un sous-ensemble de ses membres, puisque les 3 membres choisis joueront le même rôle ; que
la commision soit constituée de a, de b et de c, revient au même que de dire que la commission est constituée de
b, de c et de a ; au contraire si cette association cherche à désigner un Président, un Secrétaire et un Trésorier,
il faut bien choisir un triplet et non plus un sous-ensemble, car dire que a est Président, b Secrétaire et c
Trésorier, ce n’est pas la même chose que de dire que b est Président, c Secrétaire et a Trésorier.

2
 On peut représenter graphiquement cette différence :

× c

× × ×
a b c
× a × b

Sous-ensemble à 3 éléments Liste ordonnée de 3 éléments

Principe des tiroirs Si au moins k + 1 objets doivent être placés dans k boı̂tes, alors il y a, au moins,
une boı̂te qui contient au moins 2 objets.

Principe des tiroirs généralisé lnm

Si n objets doivent être placés dans k boı̂tes, alors l’une au moins contient au moins objets.
k

1.2 Conventions utilisées dans ce document

Nous ferons précéder les définitions formelles du symbole h et les définitions un peu plus intuitives, du
symbole K.

E = Cardinal de E.
J1 ; nK = [1 ; n] ∩ N (l’ensemble des entiers compris entre 1 et n).

2 Permutation
2.1 Définitions

h Définition : Une Permutation (sans répétition) d’un ensemble de cardinal n est une bijection de cet
ensemble dans lui-même.

On peut donner une définition plus intuitive : Soit E un ensemble de cardinal n ; par définition du cardinal
il existe une bijection 1 ϕ : J1 ; nK 7−→ E. Cette bijection induit un ordre sur E défini par (le symbole ≺ se lit
 précède )

∀x ∈ E ∀y ∈ E((x ≺ y) ⇔ (ϕ−1 (x) < ϕ−1 (y)))

Il est facile de comprendre ce point si on se représente la bijection ϕ comme une façon de coller un N◦ sur
chaque élément de E, alors on peut dire que x précède y si le N◦ de x est plus petit que celui de y.
Soit f une permutation de E, cette bijection induit un autre ordre sur E, en effet, f ◦ ϕ : J1 ; nK 7−→ E
est une bijection (comme composition de bijections).
1. Il en existe plusieurs, en général, il suffit d’en choisir une.

3
 La réciproque est vraie : si ψ est une bijection ψ : J1 ; nK 7−→ E, alors ϕ ◦ ψ −1 est une bijection de E dans
E, c’est à dire une permutation.
Ces remarques permettent de donner une autre définition, moins formelle, d’une permutation :

Une Permutation de E est une suite ordonnée des n éléments de E, c’est à dire une façon de choisir le
N◦ que l’on colle sur chaque élément de E.
K C’est aussi une façon de ranger (donc l’ordre importe) les n éléments d’un ensemble E, une et une seule
fois (sans remise).

Nous noterons Pn le nombre de permutations d’un ensemble de cardinal n.

h On peut remarquer qu’il n’y a qu’une seule bijection de l’ensemble vide dans lui-même (c’est l’application
vide), et donc P0 = 1.

K On peut remarquer qu’il n’y a qu’une seule façon de ranger

P0 = 1.
 aucun élément  (ne rien faire), et donc

On peut noter que P1 = 1, car il n’y a qu’une seule façon de ranger un seul objet (et, bien sûr, il n’y a
qu’une seule bijection d’un singleton dans lui-même).

Pour le calcul général de Pn , on peut remarquer que pour ranger les n éléments de l’ensemble E, c’est
à dire pour attribuer un N◦ à chacun des n éléments d’un ensemble, on peut commencer par choisir le N◦
du premier élément parmi les n N◦ disponibles (soit n possibilités), puis attribuer un N◦ aux n − 1 éléments
suivants, nous pouvons appliquer la Règle du Produit à ces deux sous-tâches, et on obtient : Pn = n·Pn−1 .
On aurait pu raisonner dans l’autre sens : on peut commencer par choisir l’élément de E auquel on attribue
le N◦ 1 (soit n possibilités), puis on attribue les n−1 N◦ restant aux éléments restants, nous pouvons appliquer
la Règle du Produit à ces deux sous-tâches, et on obtient : Pn = n·Pn−1 .
En itérant le résultat précédent on obtient Pn = n · (n − 1) · · · · · 2 · 1, ce qui s’écrit de façon plus concise :
Pn = n! 2

Comme nous avons vu que P0 = 1, ce qui peut aussi s’écrire : 0! = 1.

Pour
 n les valeurs élevées de n, il peut être pratique d’utiliser une valeur approximative (formule de Stirling) :
n√
n! ≈ 2πn.
e
Cette formule donne un résulat correct à 0,8 % pour n = 10, à 0,2 % pour n = 50 et 0,08 % pour n = 100.
2. n! se lit n-factoriel, ou factoriel n.

4
 Pour compter directement le nombre de permutation d’un ensemble E de cardinal n, il suffit donc de
compter les bijections entre J1 ; nK et E ; et même, pour se simplifier les notations, de compter les bijection de
J1 ; nK dans lui-même, ce que nous allons faire sous la forme d’un arbre des possibles.

4 2 / ··· / n
2 3 / ··· / ···

.
/ .. / ··· / ···
E1

, / ··· / 2
n
(n − 1) choix 1 choix

4 1 / ··· / n
2 3 / ··· / ···

.
/ .. / ··· / ···
8 2

, / ··· / 1
n
(n − 1) choix 1 choix
∅
..
6 . / ··· / ···
.
3 .. / ··· / ···

% . .
.. / .. / ··· / ···

+ .. / ··· / ···
.

(n − 1) choix 1 choix

4 1 / ··· / n−1
2 2 / ··· / ···

 .
/ .. / ··· / ···
n

+ / ··· / 1
n−1
n choix (n − 1) choix 1 choix

En appliquant la Règle du Produit, on obtient directement Pn = n · (n − 1) · · · · · 2 · 1.

2.2 Exemples simples

Exemple 1. On dispose de 3 bandes de tissu de même taille, une Jaune, une Noire et une Rouge, combien
de drapeaux peut-on fabriquer avec ces trois bandes disposées verticalement ?
Choisir un drapeau c’est choisir, dans l’ordre, les 3 bandes de tissu qui vont le constituer, c’est aussi établir
une bijection f : J1; 3K 7−→ {Jaune, Noire, Rouge} (choisir la bande de tissu recevant le N◦ 1, celle qui reçoit
le N◦ 2 et celle qui reçoit le N◦ 3).

5
 La réponse est immédiate : 3 ! = 6 drapeaux différents, vérifions-le en donnant la liste :

(Jaune, Rouge, Noire) (Jaune, Noire, Rouge)

(Noire, Jaune, Rouge) (Noire, Rouge, Jaune)
(Rouge, Noire, Jaune) (Rouge, Jaune, Noire)

Exemple 2. Combien de mots différents peut-on écrire en utilisant une et une seule fois chacune des lettres
du mot  NYMPHES  ?

On peut visualiser cet exercice comme un simple problème de Scrabble c : on dispose des sept jetons :

N Y M P H E S
On veut, dans un premier temps, compter le nombre de mots de 7 lettres que l’on peut fabriquer avec ces
pièces (que le mot soit, ou non, dans le dictionnaire).
Les septs lettres étant différentes, chaque façon de placer ces jetons sur le chevalet correspond à un mot
différent de tous les autres, il s’agit bien de choisir un ordre pour ces sept jetons (c’est à dire une bijection
J1 ; 7K 7−→ {N, Y, M, P, H, E, S}, soit P7 = 7 ! = 5040 mots différents.

Exemple 3. De combien de façons peut-on classer les 32 cartes d’un jeu constitué de 8 ♣, 8 ♦, 8 ♥ et 8 ♠ ?
De combien de façons peut-on classer ces cartes en 4 paquets (posés de gauche à droite devant-soi) de 8 cartes
de la même couleur ?

La première question est une application immédiate de la définition, la réponse est donc
P32 = 32 ! = 263 130 836 933 693 530 167 218 012 160 000 000.
Pour la deuxième question, il suffit de décomposer la tâche de construction de ces paquets en sous-tâches :
Construire un classement en 4 paquets de 8 cartes revient à :

1. Choisir l’ordre des 4 couleurs : P4 = 4 ! = 24 possibilités.

2. Choisir l’ordre des 8 ♣ dans son paquet, soit P8 = 8 ! = 40 320 possibilités.
3. Choisir l’ordre des 8 ♦ dans son paquet, soit P8 = 8 ! = 40 320 possibilités.
4. Choisir l’ordre des 8 ♥ dans son paquet, soit P8 = 8 ! = 40 320 possibilités.
5. Choisir l’ordre des 8 ♠ dans son paquet, soit P8 = 8 ! = 40 320 possibilités.

En appliquant la règle du produit, on obtient :

P4 × P8 × P8 × P8 × P8 = 4 ! × 8 ! × 8 ! × 8 ! × 8 ! = 63 429 799 040 778 240 000.

3 Arrangement
3.1 Définitions

h Définition : Un p-Arrangement (sans répétition) d’un ensemble de cardinal n (où p ≤ n) est une injection
de J1 ; pK dans cet ensemble.

K Définition : Un p-Arrangement (sans répétition) d’un ensemble E de cardinal n (où p ≤ n) est une liste
ordonnée de p éléments, tous différents, choisis parmi les n éléments de E.

On peut remarquer qu’un n-Arrangement d’un ensemble à n éléments est une permutation de cet ensemble,
d’ailleurs, comme pour les permutations, un arrangement correspond à un tirage ordonné, sans remise.

6
 Définition : Soient E un ensemble fini de cardinal n et p un entier naturel plus petit que n. Un p-

K arrangement de E (ou p-arrangement sans répétition de E, ou encore arrangement sans répétition de n

éléments pris p à p) est un p-uplet (a1 , a2 , ..., ap ) d’éléments de E (c’est donc un élément de E n ) tel que
ai 6= aj quel que soit i, j ∈ J1, pK avec i 6= j.

p
Le calcul du nombre de p-Arrangements d’un ensemble de cardinal n qui est noté An , se fait sur le même
modèle que pour les permutations :
Pour constituer une liste ordonnée de p éléments distincts choisis parmi les n éléments de E, on peut
commencer par choisir l’élément de E que l’on place en premier (autrement dit : auquel on attribue le N◦ 1),
soit n possibilités, puis on crée une liste ordonnée de p−1 éléments choisis parmi les n−1 éléments restants que
l’on place derrière le N◦ 1, nous pouvons appliquer la Règle du Produit à ces deux sous-tâches, et on obtient :
p p−1
An = n·An−1 .
p
En itérant p fois le résultat précédent, on obtient An = n · (n − 1) · · · · · (n − (p + 1)), ce qui peut s’écrire
plus simplement :

p n!
An =
(n − p)!

h Une question qui vient naturellement, est se demander combien de uplets peut-on fabriquer avec n-
éléments (c’est à dire le nombre de 0-uplet, de 1-uplet etc.)..

Pour illustrer cette question on peut reprendre l’exemple précédent sur le simple problème de Scrabble c :
on dispose des sept jetons :

N Y M P H E S
Combien de mots (dans un sens très large, puisque l’on considère les mots de 1 lettre, et même le mot vide,
et bien sûr, on ne tient pas compte de l’existence ou non du mot formé, dans le dictionnaire) quelque soit leur
longueur peut-on former avec ces 7 lettres ?
n n
X p X n!
Autrement dit nous voulons calculer, dans le cas général, Wn = An = .
p=0 p=0
(n − p)!
n n n
X n! X 1 X1
Wn = = n! = n!
p=0
(n − p)! p=0
(n − p)! p=0
p!
∞
X 1
Or =e
p=0
p!
0
Calculons, pour n > 0 (on peut calculer W0 = An = 1) :
∞
X 1
en! - Wn = n!
p=n+1
p!
1 1 1
= + + ···
n + 1 (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)
1 1 1
< + + · · · (suite géométrique)
n + 1 (n + 1)2 (n + 1)3
1 1
< ·
n+1 1
1−
n+1
1
<
n

7
 1
D’où on déduit : en! − 1 < en! − < Wn < en!, et finalement Wn = ben!c 3
n
Et donc, dans l’exemple précédent, nous aurions trouvé : b7!ec = 13700.
p
En écrivant (en appliquant la définition de An ) Wn = 1 + n + n(n − 1) + n(n − 1)(n − 2) + · · · + n! et donc
Wn = 1 + n(1 + (n − 1) + (n − 1)(n − 2) + · · · + (n − 1)!), comme dans 1 + (n − 1) + (n − 1)(n − 2) + · · · + (n − 1)!
on reconnaı̂t Wn−1 , on peut en déduire la relation de récurrence : Wn = 1 + nWn−1 .

On peut noter les formules (qui se démontrent par l’application de la formule de calcul, ou qui ont été déjà
vues, voir éventuellement Exercices résolus) :
p p−1
• An = nAn−1
p p p−1
• An = An−1 + pAn−1
• Wn = 1 + nWn−1
• Wn = ben!c

3.2 Exemples simples

Exemple 4. Les exemples classiques sont les courses de chevaux (sans ex-æquo), comme le tiercé, le quarté
ou le quinté :
3 4 5
Avec 20 partants, on trouve respectivement : A20 = 6 840, A20 = 116 280 et A20 = 1 860 480.

Exemple 5. De combien de façons peut-on placer les 26 lettres de l’alphabet de telle sorte qu’il y ait exactement
10 lettres entre A et Z :
Pour placer les 26 lettres conformément à l’énoncé, on peut commencer par choisir dans quel ordre les
lettres A et Z, seront placés, donc choisir l’ordre de 2 objets (P2 possibilités), puis il faut placer dans un
10
certain ordre, 10 lettres parmi les 24 restantes (A24 possibilités), enfin il faut choisir l’ordre de ce bloc de 12
lettres et les 14 lettres restantes, soit 15 objets à ordonner (P15 possibilités).
10
Soit finalement P2 · A24 · P15 = 2 * (7 117 005 772 800) * (1 307 674 368 000) possibilités.

4 Combinaison
4.1 Définitions
Définition : Une Combinaison d’un ensemble de cardinal n est un sous-ensemble de cet ensemble, plus
h précisément, une p-Combinaison d’un ensemble de cardinal n est un sous-ensemble de cardinal p de cet
ensemble.

Une Combinaison de p objets parmi n est une façon de choisir p objets parmi n objets disponibles. Les
K p objets sont pris en une seule fois (une seule poignée, par exemple), il n’est donc pas possible de définir
un ordre naturel parmi ces objets. Il s’agit donc d’un tirage sans remise et sans tenir compte de l’ordre.
p
Le nombre de p-Combinaisons d’un ensemble de cardinal n se note np ou Cn cette dernière notation est

la plus courante au lycée, aussi est-ce celle-ci que nous utiliserons ici.

On peut remarquer que pour définir un arrangement de p éléments pris parmi n, il faut choisir un sous-
p p
ensemble à p éléments, puis choisir une permutation de ces p élements, on obtient la formule : An = Cn ×
Pp
p
p An n!
Cn = =
p! p!(n − p)!
3. La notation bxc désigne la partie entière de x, autrement dit, le plus grand entier plus petit ou égal à x.

8
 On peut noter les formules (qui se démontrent par l’application de la formule de calcul) :
p n−p
• Cn = Cn
p p−1 p
• Cn = Cn−1 + Cn−1
p p−1
• p · Cn = n · Cn−1
On peut calculer la somme de toutes les combinaisons de p objets parmi n, pour p variant de 0 à n,
n
X p
autrement dit Cn , ce qui revient à calculer le nombre de sous-ensembles d’un ensemble à n éléments 4 , on
p=0
obtient donc la formule :
n
X p
• Cn = 2n
p=0

4.2 Exemples simples

Exemple 6. Combien existe-t-il de grille au loto ?

Le jeu de loto (nouvelles règles) consiste à choisir 5 N◦ parmi les 49 disponibles, et 1 parmi 10, pour
5
faire une grille, il faut choisir 5 N◦ parmi les 49 possibles (soit C49 ), puis choisir un N◦ chance parmi les 10
1
disponibles (soit C10 ), en appliquant le principe du produit, on obtient :
5 1
C49 × C10 = 1 906 884 × 10 = 19 068 840.

Exemple 7. De combien de façons peut-on choisir 2 ♣, 2 ♠ et 1 autre carte dans un jeu de 32 cartes (8 de
chaque couleur).
2 2
Il faut choisir les 2 ♣ parmi les 8 disponibles (soit C8 ), puis les 2 ♠ parmi les 8 disponibles (soit C8 ) et
1
enfin il faut choisir 1 carte parmi les 16 autres (soit C16 ), en appliquant le principe du produit, on obtient :
2 2 1
C8 × C8 × C16 = 28 × 28 × 16 = 12 544.

Exemple 8. Binôme de Newton : développer (x + y)n .

Multiplier (x + y) n fois par lui-même, consiste à choisir dans chacun des n facteurs, soit x, soit y, et, bien
sûr, si on choisit k fois x, il faut, ipso facto, choisir n − k fois y, il faut donc choisir k facteurs parmi les n
k
disponibles, soit Cn façons de les choisir ; ensuite il faut choisir les n − k facteurs dans lesquels on choisit y,
n−k
parmi les n − k facteurs restant, soit Cn−k = 1, d’où le résultat :
n n
X k n−k X k
(x + y)n = Cn xk Cn−k yn−k = Cn xk yn−k
k=0 k=0

5 Permutation avec Répétitions

5.1 Définitions

h Soit n1 , n2 , ..., np , p nombres entiers naturels tels que n1 + n2 + ... + np = n, une Permutation avec
Répétition est une surjection de ϕ : J1 ; nK 7−→ J1 ; pK, telle que ϕ−1 ({i}) = ni .

Une Permutation avec Répétition est une liste ordonnée des éléments de E (de cardinal n), le iième élément
pouvant être répété ni .
K Une permutation de n éléments de E avec n1 , n2 , ..., np répétitions, est un n-uplet d’éléments de E dans
lequel chacun des éléments x1 , x2 , ..., xp de E apparaı̂t n1 , n2 , ..., np fois.
n ,n2 ,...,np
La notation la plus usuelle est Cn1 (avec n1 + n2 + · · · + np = n).
4. Voir les exercices des Arrangements avec Répétitions

9
 Pour fabriquer une permutation avec répétitions, il faut :
• Choisir les n1 positions de l’élément N◦ 1, parmi les n positions disponibles.
• Choisir les n2 positions de l’élément N◦ 2, parmi les n − n1 positions disponibles.
• Choisir les n3 positions de l’élément N◦ 3, parmi les n − n1 − n2 positions disponibles.
• ...
• Choisir les np positions de l’élément N◦ p, parmi les n − n1 − n2 − · · · − np−1 positions disponibles.
En appliquant la règle de la somme, on obtient :
n ,n2 ,...,np n n n
C n1 = Cn1 Cn−n
2
1
p
. . .Cn−n1 −n2 −···−np−1

On peut vérifier la formule suivante (par une simple application de la formule de calcul) :
n ,n2 ,...,np n!
• Cn1 =
n1 !n2 ! . . . np !

Une autre façon, un peu plus  tordue , de définir une permutation avec répétition :
Soit E un ensemble tel que E = n. Soit ∼ une relation d’équivalence sur E qui définit une partition de
E en p classes, de cardinal respectif : (n1 , n2 , . . . , np ) (c’est une façon de définir un multi-ensemble).
h Soit E, l’ensemble des bijections de J1 ; nK dans E, et ≈ la relation définie sur E, par
∀f ∈ E ∀g ∈ E (f ≈ g) ⇔ ∀x ∈ J1 ; nK(f (x) ∼ g(x))
Une permutation avec répétition de E est alors un élément de E / ≈.

5.2 Exemples simples

Exemple 9. Combien de mots différents peut-on écrire en utilisant une et une seule fois chacune des lettres
du mot  DEESSES  ?
On peut visualiser cet exercice comme un simple problème de Scrabble c : on dispose des sept pièces :

D E E S S E S
On veut compter le nombre de mots de 7 lettres que l’on peut fabriquer avec ces pièces (que le mot soit,
ou non, dans le dictionnaire).
Cette fois certaines lettres sont répétées, il va de soi qu’interchanger deux jetons portant la même lettre ne
change pas le mot composé, nous sommes bien ici dans le cas d’une permutation avec répétition.
On peut refaire complètement le raisonnement : choisir un mot consiste à :
3
1. Choisir 3 positions pour les 3 E, revient à choisir 3 positions parmi les 7 possibles, soit C7 = 35 positions
3
2. Choisir 3 positions pour les 3 S, revient à choisir 3 positions parmi les 4 restantes, soitC4 = 4 positions
1
3. Choisir 1 position pour le D, revient à choisir 1 position parmi la position restante, soit C1 = 1 position
3 3 1
La règle du produit amène au résultat : C7 × C4 × C1 = 140 (à comparer aux 5040 solutions pour le mot
NYMPHES).
On peut remarquer que l’ordre dans lequel se fait la décision n’a pas d’importance :
1
1. Choisir 1 position pour le D, revient à choisir 1 position parmi les 7 possibles, soit C7 = 7 position
3
2. Choisir 3 positions pour les 3 E, revient à choisir 3 positions parmi les 6 restantes, soit C6 = 20 positions
3
3. Choisir 3 positions pour les 3 S, revient à choisir 3 positions parmi les 3 restantes, soit C3 = 1 position
1 3 3
Ce qui donne bien C7 × C6 × C3 = 140.

On aurait pu, aussi, utiliser directement la formule établie ci-dessus :

1,3,3 7!
C7 = = 140
1!3!3!

10
 Exemple 10. Développer (x1 + x2 + · · · + xp )n =, sur le modèle du  Binôme de Newton .

Lorsque l’on développe (x1 + x2 + · · · + xp )n , on doit choisir, dans chacun des n facteurs, quel élément on
n
choisit (parmi x1 à xp ), ce qui donne un facteur de la forme xn1 1 xn2 2 xn3 3 . . . xp p , où n1 +n2 +· · ·+np = n, facteur
que l’on peut fabriquer de plusieurs façons différentes : il faut chosir les n1 facteurs parmi n dans lesquels on
choisira l’élément x1 , puis il faut chosir les n2 facteurs parmi n − n1 dans lesquels on choisira l’élément x2 etc.,
d’où le résultat : X  n ,n ,··· ,n 
(x1 + x2 + x3 + · · · + xp )n = Cn1 2 xn1 1 xn2 2 xn3 3 . . . xnp p
p

n1 +n2 +n3 +...+np =n

6 Arrangement avec Répétition

6.1 Définitions

h Un p-Arrangement avec Répétition de E est une application quelconque ϕ : J1 ; pK 7−→ E.

Autrement dit, un p-arrangement avec répétition de E est une façon de donner zéro, un ou plusieurs No aux
éléments de E.

K Un p-Arrangement avec Répétition de E est une façon de définir un ordre sur p éléments choisis dans E,
un même élément pouvant être répété jusqu’à p fois.

Pour fabriquer une application de ϕ : J1 ; pK 7−→ E, il faut choisir une image parmi les n possibles,  pour
1 p

chacun des p éléments de J1 ; pK, autrement dit, il faut faire p fois le choix d’un élément parmi n, soit Cn .
En notant αpn le nombre de p-Arrangements d’un ensemble de cardinal n, on obtient :
αpn = np
6.2 Exemples simples
Exemple 11. Combien existe-t-il de codons différents dans l’ARN ; un codon = 3 nucléotides dans un ordre
spécifique, choisis parmi les 4 disponibles représentés par leur base azotée (A(dénine), G(uanine), C(ytosine)
et U(racile)).

On peut donc poser E = {A, G, C, U } et p = 3, en effet, définir un codon revient à décider quel est le
premier nucléotide (choisi parmi les 4), puis choisir le deuxième (parmi les 4), et enfin le troisième (toujours
parmi les 4) ; définir un codon, c’est donc, très exactement définir une application ϕ : J1 ; 3K 7−→ {A, G, C, U }.
Pour trouver le nombre de codons possibles, il suffit donc d’appliquer la formule ci-dessus, ou remarquer
que l’on peut appliquer la règle du produit, chacune des sous-tâches (chaque choix de nucléotide) pouvant
3
α
se réaliser de 4 façons différentes, on trouve donc 4 = 43 , ce qui correspond bien à 4 × 4 × 4.
Exemple 12. Combien existe-t-il de sous-ensemble d’un ensemble de cardinal n ?
Soit E un ensemble de cardinal n, on peut définir un sous ensemble de E en disant, pour chacun des
éléments de E, s’il appartient ou non à ce sous-ensemble ; une façon de  dire  si un élément appartient ou
non à ce sous ensemble est de lui attribuer une étiquette  IN  s’il est dedans, et une étiquette  OUT  s’il
n’est pas dedans, autrement dit, on définit un sous-ensemble de E en établissant une application de E dans
l’ensemble des étiquettes : { IN ,  OUT }.
Par définition le nombre de ces applications est αn2 = 2n.
Il est plus habituel d’utiliser {0, 1} à la place de { IN ,  OUT }, mais c’est, évidemment, la même
chose.
n
X p
On peut noter que ce résultat permet de démontrer le résultat vu plus haut : Cn = 2n .
p=0

11
 7 Combinaison avec Répétition
7.1 Définitions

h Une p-Combinaison avec Répétition de n éléments est une application croissante ϕ : J1 ; pK 7−→ J1 ; nK.

K Une Combinaison avec Répétition de p éléments de E est une façon de choisir p éléments parmi les
éléments de E, avec remise à chaque tirage, mais sans tenir compte de l’ordre des tirages.

Le lien entre ces deux définitions ne saute pas aux yeux, mais nous pouvons l’expliciter :
D’abord nous pouvons identifier E avec J1 ; nK à l’aide d’une bijection f : J1 ; nK 7→ E, ensuite à un tirage
de p éléments parmi les éléments de E, on associe le tirage de p valeurs parmi les valeurs de J1 ; nK (grâce
à la bijection f définie ci-dessus), puis à ce tirage on associe la fonction ϕ : J1 ; pK 7−→ J1 ; nK qui à 1 fait
correspondre la plus petite valeur de J1 ; nK présente dans le tirage, à 2 fait correspondre la plus petite valeur
de J1 ; nK restante, présente dans le tirage etc., ce qui permet de construire une application croissante de J1 ; pK
dans J1 ; nK.
Une autre définition simple est possible :

X Combinaison avec Répétition de p éléments de E est une fonction ϕ : E 7−→ J1 ; pK, vérifiant
Une

K x∈E
f (x) = p.

f (x) s’interpréte comme le nombre de fois où l’élément x est choisi.

p
Le nombre de combinaison de p éléments, pris parmi n, sera noté : Γn .
p
Pour calculer Γn on peut considérer la construction suivante : on dispose de (n + 1) symboles de séparation
(nous utiliserons  ), et de p symboles d’objet (nous utiliserons  • ). On peut mettre en évidence une
bijection entre une combinaison avec répétition de p éléments choisis parmi n et les chaı̂nes de caractères
construites avec (n + 1) fois et p fois •, commençant et finissant par .
En effet, les (n + 1) délimitent exactement n zones en correspondance avec les n objets disponibles que
nous noterons 1, 2, · · · , n (la première zone correspondant à 1 la deuxième à 2 etc.), et le nombre de • contenus
dans la zone Numéro k s’interprète comme le nombre d’objets k choisis.
Par exemple, pour n = 9 et p = 8 (la notation {{· · · }} représente un multiensemble).

• • •• ••• •
= {{1, 3, 4, 4, 6, 6, 6, 9}}
1 2 3 4 5 6 7 8 9

• • •• ••• • = {{1, 3, 4, 4, 6, 6, 6, 9}}

Or il est facile de compter ces chaı̂nes de caractères (de longueur n + 1 + p), il suffit de choisir les positions
des p • parmi les n + p − 1 positions autorisées (la première et la dernière place sont prises par des séparateurs),
p p
soit Γn = Cn+p−1
n
Γpn ,
X
On peut faire le calcul (un peu comme pour les Arrangements sans répétitions) de toutes les
p=0
combinaisons avec répétitions de l’ensemble E (sans préciser le nombre total choix, pouvant varier de 0 à n).
Pour fabriquer une combinaison avec répétitions de n éléments, il suffit d’ajouter un (n + 1)ième élément,
qui jouera le rôle d’un élément ne servant à rien, de choisir une combinaison avec répétition de n éléments
n
parmi les (n + 1) éléments disponibles, puis de jeter l’élément surnuméraire, soit Γn+1 possibilités.
n
Γpn = Γnn+1 = Cnn+(n+1)−1 = Cn2n .
X

p=0

12
 On obtient donc les formules :
• Γpn =
p
Cn+p−1
• Γpn p−1 p
= Γn + Γn−1
n
Γpn = Cn2n
X
•
p=0

7.2 Exemples simples

Exemple 13. On lance 3 dés, combien de combinaisons différentes sont-elles possibles ?

D’abord, nous pouvons remarquer que l’ordre n’importe pas, les deux résultats suivants sont identiques
n o n o
=

Nous pouvons aussi remarquer que chaque valeur possible peut se répéter sur les différents dès, autant de
fois que l’on veut.
3 3
En appliquant la formule des combinaisons avec répétition, on obtient Γ6 = C8 = 56 possibilités.
Exemple 14. Combien de pièces comporte un jeu de domino ?
Un domino est constitué de 2 nombres choisis parmi {0, 1, 2, 3, 4, 5, 6}, éventuellement avec répétition : par
2 2
définition, ce nombre est Γ7 = C8 = 28 dominos.

8 Dérangement
8.1 Définitions

h Un Dérangement des n éléments de l’ensemble E, est une bijection ϕ sans point fixe de E dans lui-même.

K Un Dérangement de E est une permutation telle qu’aucun élément n’est à sa place initiale.

Un dérangement est donc une bijection ϕ : E 7−→ E, vérifiant : ∀x ∈ E(ϕ(x) 6= x).

Nous noterons Dn le nombre de dérangement d’un ensemble à n éléments, et pour les démonstration qui
suivent nous considérerons que E = J1, nK (on peut toujours se ramener à ce cas puisqu’il existe une bijection
entre E et J1, nK).
Il est facile de mettre en place une relation de récurrence :
Pour fabriquer une bijection ϕ sans point fixe de J1, nK dans lui-même, il faut :

1. Choisir l’image de 1 (ϕ(1)) qui est forcément différente de 1, soit (n-1) choix, notons ϕ(1) = k.
2. Puis, choisir les images des autres éléments
(a) Soit ϕ(k) = 1 et il reste à déranger les (n − 2) éléments suivants, soit Dn−2 .
(b) Soit ϕ(k) 6= 1, et en identifiant 1 et k, il reste (n − 1) éléments à déranger, soit Dn−1
En appliquant le principe de multiplication

et celui de somme, on obtient, pour n > 2, la relation de
récurrence : Dn = (n − 1) Dn−1 + Dn−2 .
Les résultats suivants son triviaux à calculer  à la main  :
D0 = 1
D1 = 0
D2 = 1

13
 La relation précédente permet de démontrer (par récurrence par exemple) une nouvelle relation plus simple
que la précédente Dn = nDn−1 + (−1)n . Cette dernière relation permet, à son tour, de démontrer (par
n
X (−1)k
récurrence par exemple) que Dn = n! .
k!
k=0

Il est possible de calculer Dn simplement et précisément (formule exacte et non approximative ou asymp-
h totique).
n ∞
X (−1)k X (−1)p 1
Dn = n! , or = e−1 =
k! p=0
p! e
k=0
Calculons, pour n > 0
∞
n! X (−1)p
- Dn = n!
e p=n+1 
p!

n+1 1 1 1
= (−1) − + − ···
n + 1 (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)
Nous sommes
 dans un cas ou le regroupement
  de termes est valide  
n+1 1 1 1
= (−1) − + − ··· + ···
 n + 1 (n + 1)(n + 2) (n + 1)(n + 2)(n + 3)
1 1
= (−1)n+1 + + ···
n + 2 (n + 1)(n + 2)(n + 4)
n! 1 1 1
- Dn < + + · · · (suite géométrique)
e n + 2 (n + 2)2 (n + 2)3
1 1
< ·
n+2 1
1−
n+2
1
<
n+1
 
n! 1 n! 1 n! 1 5
D’où on déduit : − < Dn < + , et finalement Dn = +
e 2 e 2 e 2
Dn est l’entier le plus proche de n !/e

L’ensemble des bijections de E dans lui-même est l’union des ensembles de bijections de E ayant p points
fixes, pour p variant de 0 à n (ces ensembles sont, bien sûr, disjoints), or il est facile de compter les bijections de
p
E dans lui-même ayant p points fixes : il faut choisir p éléments parmi les n possibles (soit Cn ) puis déranger
n
X p


les (n − p) éléments restants, soit Dn−p , on obtient donc : Cn Dn−p = Pn .
p=0

Nous pouvons résumer les formules trouvées :

• Dn = (n − 1) Dn−1 + Dn−2 .
• Dn = nDn−1 + (−1)n .
n
X (−1)k
• Dn = n! .
k!
k=0
n
X p
• Cn Dn−p = Pn = n!.
p=0
 
n! 1 n!
• Dn = + , l’entier le plus proche de .
e 2 e

8.2 Exemples simples

Exemple 15. Un enfant est placé devant un jeu constitué de 5 pièces de bois qui sont toutes des cylindres
droits (1 circulaire, 1 triangulaire, 1 carré, 1 pentagonal et 1 hexagonal), et une boı̂te fermée ayant 5 trous
5. La notation bxc désigne la partie entière de x, autrement dit, le plus grand entier plus petit ou égal à x.

14
 sur sa face supérieure (1 cercle, 1 triangle, 1 carré, 1 pentagone et 1 hexagone), les dimensions de ces trous
sont telles que chaque cylindre ne peut passer que par un seul trou et chaque trou ne laisse passer qu’un seul
cylindre.
De combien de façon peut on placer les 5 cylindres en face des 5 trous telles que :

1. Aucune condition (donc toutes les dispositions).

2. Toutes les pièces sont bien placées.
3. Aucune pièce n’est bien placée.
4. 1 seule pièce est bien placée.
5. Exactement 2 pièces sont bien placées.
6. Exactement 4 pièces sont bien placées.

1. Il s’agit simplement des permutation de l’ensemble des cylindres : P5 = 120.

1 11 1 1
2. Il faut choisir les cylindres dans l’ordre des trous : C × C × C × C1 × C1 = 1 6 .
1 1 1
3. Il s’agit donc du nombre de dérangements de 5 éléments : D5 = 44.
 1

4. Il faut choisir la pièce bien placée parmi les 5 disponibles soit C5 puis il faut mal placer les 4 autres
  1
soit D4 : C5 × D4 = 5 × 9 = 45.
 2

5. Il faut choisir les 2 pièces bien placées parmi les 5 disponibles soit C5 puis il faut mal placer les 3
  2
autres soit D3 : C5 × D3 = 10 × 2 = 20.
 4

6. Il faut choisir les 4 pièces bien placées parmi les 5 disponibles soit C5 puis il faut mal placer la dernière
  4
soit D1 : C5 × D1 = 5 × 0 = 0 7 .

9 Présentation générique

h Cette section est entièrement d’un niveau au delà du lycée.

Une façon d’aborder l’analyse combinatoire est de considérer les applications ϕ d’un ensemble fini E dans
un ensemble fini F de cardinal respectif : E = p et F = n. On peut donc toujours se ramener au cas
E = J1 ; pK et F = J1 ; nK.
Nous distinguerons :

1. Les éléments de E sont distincts ou non.

2. Les éléments de F sont distincts ou non.
3. ϕ est quelconque, injective, ou surjective.
Le cas ϕ est une bijection n’est qu’un cas particulier (de l’injection comme de la surjection) lorsque n = p.

Nous noterons P(X) l’ensemble des bijections de X dans lui-même (c’est à dire les permutations de X).
Mathématiquement, dire que les éléments de F sont indistincts et ceux de E sont distincts, revient à définir
une relation d’équivalence sur les applications de F E :

(f ∼ g) ⇔ (∃h ∈ P(F )(f = h ◦ g))

ou encore

(f ∼ g) ⇔ (∀x ∀y (((f (x) = f (y)) ⇔ (g(x) = g(y))))

6. C’est une façon un peu compliquée de dire qu’il n’y a pas le choix.
7. On pouvait se douter que si 4 pièces sur 5 sont bien placées, la dernière ne pouvait être qu’à sa place.

15
 Dans les figures 1 et 2, les applications équivalentes pour le relation ∼, ont des ensembles d’arrivée de
couleurs identiques.
Mathématiquement, dire que les éléments de E sont indistincts et ceux de F sont distincts, revient à définir
une relation d’équivalence sur les applications de F E :

(f ≈ g) ⇔ (∃k ∈ P(E)(f = g ◦ k))

ou encore
 
(f ≈ g) ⇔ (∀z f −1 ({z}) = g −1 ({z}) )
Dans les figures 1 et 2, les applications équivalentes pour le relation ≈, ont des espaces de départ de couleurs
identiques.
Mathématiquement, dire que les éléments de E sont indistincts et ceux de F sont aussi indistincts, revient
à définir une relation d’équivalence sur les applications de F E :

(f ≡ g) ⇔ (∃h ∈ P(F ) ∃k ∈ P(E) (f = h ◦ g ◦ k))

Montrer que ces trois relations sont d’équivalence est immédiat.

Dans ce qui suit, pour les injections, les valeurs sont données pour p ≤ n (sinon, le nombre de cas est 0) et
pour les surjections, les valeurs sont données pour p ≥ n (sinon, le nombre de cas est 0).

E =p F =n ϕ quelconque ϕ injective ϕ surjective ϕ bijective

p
Distinct Distinct np [1] An [2] n!S(p, n) [3] n!

Indistinct Distinct Γpn [4] Cn

p
[5] Γnp−n [6] 1
n
S(p, i) S(p, n)
X
Distinct Indistinct [7] 1 [8] [9] 1
i=1
n
p(p, i) p(p, n)
X
Indistinct Indistinct [10] 1 [11] [12] 1
i=1

Sur fond rose, on reconnaı̂t le tableau plus simple (et plus usuel) des tirages de p objets choisis parmi n,
avec ou sans remise, avec ou sans ordre :

Tirages Avec remise Sans remise

p
Avec ordre np An
Sans ordre Γpn p
Cn

S(p, n) : Nombre de Stirling de seconde espèce.

B(p) : Nombre de Bell
n
S(p, i) = B(p)
X
: Si p ≥ n,
i=1
p(p, n) : Nombre de partitions de l’entier p en n parties.
P(p) : Nombre de partitions de l’entier p (que l’on pourrait baptiser  Nombre de Ken Ono )
n
p(p, i) = P(p)
X
: Si p ≥ n,
i=1

Définition Nombre de Stirling 8 : S(p, n) = nombre de partitions de J1; pK en n sous-ensembles (pour p > n
sinon 0).
8. Plus de détail dans les Annexes.

16
 n
B(p) = S(p, i)
X
Définition Nombre de Bell :
i=1
Définition Nombre de partitions d’un entier 9 : p(p, n) = nombre de façon d’écrire p comme la somme de
n nombres entiers non nuls, sans tenir compte de l’ordre des opérandes.

Les cas [1], [2] et [5] découlent directement des définitions des Arrangements avec répétition, des Arrange-
ments et des Combinaisons.
Démonstration du cas [8] et du cas [11] :
Soit ϕ ∈ F E et ψ ∈ F E , deux injections, soit g une bijection de F \ ϕ(E) vers F \ ψ(E) (ce qui est possible
puisque ϕ et ψ sont des injections (et donc ϕ(E) = ψ(E) = p)) :
Pour x ∈ ψ(E), on pose h(x) = ϕ ◦ (ψψ(E) )−1 (x) Pour x ∈ / ψ(E), on pose h(x) = g(x).
Clairement ϕ = h ◦ ψ, autrement dit toutes les injections de E dans F sont ∼-équivalentes, il n’existe donc
qu’une seule classe d’équivalence pour cette relation.
Démonstration du cas [9] et du cas [3] :
Soit ϕ : J1, pK 7−→ J1, nK, une surjection, à ϕ on peut associer une partition de J1, pK en n parties, de la
façon suivante :
 
On définit la relation ∼ par ∀x ∈ J1, pK ∀y ∈ J1, pK ((x ∼ y) ⇔ (ϕ(x) = ϕ(y))
Cette relation est clairement une relation d’équivalence, elle définit donc bien une partition de J1, pK en n
parties (autant qu’il y a de valeurs différentes dans ϕ(J1, pK)).
Par contre une partition peut correspondre à plusieurs surjections, plus précisément si h est une bijection
de J1, nK dans lui-même, alors ϕ et h ◦ ϕ définissent la même partition (et réciproquement), et comme il existe
exactement n! bijections de J1, nK dans lui-même, nous retrouvons bien le cas [3] : n!S(p, n).
On peut remarquer que les surjections précédentes vérifient : ϕ ∼ (h ◦ ϕ), il y a donc autant de classes pour
la relation ∼ que de partitions, et on retrouve bien le cas [9] : S(p, n).
Démonstration du cas [12] :
n
X
Soit ϕ : J1, pK ⇒ J1, nK, une surjection, il est clair que p = ϕ−1 ({i}) , c’est dire qu’à chaque surjection
i=1
on peut faire correspondre une partition de p en n parties, par contre plusieurs surjections peuvent définir la
même partition de J1, nK (donc a fortiori la même partition de l’entier n) ; et, mêmes deux surjections ϕ et ψ
ne définissant pas la même partition de J1, nK peuvent définir la même partition de l’entier n, par contre ces
partitions sont isomorphes (en tant que modèles de la théorie des relations d’équivalence), c’est à dire qu’il
existe une bijection de J1, nK dans lui-même, et comme l’ordre des éléments de la partition n’a pas d’importance,
il existe aussi une bijection de J1, pK dans lui-même qui font que ϕ ≡ ψ, ce qui établit le résultat du cas [12].
Démonstration du cas [7] et du cas [10] :
Une application quelconque est une surjection sur son image, dont le cardinal peut varier de 1 à n, on
n
S(p, i).
X
obtient donc le cas [7] à partir du cas [9] :
i=1
n
p(p, i)
X
De la même façon, on obtient le cas [10] à partir du cas [12] :
i=1

Démonstration du cas [4] et du cas [6] :

Dans la classe des applications ϕ : J1, pK ⇒ J1, nK pour la relation ∼, il en existe une et une seule qui soit
croissante (cf. le chapitre Combinaison avec Répétitions pour sa construction), d’où le résultat immédiat pour
n
le cas [4] : Γp .
Pour fabriquer une surjection ϕ : J1, pK ⇒ J1, nK, on peut distinguer n éléments quelconques de J1, pK,
(p > n, puisque ϕ est une surjection), puis :

9. Plus de détail dans les Annexes.

17
• Etablir une bijection entre ces n éléments et J1, nK, or il n’existe qu’une seule telle bijection (cf. le tablea
ci-dessus) lorsque les éléments de l’ensemble de départ sont indistincts.
p−n
• Choisir une application quelconque entre les p − n éléments restants, soit Γp (c’est le cas [4].

En appliquant le principe du produit on obtient bien Γpp−n , ce qui établit le résultat du cas [6].

18
 E =p=2 F =n=3 ϕ quelconque ϕ injective ϕ surjective
Distinct Distinct 9 6 0
Indistinct Distinct 6 3 0
Distinct Indistinct 2 1 0
Indistinct Indistinct 2 1 0

Figure 1 – Application de E (|E| = 2) dans F (|F | = 3).

B Les applications dont les flèches sont noires sont les injections.
B Les applications dont les flèches sont rouges sont les applications non injectives.
B Les applications ayant des ensembles d’arrivée de même couleurs sont ∼-équivalentes.
B Les applications ayant des ensembles de départ de même couleurs sont ≈-équivalentes.

19
 E =p=3 F =n=2 ϕ quelconque ϕ injective ϕ surjective
Distinct Distinct 8 0 6
Indistinct Distinct 4 0 2
Distinct Indistinct 4 0 3
Indistinct Indistinct 2 0 1

Figure 2 – Application de E (|E| = 3) dans F (|F | = 2).

B Les applications dont les flèches sont noires sont les surjections.
B Les applications dont les flèches sont rouges sont les applications non surjectives.
B Les applications ayant des ensembles d’arrivée de même couleurs sont ∼-équivalentes.
B Les applications ayant des ensembles de départ de même couleurs sont ≈-équivalentes.

20
10 Exercices résolus
Exercice 1. Principe d’inclusion-exclusion
Combien d’entiers compris entre 1 et 300 (inclus) sont :

1. Divisible par au moins un des nombres 3, 5 et 7 ?

2. Divisible par 3 et 5 mais pas par 7 ?
3. Divisible par 5 mais ni par 3 ni par 7 ?
Nous allons appliquer le principe d’inclusion-exclusion en posant Dp = {n | (n ∈ N? ) ∧ (n ≤ 300) ∧ (p|n) 10 }.
On peut calculer
  le cardinal de chaque ensemble constitué des multiples d’un nombre donné :
300
• D3 = = 100
 3 
300
• D5 = = 60
 5 
300
• D7 = = 42
7
3, 5 et 7 étant premiers entre eux, l’intersection, par exemple, de D3 et de D5 est constitué des multiples
de 3 et de 5 donc des multiples de 15.
 
300
• D15 = = 20
 15 
300
• D21 = = 14
 21 
300
• D35 = =8
35 
300
• D105 = =2
105

La première question revient à calculer le cardinal de l’union : D3 ∪ D5 ∪ D7 .

En appliquant le principe d’inclusion exclusion, on obtient :
 
D3 ∪ D5 ∪ D7 = D3 + D5 + D7 − D15 + D35 + D21 + D105

Soit D3 ∪ D5 ∪ D7 = 100 + 60 + 42 − (20 + 14 + 8) + 2 = 202 − 42 + 2 = 162.

La deuxième question revient à calculer le cardinal de : D15 \ D7 .
En appliquant le principe d’inclusion exclusion, on obtient :

D15 \ D7 = D15 − D105

Soit D15 \ D7 = 20 − 2 = 18.

La troisième question revient à calculer le cardinal de : D5 \ (D15 ∪ D35 ) .
En appliquant le principe d’inclusion exclusion, on obtient :
 
D5 \ (D15 ∪ D35 ) = D5 − D15 ∪ D35 = D5 − D15 + D35 − D105

Soit D5 \ (D15 ∪ D35 ) = 60 − (20 + 8 − 2) = 34

Exercice 2. On lance 99 billes sur un plateau de jeu de 70 cm de côté ; montrez qu’il existe au moins 3 billes
délimitant un triangle d’aire inférieure ou égale à 50 cm2
10. (p|n) se lit  p divise n .

21
 Découpons le plateau de jeu en 7 × 7 = 49 carrés de 10 cm de côté, en appliquant le  principe des tiroirs
99
généralisé, on obtient qu’il existe au moins un de ces carrés qui contient au moins = 3 billes, ces 3
49
billes délimitent un triangle dont l’aire est au plus la moitié de l’aire du carré dans lequel elles se trouvent soit
10 × 10
= 50 cm2 .
2

Exercice 3. Les mains au poker fermé

Une main au poker fermé est constituée de 5 cartes prises parmi les 52 d’un jeu de carte standard (cartes
numérotée de 1 à 10, plus le valet (V), la Dame (D) et le roi (R), soit 13 hauteurs, et de 4 couleurs possibles
Trèfle, Carreau, Coeur et Pique)
Les mains possibles au poker sont les suivantes (l’as sera noté 1 dans les suites ou il précède le 2, et A
lorsqu’il suit le roi) :

Quinte Flush Royale : (10, V, D, R, A) toutes d’une même couleur.

Quinte Flush non Royale : 5 cartes qui se suivent, de la même couleur, mais pas (10, V, D, R, A).
Carré : 4 cartes de la même hauteur.
Full : 3 cartes de la même hauteur et 2 cartes d’une autre hauteur.
Couleur : 5 cartes de la même couleur, mais aucun des cas précédents.
Quinte : 5 cartes qui se suivent, mais aucun des cas précédents.
Brelan : 3 cartes de la même hauteur, mais aucun des cas précédents.
Deux Paires : 2 fois 2 cartes de la même hauteur, mais aucun des cas précédents.
Une Paire : 2 cartes de la même hauteur, mais aucun des cas précédents.
Hauteur : Aucun des cas précédents (c’est le rang de la carte la plus haute qui compte).

Nombre de mains :
5
1. Il faut choisir (sans tenir compte de l’ordre) 5 cartes parmi 52 soit : C52 = 2 598 960.
Nombre de Quintes Flush Royales :
1
1. Il faut et il suffit de choisir une couleur parmi les 4 disponibles (les hauteurs sont fixées) : C4 = 4.
Nombre de Quintes Flush non Royales :
1
1. Il faut choisir une couleur parmi les 4 couleurs disponibles : C4 .
2. Puis la hauteur de la carte la plus basse parmi les 9 disponibles, les hauteurs possibles sont 1, 2 . . . 9. (le
1
10 n’est pas possible, sinon nous aurions une quinte flush) : C9 .
1 1
3. Soit, au final : C4 · C9 = 4 · 9 = 36.
Nombre de Carrés :
1
1. Il faut choisir la hauteur des 4 cartes de même hauteur, parmi les 13 possibles : C13 .
4
2. Puis les 4 cartes de la hauteur choisie, donc parmi 4 : C4 .
1
3. Puis une des cartes d’une autre hauteur, donc parmi 52 - 4 = 48 cartes : C48 .
1 4 1
4. Soit, au final : C13 · C4 · C48 = 13 · 48 = 624.
Nombre de Fulls :
1
1. Il faut choisir la hauteur des 3 cartes de même hauteur parmi les 13 possibles : C13 .
3
2. Choisir 3 cartes parmi les 4 possibles (de la hauteur choisie) : C4 .
3. Choisir la hauteur des 2 autres cartes, parmi les 12 possibles 11 (puisque l’on ne peut pas reprendre la
1
précédente) : C12 .
11. On aurait pu aussi choisir les deux hauteurs parmi les 13 possibles de façon ordonnée (la première hauteur concernera 3
cartes et la deuxième concernera 2 cartes), puis choisir les 3 cartes parmi les 4 de la première hauteur choisie, enfin, choisir les 2
2 3 4
cartes parmi les 4 possibles de la deuxième hauteur choisie : A13 · C4 · C2 = (13 · 12) · 4 · 6 = 3744.

22
 2
4. Choisir 2 cartes parmi les 4 possibles (de la hauteur choisie) : C4 .
1 3 1 2
5. Soit, au final : C13 · C4 · C12 · C4 = 13 · 4 · 12 · 6 = 3744.
Nombre de Couleurs :
1
1. Il faut choisir la couleur parmi les 4 possibles : C4 .
2. Puis 5 cartes qui ne se suivent pas parmi les 13 de cette couleur ; pour compter le nombre de façons
de choisir 5 cartes qui ne se suivent
 pas, on peut compter tous les paquets de 5 cartes dans la couleur
5
choisie, donc parmi 13 soit C13 et soustraire le nombre de paquets de cartes qui se suivent dans la
 1
 5 1
couleur choisie soit les suites commençant par 1, 2, . . . , 10 soit C10 : C13 - C10 .
1
 5 1

3. Soit, au final : C4 · C13 - C10 = 4 · (1287 − 10) = 5 108.

Nombre de Quintes :
1
1. Il faut choisir la carte la plus basse de la quinte (parmi les 10 possibles) : C10 .
 
1 5

2. Puis choisir successivement la couleur de chaque carte parmi les 4 couleurs disponibles C
4 et,
éliminer les quintes de la même couleur, pour une carte la plus basse possible donnée, il faut choisir 1
 1
  1 5 1
couleur parmi les 4 possibles soit C4 : C4 - C4 .
  
1 1 5 1
3. Soit, au final : C10 · C4 − C4 = 10 · (1024 - 4) = 10 200.

Nombre de Brelans :
1
1. Il faut choisir la hauteur des 3 cartes de même hauteur, parmi les 13 possibles : C13 .
3
C4 .
2. Puis choisir ces 3 cartes parmi les 4 disponibles :
2
3. Puis choisir 2 hauteurs parmi les 12 restantes : C12 .
 1 2
4. Puis 1 carte parmi les 4 de chacune des 2 hauteurs sélectionnées : C4 .
1 3 2
 1 2
5. Soit, au final : C13 · C4 · C12 · C4 = 13 · 4 · 66 · 16 = 54 912.

Nombre de Mains avec 2 Paires :

1. Il faut choisir 2 hauteurs parmi les 4 disponibles (ces 2 hauteurs jouant le même rôle on peut les choisir
2
sans tenir compte de l’ordre) : C13 .
 2 2
2. Puis les 2 cartes parmi les 4 disponibles dans chacune de ces 2 hauteurs : C4 .
1
3. Puis une cinquième carte d’une troisième hauteur (donc parmi les 52 - 8 = 44 cartes restantes) : C44 .
2
 2 2 1
4. Soit, au final : C13 · C4 · C44 = 78 · 62 · 44 = 123 552.

Nombre de Mains avec 1 Paire :

1
1. Il faut choisir 1 hauteur pour la paire parmi les 13 possibles :C13 .
2
2. Puis, les 2 cartes parmi les 4 disponibles dans cette hauteur : C4 .
3. Puis 3 autres hauteurs pour les 3 cartes suivantes parmi les 12 disponibles (ces 3 cartes jouant le même
3
rôle on peut les choisir sans tenir compte de l’ordre) : C12 .
 1 3
4. Puis 3 fois de suite il faut choisir 1 carte de la hauteur choisie parmi les 4 disponibles : C4 .
1 2 3
 1 3
5. Soit, au final : C13 · C4 · C12 · C4 = 13 · 6 · 220 · 43 = 1 098 240

Nombre de Mains de Type Hauteur :

23
  5

1. Il faut choisir 5 hauteurs parmi les 13 possibles soit C13 , mais en éliminant les quintes, que l’on peut
 1
  5 1

compter en choisissant la carte la plus basse, parmi les 10 cas possibles soit C10 : C13 - C10 .
  1 5 
2. Puis il faut choisir 5 fois 1 carte parmi les 4 disponibles soit C4 , mais en éliminant les couleurs,
    1 5 
1 1
que l’on peut compter en choisissant un des 4 couleurs soit C4 : C4 − C4 .
 5 1
  1 5 1

3. Soit, au final : C13 - C10 · C4 − C4 = (1287 − 10) · (45 − 4) = 1 302 540

Récapitulatif :

1
Quinte Flush Royale : C4 = 4
1 1
Quinte Flush non Royale : C4 · C9 = 4·9 = 36
1 4 1
Carré : C13 · C4 · C48 = 13 · 48 = 624
1 3 1 4
Full : C13 · C4 · C12 · C2 = 13 · 4 · 12 · 6 = 3 744
1 5 1
Couleur : C4 · (C13 - C10 ) = 4 · (1287 − 10) = 5 108
1 1 1
Quinte : C10 · ((C4 )5 - C4 ) = 10 · (1024 - 4) = 10 200
1 3 2 1
Brelan : C13 · C4 · C12 · (C4 )2 = 13 · 4 · 66 · 42 = 54 912
2 2 1
Deux Paires : C13 · (C4 )2 · C44 = 78 · 62 · 44 = 123 552
1 2 3 1
Une Paire : C13 · C4 · C12 · (C4 )3 = 13 · 6 · 220 · 43 = 1 098 240
5 1 1 1
Rien : (C13 - C10 ) · ((C4 )5 - C4 ) = (1287 − 10) · (45 − 4) = 1 302 540
Total : = 2 598 960
5
Nombre de Mains : C52 = 2 598 960

Exercice 4. Un individu veut réunir n amis (lui compris) autour d’une table ronde, de combien de façons
peut-il les placer autour de la table ?

En fait cette question est (volontairement) mal posée, en effet on peut la comprendre d’au moins 3 façons :

1. Chaque place est spécifique.

2. Les places sont indifférentes, seuls comptent les deux voisins de chacun, mais être voisin de gauche ou
voisin de droite n’est pas la même chose.
3. Les places sont indifférentes, seuls comptent les deux voisins de chacun, et être voisin de gauche ou voisin
de droite est indifférent.

Ces 3 compréhensions amènent 3 réponses différentes :

1. Il faut donc établir une bijection entre les places et les convives : Pn .
2. Cette fois on peut placer l’un de convives n’importe où (à condition que n > 0, sinon, il n’y a qu’une
seule solution), puis il faut placer les (n − 1) convives suivants aux (n − 1) places restantes, soit Pn−1 .
3. Cette fois (à condition que n > 3, sinon, il n’y a qu’une seule solution) on peut toujours placer le premier
convive n’importe où, puis il faut choisir 2 autres convives (sans les ordonner) et les placer autour du
premier (l’un à gauche, l’autre à droite), enfin il faut placer les (n − 3) convives restants aux (n − 3)
2
places restantes : Cn−1 ·Pn−3 .

Exercice 5. Combien existe-t-il de nombres palindromes 12 constitué de 7 chiffres différents (le premier est
forcément différent de 0).
12. Un palindrome est une chaı̂ne de caractères qui se lit de la même façon de gauche à droite et de droite à gauche

24
 Pour résoudre cet exercice il suffit de le découper en deux parties :

1. Choisir le premier chiffre (qui est aussi le dernier) qui doit être différent de 0, donc faire un choix de 1
1
objet parmi 9, soit C9 possibilités.
2. Choisir les chiffres en position 2, 3 et 4 (ce qui donne aussi les chiffres en position 5 et 6), donc faire le
3
choix ordonné de 3 chiffres parmi les 9 restants (0 inclu, mais le premier choisi exclu), soit A9 = 504
possibilités
1 3
En appliquant la règle du produit, on obtient C9 × A9 = 9 × 504 = 4536 possibilités.
p p p−1
Exercice 6. Démontrer An = An−1 + pAn−1
Bien sûr on peut démontrer ce résultat par le calcul (une ligne), mais on peut aussi utiliser une autre
méthode, courante dans le cadre du dénombrement :
On distingue un élément, et on compte les arrangements incluant ou non cet élément :
1. Pour fabriquer un arrangement contenant l’élément distingué, il faut choisir la place de cet élément parmi
1
les p places disponibles, soit Cp ; puis il faut choisir (p − 1) éléments parmi les (n − 1) autres éléments,
p−1
et les arranger, soit An−1 .
2. Pour fabriquer un arrangement ne contenant pas l’élément distingué, il faut arranger p éléments choisis
p
parmi les (n − 1) autres éléments, soit An−1
p p p−1
Il suffit d’appliquer les principes du produit et de la somme pour obtenir : An = An−1 + pAn−1 .

Exercice 7. Démontrer S(p, n) = S(p − 1, n − 1) + nS(p − 1, n)

Soit x un élément distingué de E un ensemble de cardinal p, une partition de E en n sous-ensembles peut :

1. Soit contenir le singleton {x}, pour construire une telle solution il faut et il suffit de fabriquer une
partition des (p − 1) éléments différents de x en (n − 1) sous-ensembles et ajouter le singleton {x} (soit
S(p − 1, n − 1) possibilités).
2. Soit l’élément x appartient à un ensemble de cardinal strictement plus grand que 1, pour construire
une telle solution, il faut et il suffit fabriquer une partition des (p − 1) éléments différents de x en
n sous-ensembles et ajouter l’élément x à l’un des n sous-ensembles de la partition (soit nS(p − 1, n)
possibilités).

Le résultat final découle directement de la règle de la somme.

Exercice 8. Démontrer p(p, n) = p(p − 1, n − 1) + p(p − n, n)

Une partition de p en n entiers non nuls, peut :

1. Soit contenir au moins un fois le 1, pour construire une telle solution il faut et il suffit de fabriquer une
partition de (p − 1) en (n − 1) entiers et ajouter l’entier 1 (soit p(p − 1, n − 1) possibilités).
2. Soit tous les nombres de la somme sont supérieurs à 1, pour construire une telle solution, il faut et il
suffit de fabriquer une partition de (p − n) en n entiers et ajouter 1 à tous ces entiers (soit p(p − n, n)
possibilités).

Le résultat final découle directement de la règle de la somme.

25
11 Annexes
11.1 Nombre de Stirling de seconde espèce
Nombre de Stirling de seconde espèce, S(p, n) : nombre de relations d’équivalence ayant n classes d’équivalence
définies sur un ensemble de cardinal p, c’est-à-dire aussi le nombre de partitions en n sous-ensembles d’un en-
semble de cardinal p.
On peut noter les formules (qui se démontrent en appliquant la définition, voir éventuellement Exercices
résolus) :
• S(p, n) = S(p − 1, n − 1) + nS(p − 1, n)
• S(p, n) = 0 si p < n
• S(p, 0) = 0 si p > 0
• S(0, 0) = 1 (les résultats précédents suffisent à la génération de toutes les valeurs)
• S(p, 1) = S(p, p) = 1 p > 0
n
p
0 1 2 3 4 5 6 7 8 9 B(p)
0 1 1
1 0 1 1
2 0 1 1 2
3 0 1 3 1 5
4 0 1 7 6 1 15
5 0 1 15 25 10 1 52
6 0 1 31 90 65 15 1 203
7 0 1 63 301 350 140 21 1 877
8 0 1 127 966 1701 1050 266 28 1 4140
9 0 1 255 3025 7770 6951 2646 462 36 1 21147

S(p, n)

26
11.2 Partition d’un entier
Une partition d’un entier p en n élément est un multiensemble d’entiers naturels non nuls, de cardinal n
dont la somme est p.
Par exemple, pour p = 6 les partitions possibles sont :

1 2 3 4 5 6
6 5+1 4+1+1 3+1+1+1 2+1+1+1+1 1+1+1+1+1+1
4+2 3+2+1 2+2+1+1
3+3 2+2+2
A noter que l’ordre n’intervient pas et, par exemple, que les sommes 4 + 2 et 2 + 4 ne correspondent qu’à
une seule partition de 6 en 2 parties.
On peut noter les formules (qui se démontrent en appliquant la définition, voir éventuellement Exercices
résolus) :
• p(p, n) = p(p − 1, n − 1) + p(p − n, n)
• p(p, n) = 0 si p < n
• p(0, 0) = 1 (les résultats précédents suffisent à la génération de toutes les valeurs)
• p(p, p) = p(p, 1) = 1
n
p
0 1 2 3 4 5 6 7 8 9 P(p)
0 1 1
1 0 1 1
2 0 1 1 2
3 0 1 1 1 3
4 0 1 2 1 1 5
5 0 1 2 2 1 1 7
6 0 1 3 3 2 1 1 11
7 0 1 3 4 3 2 1 1 15
8 0 1 4 5 5 3 2 1 1 22
9 0 1 4 7 6 5 3 2 1 1 30

p(p, n)

27