Méthodes Combinatoires, Problèmes de Dénombrement

Clément Legrand

31 juillet 2020

1
Introduction
Notre premier lien avec les mathématiques apparaît lorsqu’on apprend à compter. Au dé-
but on compte sur ses doigts, des bonbons et des pièces, mais bientôt cela ne suffit plus. Les
nombres deviennent trop grands, les objets deviennent abstraits, et nous devons trouver de
nouvelles manières (i.e. des outils) pour compter (i.e. dénombrer) ceux qui nous intéressent.
Ces outils ne sont rien d’autre que des méthodes combinatoires, que l’on applique ensuite à
divers problèmes de dénombrement.
Les problèmes de dénombrement se retrouvent par ailleurs dans toutes les branches des
mathématiques, que ce soit en probabilité, en arithmétique ou en algèbre. Par exemple, à par-
tir de méthodes combinatoires, on peut s’intéresser à la probabilité que deux nombres choisis
aléatoirement, soient premiers entre eux. On peut également s’intéresser au nombre de ma-
nières de colorer les faces d’un cube avec k couleurs. Pour réaliser un tel dénombrement, il
est fondamental de savoir utiliser des techniques d’algèbre faisant intervenir des actions de
groupe.
Ce mémoire ne fournit pas une liste exhaustive des méthodes combinatoires, tant il y en a,
et elles ne permettront pas non plus de traiter l’intégralité des problèmes de dénombrement
auxquels le lecteur pourrait être confronté. En effet, la créativité joue souvent un rôle non né-
gligeable dans la résolution de ce genre de problèmes, puisqu’il y a souvent plusieurs manières
pour arriver au résultat. Par ailleurs, l’un des intérêts de savoir dénombrer de différentes ma-
nières est de pouvoir relier entre elles différentes quantités. Néanmoins ce mémoire fournit un
aperçu des méthodes classiques et couramment utilisées en pratique pour résoudre des pro-
blèmes de dénombrement, et fournit au lecteur un bagage pour lui permettre de trouver par
lui-même les réponses qu’il cherche. Des références sont également présentées si le lecteur sou-
haite en apprendre davantage sur une méthode en particulier. D’ailleurs, si le lecteur se trouve
être passionné de problèmes combinatoires, il peut sans hésitations se lancer dans la lecture
du livre [2], qui regorge de tels problèmes, et qui essaye d’adopter une manière pédagogique
pour présenter la résolution des problèmes de dénombrement.
On commence par présenter la méthode combinatoire la plus naturelle pour dénombrer,
qui consiste à établir une bijection entre deux ensembles, quand on connaît le cardinal de l’un
des deux ensembles. Certains nombres souvent utilisés en dénombrement sont également in-
troduits. Dans une deuxième partie, on présente le paradigme "diviser pour régner" dans le
cadre des problèmes combinatoires. Toutefois, dans certains problèmes il est nécessaire d’uti-
liser des formules d’inversion pour revenir à la quantité recherchée. Une troisième partie in-
troduit les séries génératrices, et présente quelques cas d’application typique. Enfin la dernière
partie présente surtout des techniques d’algèbre pour résoudre certains problèmes de dénom-
brement, dont les coloriages.

2
Table des matières
1 Le cardinal pour dénombrer 4
1.1 Un peu de théorie des ensembles finis . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Calcul de cardinaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Combinaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Coefficients binomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.2 Coefficients multinomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Formules d’inversion et applications 10

2.1 Formule d’inversion de Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Formule d’inversion de Möbius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Fonction de Möbius et produit de convolution . . . . . . . . . . . . . . . . 11
2.2.2 La formule d’inversion et applications . . . . . . . . . . . . . . . . . . . . . 15

3 Séries génératrices 16
3.1 Introduction aux séries génératrices . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1.2 Opérations sur les séries génératrices . . . . . . . . . . . . . . . . . . . . . 17
3.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.1 Un exemple typique : les partitions . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.2 Triangulations d’un n-gone . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

4 Méthodes algébriques 20
4.1 Actions de groupe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Problèmes de coloration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 La formule de Burnside . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.2 Coloriages du cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

5 Questions posées lors de l’oral 25

5.1 Sur le développement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Sur le plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3
1 Le cardinal pour dénombrer
Une première manière de dénombrer un ensemble peut être de rechercher un isomor-
phisme entre l’ensemble à dénombrer et un ensemble dont on connaît le cardinal. Les notions
introduites sont présentes dans le livre [4].

1.1 Un peu de théorie des ensembles finis

Pour définir la notion d’ensembles finis, on se réfère à l’ensemble N∗ = N \ {0} = {0, 1, . . .}
des entiers naturels. Les sous-ensembles de N∗ qui interviennent constamment dans la suite
sont les {1, 2, . . . , n} et {m + 1, m + 2, . . . , n}, qui seront notés respectivement [n] et [m + 1, n]
dans la suite. Par convention, [n] = ∅ si n = 0. Rappelons les propriétés suivantes, concernant
l’ensemble des entiers naturels.

Proposition 1. Soient n et p deux entiers strictement positifs.

1. Il existe une bijection de l’intervalle [n] sur l’intervalle [ p], si et seulement si n = p ;
2. Pour tout sous-ensemble non vide E de [n], il existe une bijection de E sur un intervalle
[ p] tel que p ≤ n ;
3. Il existe une bijection de [ p] sur l’intervalle [n + 1, n + p].
On en vient alors à la définition d’un ensemble fini.

Définition 2. On dit qu’un ensemble E, est fini, s’il existe une bijection de l’intervalle [n] de N∗
sur E. Une telle bijection est alors appelée numérotation de E.
Si E est un ensemble fini, il ne peut être mis en bijection, d’après la proposition 1, qu’avec
un seul intervalle de la forme [n]. Cet entier est donc déterminé de manière unique.

Définition 3. On appelle cardinal de E, l’unique entier n tel que E soit en bijection avec [n]. On
le note card(E) ou encore | E| s’il n’y a pas ambiguïté. On dit encore que E contient n éléments.
Dans la suite, on convient que l’ensemble vide est fini et on pose |∅| = 0.

Exemple 4. {2, 4, 8, 16} est un ensemble fini de cardinal 4, mais N, Q et R ne le sont pas.
La proposition suivante est une conséquence immédiate de la définition du cardinal et de
la proposition 1.

Proposition 5. 1. Toute partie d’un ensemble fini est finie ;

2. Deux ensembles finis E et F ont le même cardinal, si et seulement s’il existe une bijection
de E sur F.
On définit ensuite les trois opérations ensemblistes usuelles, que sont l’union, l’intersection
et le produit cartésien.

Définition 6. Soient E et F deux sous-ensembles. L’union de E et F, noté E ∪ F est l’ensemble

des éléments qui sont soit dans E, soit dans F (non exclusif). On a

E ∪ F = { x | x ∈ E ∨ x ∈ F }.

On peut étendre cette définition à une famille finie d’ensembles. Soit I une partie de N, ( Ei )i∈ I
une famille d’ensembles. On a
[
Ei = { x |∃i ∈ I, x ∈ Ei }.
i∈ I

4
Définition 7. Soient E et F deux sous-ensembles. L’intersection de E et F, noté E ∩ F est l’en-
semble des éléments qui sont à la fois dans E et dans F (non exclusif). On a

E ∩ F = { x | x ∈ E ∧ x ∈ F }.

Soit I une partie de N, ( Ei )i∈ I une famille d’ensembles. On a

\
Ei = { x |∀i ∈ I, x ∈ Ei }.
i∈ I

Définition 8. Soient E et F deux sous-ensembles. Le produit cartésien de E et F, noté E × F est

l’ensemble des paires d’éléments dont le premier élément est dans E, et dont le deuxième est
dans F. On a
E × F = {( x, y)| x ∈ E ∧ y ∈ F }.
Soient E1 , . . . , En une famille d’ensembles. On a

E1 × E2 × . . . × E p = { x = ( x1 , x2 , . . . , x p )|∀i ∈ [ p], xi ∈ Ei }.

1.2 Calcul de cardinaux

On s’intéresse dans la suite à des formules donnant le cardinal des ensembles définis pré-
cédemment. De cette manière, si dans le cadre d’un problème de dénombrement on parvient à
se ramener au dénombrement de l’un de ces ensembles, on pourra s’en sortir.
On rappelle que deux ensembles E et F sont dits disjoints, si leur intersection est vide, i.e.
E ∩ F = ∅. Dans ce cas on note E + F leur réunion. On a alors la propriété suivante concernant
le cardinal d’une union de deux ensembles disjoints.
Proposition 9 (Formule de la somme). Si E et F sont deux ensembles finis disjoints, leur
réunion E + F est finie et l’on a :
| E + F | = | E | + | F |.

On peut alors étendre la formule précédente par récurrence sur k ∈ N∗ , si E1 , . . . , Ek sont

des ensembles finis et disjoints deux à deux, alors

| E1 + . . . + Ek | = | E1 | + . . . + | Ek |.

Proposition 10. Si E et F sont finis mais non nécessairement disjoints, on a la formule dite des
"quatre cardinaux"
| E ∪ F | + | E ∩ F | = | E| + | F |
.
On dispose également d’une formule plus générale pour l’union de n ensembles, appelée
formule du crible de Poincaré, ou encore principe d’inclusion-exclusion.
Proposition 11 (Principe d’inclusion-exclusion). Soient n ≥ 2 et E1 , . . . , En des ensembles
quelconques, éventuellement vides, mais finis. Alors
n
| E1 ∪ E2 ∪ . . . ∪ En | = ∑ (−1)k−1 ∑ | Ei1 ∩ . . . ∩ Eik |.
k =1 1≤i1 <...<ik ≤n

5
Exemple 12. Grâce à cette formule, on peut déterminer le nombre S p,n de surjections de [ p]
dans [n]. Montrons le résultat suivant.
n  
n
S p,n = ∑ (−1)n−k k p .
k =0
k

Pour y ∈ [n], soit Ey l’ensemble des applications de [ p] dans [n] qui ne prennent jamais la
valeur y. Une surjection de [ p] dans [n], est alors une application qui ne se retrouve dans aucun
S
des Ey . Autrement dit, S p,q = |[ p][n] | − | Ey |. D’après le principe d’inclusion-exclusion, on
y∈[ p]
a:
[ n
Ey = ∑ (−1)k−1 ∑ | EY |.
y∈[ p] k =1 Y ⊂[n]
|Y |=k
T
où EY = Ey est l’ensemble des applications de [ p] dans [n] telles qu’aucun élément de Y n’a
y ∈Y
d’antécédent. On remarque qu’il y en a autant que d’applications de [ p] dans [n] \ Y, et donc
| EY | = (n − |Y |) p . En remplaçant dans la formule, il vient :

[ n
Ey = ∑ (−1)k−1 ∑ (n − k) p
y∈[ p] k =1 |Y |=k
Y ⊂[n]

n
= ∑ (−1)k−1 (n − k) p |{Y ⊂ [n]||Y | = k}|
k =1
n  
k −1 n
= ∑ (−1) (n − k)
k
p

k =1

On peut alors revenir à l’expression de S p,n et en utilisant la symétrie des coefficients bino-
miaux : (nk) = (n−
n
k ), on obtient bien le résultat voulu.

Exemple 13. On peut aussi calculer la probabilité que deux nombres entiers soient premiers
entre eux. On reviendra sur ce résultat après avoir introduit la formule d’inversion de Möbius
dans la section 2.
La formule de la somme peut être reformulée de façon intuitive en une règle de la somme :
"si un objet a peut être choisi de n façons et un objet b de p autres façons, il y n + p façons de
choisir soit a, soit b". Toutefois cet énoncé conserve une légère ambiguïté et c’est justement le
langage de la théorie des ensembles qui permet de lever celle-ci, avec le produit cartésien.

Proposition 14 (Formule du produit). Si E et F sont deux ensembles finis (non nécessairement

disjoints), alors le produit cartésien E × F est fini et on a

| E × F | = | E | · | F |.

La formule précédente se prolonge également au cas de n ≥ 2 ensembles finis. Ainsi, on

obtient pour toute suite E1 , . . . , En d’ensembles finis, la formule

| E1 × . . . × En | = | E1 | × . . . × | En |.

6
 De même la règle du produit s’énonce comme suit : "si un objet a peut être choisi de n
façons et qu’ensuite un objet b peut être choisi de p façons, la paire ( a, b), prise dans cet ordre,
peut être choisie de np façons".
Dans le langage fonctionnel, on peut dire que l’ensemble B A de toutes les applications d’un
ensemble A, de cardinal p, dans un ensemble B, de cardinal n, a pour cardinal n p .
Exemple 15. Le nombre de parties d’un ensemble à n éléments, est 2n . En effet si b1 , . . . , bn sont
les éléments de B numérotés, toute partie A de B est entièrement caractérisée par la donnée
d’une suite ( x1 , . . . , xn ), où pour 1 ≤ i ≤ n chaque xi vaut 0 ou 1. On a donc une bijection entre
les parties de B et {0, 1}n .
Exemple 16. L’alphabet Braille, est un alphabet adapté pour les malvoyants, dont chaque ca-
ractère peut être codé avec au plus 6 points. On peut donc coder 26 = 64 caractères différents,
ce qui permet de coder l’intégralité de notre alphabet, ainsi que les chiffres et les symboles de
ponctuation.
On dispose également d’un résultat fort utile en pratique, connu sous le nom de lemme des
bergers, qui s’énonce comme suit.
Proposition 17 (Lemme des bergers). Soient A et B deux ensembles finis, de cardinaux respec-
tifs a et b. Soit f : A → B une surjection telle que pour tout y ∈ B, | f −1 (y)| = c, où c ∈ N, alors
on a a = b × c.
Exemple 18. L’application la plus simple de ce lemme, et qui lui donne son nom également, est
la suivante. Un berger souhaite compter ses moutons, mais il ne voit que leurs pattes. Chaque
mouton ayant 4 pattes, s’il voit 36 pattes, c’est qu’il y a en fait 36
4 = 9 moutons, d’après le
lemme des bergers.
Exemple 19. On peut utiliser ce résultat pour dénombrer les sous-espaces vectoriels de dimen-
sion finie sur les corps finis. Soit K un corps fini de cardinal q. Soit n ∈ N∗ , notons E = Kn
un K-espace vectoriel. Cherchons ses sous-espaces vectoriels de dimension p, notons Sq (n, p)
leur nombre. Une base de E est la donnée d’un n-uplet de vecteurs de E linéairement indépen-
dants. Pour construire une telle base, on dispose de qn − 1 possibilités pour le premier vecteur
(en effet il y a q possibilités pour chaque composante du vecteur, et le vecteur nul ne convient
pas). Notons e1 ce premier vecteur. Pour le deuxième vecteur, on peut prendre tous les vecteurs
sauf ceux qui sont dans vect(e1 ), ce qui interdit tous les vecteurs de la forme Ke1 , c’est à dire
q vecteurs. Il reste alors qn − q possibilités pour le deuxième vecteur, notons le e2 . En remar-
quant que vect(e1 , e2 , . . . , ei ) interdit qi vecteurs, on déduit de proche en proche que le nombre
de bases possibles pour E est (qn − 1)(qn − q) . . . (qn − qn−1 ). Considérons alors l’application :
f : {bases de E} → {bases de F }
( e1 , e2 , . . . , e n ) 7 → ( e i1 , . . . , e i p )
où (e1 , e2 , . . . , en ) est une base de E, F un sous-espace vectoriel de dimension p, et (ei1 , . . . , ei p )
une base de cet espace. Cette application est clairement surjective. Pour appliquer le lemme
des bergers, il reste à savoir combien de familles libres de taille p on peut former dans E. On
peut raisonner exactement de la même manière que précédemment, en s’arrêtant dès qu’on a
p vecteurs. Ceci donne un total de (kn − 1) . . . (kn − k p−1 ) familles. En appliquant le lemme des
bergers on obtient alors :
(kn − 1)(kn − k) . . . (kn − kn−1 ) (kn − 1)(kn−1 − 1) . . . (kn− p+1 − 1)
Sk (n, p) = = .
( k n − 1 ) . . . ( k n − k p −1 ) (k p − 1)(k p−1 − 1) . . . (k − 1)
Si p = 0, par convention, on prendra Sk (n, 0) = 1. Ces entiers sont également appelés co-
efficients binomiaux de Gauss. En particulier avec k = 3, n = 3, on en déduit qu’il y a
S3 (3, 0) + S3 (3, 1) + S3 (3, 2) + S3 (3, 3) = 28 sous-espaces vectoriels dans (F3 )3 .

7
1.3 Arrangements
Définition 20. Supposons B de cardinal n. Une suite (c1 , . . . , c p ) est dite ( p, n)-injective, si elle
est de longueur n, si tous ses termes ci sont pris dans B et si tous les ci sont distincts. On appelle
une telle suite, un arrangement. L’ensemble de tous les arrangements de p éléments dans un
ensemble à n éléments est noté A( p, n), et son cardinal A( p, n).

Proposition 21. Si 0 ≤ p ≤ n, le nombre d’arrangements A( p, n) est donné par :

n!
A( p, n) = = n ( n − 1) . . . ( n − p + 1).
(n − p)!

Exemple 22. En particulier, le nombre de permutations d’un ensemble de cardinal n est égal à
A(n, n) = n!.
Dans le langage fonctionnel A( p, n) est le cardinal de l’ensemble des injections d’un en-
semble de cardinal p dans un ensemble de cardinal n.
Un résultat fort utile en probabilités et souvent utilisé en pratique est celui du paradoxe
des anniversaires.

Proposition 23 (Les anniversaires). Parmi n personnes, la probabilité pour qu’au moins deux
A(n,365)
d’entre elles aient leur anniversaire le même jour est Pn = 1 − 365n .
En particulier on a les valeurs approchées suivantes : P15 = 0, 25, P23 = 0, 51, P32 = 0, 75 et
P55 = 0, 99.
Ce paradoxe est notamment utilisé en cryptographie pour prouver certaines propriétés sur
des tests de primalité tels que celui de Miller-Rabin.

1.4 Combinaisons
1.4.1 Coefficients binomiaux
Lorsqu’on s’intéresse aux parties de taille p ≥ 0 d’un ensemble à n ≥ 0 éléments, on voit
apparaître d’autres nombres remarquables : les coefficients binomiaux.

Définition 24. Soient p ≥ 0 et n ≥ 0 deux entiers. Le nombre de parties à p éléments d’un

ensemble à n éléments est noté (np), et se lit "p parmi n". Ces nombres sont appelés coefficients
binomiaux et sont définis par la relation de récurrence :
     
n n−1 n−1
= + .
p p−1 p

avec les conditions initiales : (n0 ) = 1 pour tout n ≥ 0 et ( 0p) = 0 pour tout p ≥ 1.
Cette relation peut s’obtenir de manière intuitive en remarquant que pour construire une
partie à p éléments dans un ensemble à n éléments, soit on part d’une partie à p − 1 éléments
dans un ensemble à n − 1 éléments, puis on ajoute le n-ième élément pour avoir p éléments,
soit on n’utilise pas le n-ième élément, et on prend une partie à p éléments dans un ensemble à
n − 1 éléments. Les petites valeurs de ces coefficients sont visibles dans le tableau 1, et forment
une figure appelée triangle de Pascal.

Exemple 25. Les coefficients binomiaux apparaissent naturellement, lorsqu’on élève une somme
de deux termes à la puissance n. En effet, si on cherche à développer ( a + b)n , dans la somme

8
 p=0 1 2 3
n=0 1
1 1 1
2 1 2 1
3 1 3 3 1

TABLE 1 – Triangle de Pascal

on aura uniquement des termes de la forme a p bn− p , et pour obtenir un tel terme il a fallu choi-
sir p fois le terme a dans le produit des n termes, il y a donc exactement (np) manières d’obtenir
ce terme. D’où la formule du binôme de Newton :
n  
n p n− p
( a + b) = ∑
n
a b .
p =0 p

Proposition 26. On peut expliciter la valeur de (np) pour 0 ≤ p ≤ n :

 
n n! 1
= = A(n, p).
p p!(n − p)! p!

Exemple 27. Il y a exactement 144 mains de cinq cartes d’un jeu de bridge contenant exacte-
ment deux as, deux rois et une dame.
Exemple 28. Le nombre de suites strictement croissantes de longueur p, où les termes sont
extraits d’un ensemble de cardinal n est (np). De plus le nombre de telles suites croissantes
est égal à (n+pp−1). En effet soit c = (c1 ≤ c2 ≤ . . . ≤ cn ) une suite croissante. On lui fait
correspondre la suite d = (d1 < d2 < . . . < dn ), définie par :
d1 = c1 ; d2 = c2 + 1 ; . . . ; dn = cn + p − 1.
La suite d ainsi formée est bien strictement croissante. De plus,
1 ≤ d1 < d2 < . . . < dn ≤ n + p − 1.
L’application c 7→ d envoie bijectivement l’ensemble des suites croissantes dans l’ensemble des
suites strictement croissantes de longueur p dont les termes sont pris dans [n + p − 1]. Comme
le cardinal de l’ensemble de ces dernières suites est égal (n+pp−1), c’est aussi le nombre de suites
croissantes voulu.
Proposition 29. Le nombre de suites ( x1 , . . . , x p ) qui sont solutions en nombres entiers positifs
de l’équation (à n et p fixés) :
x1 + x2 + . . . + x p = n.
est égal au coefficient binomial (n+np−1).
Démonstration. Soit x = ( x1 , . . . , x p ) une telle solution. On lui associe, la suite croissante
y = (y1 , . . . , y p ) définie par yi = 1 + x1 + . . . + xi , pour i ∈ [ p]. On a : 1 ≤ y1 ≤ . . . ≤
yn−1 ≤ yn = 1 + n. Réciproquement, si y est une telle suite, on définit x = ( x1 , . . . , xn ) par :
xi = yi − yn−i , pour i ∈ [2, n] et x1 = y1 − 1. Il y a donc une bijection entre les solutions x de
l’équation et les suites croissantes, au sens large, de longueur ( p − 1), dont les termes sont pris
dans [1 + n]. D’après le résultat précédent, le cardinal de l’ensemble des solutions est :
     
(1 + n ) + ( p − 1) − 1 n+ p−1 n+ p−1
= = .
p−1 p−1 n
□

9
1.4.2 Coefficients multinomiaux
On peut généraliser la notion de coefficients binomiaux avec les coefficients multinomiaux.

Définition 30. Soient n et k deux entiers tels que 1 ≤ k ≤ n, ainsi qu’une suite d’entiers
(n1 , . . . , nk ) satisfaisant à :

n1 ≥ 0, n2 ≥ 0, . . . , nk ≥ 0 et n1 + n2 + . . . + nk = n.
p!
Un coefficient multinomial est un nombre de la forme : n1 !n2 !...nk ! . On le note (n1 ,n2n,...,nk ). Dans
le cas où k = 2, on a n1 + n2 = n et on retrouve le coefficient binomial : (n1n,n2 ) = (nn1 ).

Exemple 31. Le nombre de suites de longueur p, contenant n1 fois 1, n2 fois 2, . . . , nk fois k, où

n
les ni satisfont les relations ci-dessus, est égal au coefficient multinomial (n1 ,...,n k
).
Exemple 32. On peut ainsi compter le nombre d’anagrammes du mot BONBON, qui contient
6 6!
2 lettres B, 2 lettres O et 2 lettres N : (2,2,2 ) = 2!2!2! = 90.
La formule binomiale admet également une extension multinomiale, exprimée avec la pro-
position suivante.

Proposition 33. Soient z1 , . . . , zk des éléments pris dans un anneau commutatif. On a l’identité
multinomiale :  
n
( z1 + z2 + . . . + z k ) = ∑
n
z1n1 z2n2 . . . znk k
n1 , . . . , n k
où la sommation est étendue à l’ensemble des suites (n1 , . . . , nk ) d’entiers satisfaisant à : n1 ≥
0, . . . , nk ≥ 0 et n1 + . . . + nk = n.

2 Formules d’inversion et applications

En pratique, pour résoudre un problème de dénombrement, on essaie souvent d’appliquer
le paradigme "diviser pour régner" : si on essaye de résoudre un problème de taille n, on va
essayer de décomposer le problème en sous-problèmes de taille inférieure, souvent disjoints,
puis appliquer la règle de la somme pour revenir au problème de départ. Par exemple si on
cherche à compter u(n), on va essayer de trouver un ensemble d’entiers E, et pour chaque
i ∈ E, trouver un nombre v(i ) tel que u(n) = ∑ v(i ). Toutefois, en pratique c’est souvent
i∈E
la quantité v qui est au final recherchée. Dans certains cas on peut échanger le rôle de u et v
via une formule dite d’inversion. Nous présentons dans cette section deux telles formules. Les
notations et notions introduites s’inspirent de [6], certains exemples viennent de [2]

2.1 Formule d’inversion de Pascal

Supposons que l’on soit parvenu à établir une formule de la forme suivante.
n  
n
fn = ∑ g
k =0
k k

. Si la quantité qui nous intéresse est gk alors on dispose d’une formule, dite formule d’inver-
sion de Pascal pour échanger les rôles de f et g.

10
Proposition 34 (Inversion de Pascal). Si ( f n )n∈N et ( gn )n∈N sont deux suites de réels telles que :
n 
n
∀n ∈ N, f n = ∑ g
k =0
k k

on a alors :  
n
n−k n
∀n ∈ N, gn = ∑ (−1) k k
f .
k =0

Exemple 35. En remarquant que l’ensemble des applications de [ p] dans [n] peut s’écrire comme
la réunion disjointe des ensembles d’applications où k ∈ {0, . . . , n} éléments de l’ensemble
d’arrivée ont des antécédents, on obtient une nouvelle manière de compter le nombre de sur-
jections de [ p] dans [n]. En effet, pour obtenir le nombre d’applications où exactement k élé-
ments ont des antécédents, il suffit de choisir les k éléments (il y en a (nk)), puis de multiplier
n
par le nombre de surjections vers les k éléments choisis : S p,k . On a alors : n p = ∑ (nk)S p,k . En
k =0
n
appliquant la formule d’inversion de Pascal, on a S p,n = ∑ (nk)(−1)n−k k p . Et on retrouve bien
k =0
le résultat de la section 1.

Exemple 36. Intéressons-nous à présent au nombre de dérangements Dn d’un ensemble fini

[n]. On rappelle qu’un dérangement est simplement une permutation sans points fixes (i.e. il
n’y a pas d’entiers i tels que σ(i ) = i). On peut remarquer que l’ensemble des permutations
(de cardinal n!) est la réunion disjointe des sous-ensembles composés des permutations dans
lesquelles il y a exactement n − k points fixes. Or pour obtenir le nombre de permutations
ayant exactement n − k points fixes, il suffit de choisir les n − k points fixes, puis de déranger
n
n n n
les k éléments restants, ce qui nous donne au total (n− k ) Dk = ( k ) Dk . On a alors : n! = ∑ ( k ) Dk ,
k =0
n
et en appliquant la formule d’inversion de Pascal, cela nous donne : Dn = ∑ (nk)(−1)n−k k! =
k =0
n
(−1)k
n! ∑ k! .
k =0

2.2 Formule d’inversion de Möbius

2.2.1 Fonction de Möbius et produit de convolution
Dans la suite, pour n ≥ 2 on notera Dn l’ensemble de tous les diviseurs strictement positifs
de n. Nous introduisons ici une nouvelle fonction arithmétique, qui est la fonction de Möbius.
r
Définition 37. Soit n ∈ N. On note n = ∏ piαi , sa décomposition en facteurs premiers, où r ≥ 1,
i =1
les pi sont premiers deux à deux distincts, et les αi des entiers naturels non nuls. On définit la
fonction de Möbius par :


 1 si n = 1,
 r
∀n ∈ N∗ µ(n) = (−1)r si n = ∏ pi (i.e. n est sans facteurs carrés),

 i =1

0 sinon .

11
Proposition 38. Si m et n sont deux entiers premiers entre eux, on a alors µ(mn) = µ(m)µ(n).
On dit alors que µ est une fonction multiplicative
On introduit également le produit de convolution (ou de Dirichlet) de deux suites réelles.
∗
Définition 39. Soient u et v deux suites réelles de RN , on appelle produit de Dirichlet de u et
v et on note u ∗ v, la suite définie par :
n
∀n ∈ N∗ , (u ∗ v)(n) = ∑ u(d)v .
d∈D
d
n

On dispose également du résultat suivant, concernant le produit de deux sommes.

Proposition 40. Soient (un )n∈N∗ et (vn )n∈N∗ deux suites à valeurs réelles, et (wn )n∈N∗ leur pro-
duit de convolution. Si les séries ∑ un et ∑ vn sont absolument convergentes, il en est de même
de la série ∑ wn et on a : ! !
+∞ +∞ +∞
∑ wn = ∑ u n ∑ vn .
n =1 n =1 n =1

Pour le produit de Dirichlet, la fonction de Möbius est inversible. Plus précisément, on a le

résultat suivant.
∗
Proposition 41. En notant e le neutre de RN pour la loi ∗, et ω la suite constante égale à 1 (i.e.
ω (n) = 1 pour tout n ∈ N∗ ), on a µ ∗ ω = e, c’est-à-dire que :

1 si n = 1,
∀n ≥ 1, ∑ µ(d) =
d∈D
0 si n ≥ 2.
n

r
Démonstration. Le résultat pour n = 1 est évident car µ(1) = 1. Si n = ∏ piαi est la décom-
i =1
position en facteurs premiers de l’entier n ≥ 2, tous les diviseurs de n sont alors de la forme
r β
d = ∏ pi i avec 0 ≤ β i ≤ αi , pour 1 ≤ i ≤ r, et µ(d) = 0 si l’un des β i est supérieur ou égal
i =1
à 2. Or pour i ∈ [r ], il y a exactement (ri) manières de choisir un r-uplet ( β 1 , . . . , β r ) formé de
i termes égaux à 1 (et r − i termes égaux à 0), et pour chacun de ces choix, on a µ(d) = (−1)i ,
donc :
r  
r
∑ µ(d) = ∑ i (−1)i = (1 − 1)r = 0.
d∈Dn i =0

D’où le résultat pour n ≥ 2. □

Enfin, pour clore cette partie, on présente un joli résultat concernant la probabilité que deux
nombres soient premiers entre eux. Il fait intervenir des résultats décrits en section 1, ainsi que
les propriétés de la fonction de Möbius.

Théoreme 42 (Probabilité que deux nombres soient premiers entre eux). Pour tout entier
n ≥ 2, on se place sur l’espace probabilisé ([n]2 , P ([n]2 ), P), avec la mesure de probabilité P
définie par :
1
∀( a, b) ∈ [n]2 , P({( a, b)}) = 2 .
n
On s’intéresse à l’évènement Rn = {( a, b) ∈ [n]2 , a ∧ b = 1} et on note rn = P( Rn ) sa probabi-
lité. Alors on a :
6
lim rn = 2 .
n→+∞ π

12
 Démonstration. La démonstration va se faire en trois étapes :
Etape 1 : Montrons dans un premier temps l’expression suivante de rn :

1 n j n k2
∀n ∈ N∗ , rn = ∑ µ(d) .
n2 d =1
d

Soit n ∈ N∗ . Notons An = {( a, b) ∈ [n]2 , a ∧ b = 1}, de sorte à avoir rn = | An2n | . Notons

également, { p1 , . . . , pk } les nombres premiers distincts de [n]. On cherche donc à déterminer
| An |. Pour cela, on va chercher à appliquer la formule du crible. En notant :
∀i ∈ [k], Ui = {( a, b) ∈ [n]2 , pi | a et pi |b},
on remarque que :
!c
[
k
An = Ui .
i =1
En effet deux nombres a et b sont premiers entre eux si et seulement s’ils n’ont aucun diviseur
premier en commun, si et seulement si pour tout i ∈ [k ], ( a, b) ∈
/ Ui .
S
k
On en déduit alors que | An | = n2 − Ui . La formule du crible donne alors :
i =1

[
k \
Ui = ∑ (−1)1+| I | Ui .
i =1 ∅6= I ⊂[k] i∈ I
T
Or, pour I = {i1 , . . . , il } ⊂ [k ], on a : Ui = {( a, b) ∈ [n]2 , pi1 . . . pil | a et pi1 . . . pil |b},
i∈ I
car si pik | a pour tout k ∈ [l ], comme les pik sont des nombres premiers, ils sont deux à deux
T j k2
n
premiers entre eux, et donc leur produit divise a. De cela, on déduit Ui = pi ...p il
. En
j k i∈ I 1

effet, seuls les entiers (kpi1 . . . pil , k0 pi1 . . . pil ) pour k, k0 ∈ pi ...p
n
i
, sont dans l’intersection des
1 l
Ui . En revenant au calcul de An , on obtient alors :
2
n
| An | = n −2
∑ (−1) 1+ l
p i1 . . . p i l
{i1 ,...,il }⊂[k]
 2
n
2
=n + ∑ µ ( p i1 . . . p i l ) p i . . . p i
{i ,...,i }⊂[k]
1 l 1 l

n j n k2
= n2 + ∑ µ(d) d
d =2
n j n k2
= ∑ µ(d)
d
.
d =1

Notez que pour le passage de la deuxième à la troisième ligne, on décompose tous les entiers
compris entre 2 et n en produit de facteurs premiers, et on remarque que tous les termes ajoutés
sont en fait nuls.
Etape 2 : L’expression de rn obtenue ne permet pas de conclure directement, quant à la
probabilité asymptotique de l’évènement Rn . Toutefois, on sait que bnc ∼ n, et cela nous
n→+∞
donne l’intuition que :
+∞
µ(d)
n→+∞
lim rn = ∑ d2
.
d =1

13
 µ(n)
Montrons ce résultat. Pour tout entier n ≥ 1, on a µ(n) ∈ {−1, 0, 1}, donc | n2
| ≤ 1
n2
, et en
µ(n
conséquence la série ∑ n2
est absolument convergente. Pour tout entier n ≥ 1, on a :
  
µ(k)
n
1 n
n 2 j n k2
ϵn = ∑ 2 − r n = 2 ∑ µ(k) k − k
k =1
k n k =1
 
avec, pour tout entier k compris entre 1 et n, 0 ≤ nk − 1 < nk ≤ nk . En élevant au carré, on
obtient alors :  n 2 j n k2  n 2  n 2 n
0≤ − < − − 1 = 2 − 1.
k k k k k
Ceci nous donne :  
1 n  n 2 j n k2 2 n 1 1
| ϵn | ≤ 2 ∑ − < ∑ − .
n k =1 k k n k =1 k n
n
log(n)
Avec ∑ 1
∼
k n→+ log(n) et lim n = 0, il en résulte que lim ϵn = 0. Donc la suite (rn )n∈N∗
k =1 ∞ n→+∞ n→+∞
+∞
µ(d)
est convergente et lim rn = ∑ d2
.
n→+∞ d =1
+∞
µ(d)
Etape 3 : Il ne reste plus qu’à calculer la somme ∑ d2
. Pour cela on va montrer le résultat
d =1
suivant : ! !
+∞ +∞
µ(d) 1
∑ d2 ∑ n2 = 1.
d =1 n =1
µ(n)
Les séries ∑ n12 et ∑ n2
sont absolument convergentes et on a :
! !
+∞ +∞ +∞
µ(d) 1
∑ d2 ∑ n2 = ∑ wn
d =1 n =1 n =1

où w1 = µ(1) = 1 et :
 2
µ(d) d 1
∀n ≥ 2, wn = ∑ d2 n
= 2
n ∑ µ(d) = 0.
d∈Dn d∈Dn

+∞
µ(d) 1
Ceci nous donne le résultat voulu, et donc ∑ d2
= ζ (2)
. On peut alors conclure :
d =1

+∞
µ(d) 1 6
lim rn =
n→+∞
∑ d 2
=
ζ ( 2 )
= 2.
π
d =1

□
De manière analogue, si on note rn,k la probabilité que k ≥ 2 entiers compris entre 1 et n
soient premiers entre eux, on peut montrer que :
+∞
µ(d) 1
lim rn,k =
n→+∞
∑ d k
=
ζ (k)
.
d =1

14
2.2.2 La formule d’inversion et applications
On présente maintenant le principal résultat de cette section, qui s’obtient directement à
partir de l’inversibilité de la fonction de Möbius.
∗
Théoreme 43 (Formule d’inversion). Pour toutes suites u, v dans RN , les assertions suivantes
sont équivalentes :

∀n ∈ N∗ , u(n) = ∑ v ( d ),
d∈Dn
n
∀n ∈ N∗ , v(n) = ∑ µ(d)u .
d∈Dn
d

Présentons maintenant quelques applications de cette formule.

Exemple 44. Soit Σ un alphabet à k lettres. On dit qu’un mot w sur cet alphabet est primitif
s’il n’est pas la puissance d’un autre mot (la puissance n-ième d’un mot wn est simplement la
concaténation de n fois le mot w). Notons Mk (n) le nombre de mots primitifs de longueur n sur
un alphabet à k lettres. On remarque que tout mot w de n lettres sur Σ est soit un mot primitif
de longueur n, soit n’est pas un mot primitif. Dans ce dernier cas, il existe alors un mot primitif
r et un entier d tel que w = r d . On en déduit que nécessairement d|n. Comme il y a kn mots de
longueur n sur un alphabet de k lettres, on a la relation : kn = ∑ Mk (d)d. En appliquant la
d∈Dn
formule d’inversion de Möbius, on obtient : nMk (n) = ∑ µ(d)kn/d . Par exemple, dans le cas
d∈Dn
où n = 2, un mot est primitif si et seulement s’il a deux lettres distinctes. Il est donc censé y
avoir (2k ) mots primitifs, et c’est bien le résultat que l’on retrouve avec la formule établie.
On rappelle que l’indicatrice d’Euler est définie de la manière suivante.
Définition 45. Soit n ∈ N∗ , on note ϕ(n), le nombre d’entiers de [n] qui sont premiers avec n.
Autrement dit :
ϕ(n) = |{ p ∈ [n], p ∧ n = 1}|.

On peut calculer les valeurs de ϕ à partir des valeurs de µ.

Proposition 46. Soit n ∈ N∗ . On a :
n
n= ∑ ϕ(d) et ϕ(n) = ∑µ d
d.
d|n d|n

Exemple 47. Notons Fq un corps à q = pr éléments, avec p premier et r ≥ 0. On va dénombrer

les polynômes irréductibles sur Fq [ X ]. Notons A(n, q) l’ensemble des polynômes irréductibles
unitaires de degré n de Fq [ X ] et I (n, q) = | A(n, q)|. On admet le résultat suivant, qui fait
intervenir des résultats classiques sur les corps finis et sur les polynômes (le lecteur peut en
trouver une preuve dans [6] en p. 423) :

∏ ∏
n
Xq − X = P.
d|n P∈ A(d,q)

En passant aux degrés dans l’égalité précédente, on obtient :

qn = ∑ ∑ deg( P) = ∑ dI (d, q).

d|n P∈ A(d,q) d|n

15
En appliquant la formule d’inversion de Möbius, on obtient :
n
nI (n, q) = ∑ µ qd .
d|n
d

De ce résultat on peut notamment déduire que sur un corps fini, il y a des polynômes irréduc-
tibles de tout degré.

3 Séries génératrices
Cette section n’a pas pour objectif de détailler complètement ce que sont les séries généra-
trices. Si le lecteur veut en apprendre davantage à leur sujet il trouvera son bonheur dans le
livre [3], qui présente une méthode symbolique pour déterminer des séries génératrices. Ces
dernières sont un outil puissant pour l’étude d’objets combinatoires, c’est pourquoi nous les
introduisons ici, avec une mise en pratique sur quelques exemples.

3.1 Introduction aux séries génératrices

Cette première section motive l’introduction des séries génératrices, présente des séries
génératrices usuelles, ainsi que les opérations élémentaires que l’on peut effectuer sur de telles
séries.

3.1.1 Motivation
Les séries génératrices sont un outil algébrique qui permet de reformuler des problèmes
de combinatoire afin de les transformer en des problèmes de manipulation d’expressions al-
gébriques. En particulier, en combinatoire, il s’agit souvent de déterminer le nombre d’objets
d’un certain type qui sont de taille n, ce qui donne lieu à une suite ( an ) dont on cherche à dé-
terminer le n-ième terme. La fonction génératrice associée à la suite ( an ) est la série formelle :

a0 + a1 x + a2 x 2 + . . . = ∑ ak x k .
k ≥0

En particulier la série génératrice d’une suite finie est un polynôme.

Mais cela a-t-il vraiment un sens de parler de "somme infinie" ? C’est une vaste question,
et on ne va pas trop l’aborder ici. On peut avoir deux points de vue en ce qui concerne les
séries. D’un côté, un point de vue algébrique et formel, et c’est celui que nous adopterons ici,
où x est une variable formelle. Avec ce point de vue, une série génératrice n’est rien d’autre
qu’une nouvelle notation pour la suite ( an ), de sorte que les opérations que nous définirons
plus bas apparaissent naturellement. Tant qu’on ne fera pas prendre à x des valeurs réelles, on
pourra rester dans ce cadre. D’un autre côté on peut avoir un point de vue plus analytique et
regarder pour quelles valeurs de x la série "converge". Si de plus on trouve un voisinage de 0
pour lequel la série est bien définie, la notion coïncide avec celle des séries entières.
Un premier exemple fondamental, et qui nous servira à de nombreuses reprises dans la
suite, est celui de la série génératrice de la suite constante égale à 1. D’une part, elle est égale
à:
A( x ) = ∑ xn .
n ≥0

On l’appelle la série géométrique (car elle correspond à la somme des termes d’une suite géo-
métrique). On remarque que : A( x ) − 1 = xA( x ), donc (1 − x ) A( x ) = 1. Cela signifie que la

16
série formelle A( x ) a un inverse : la série formelle (1 − x ), ce que l’on notera de manière un
peu plus suggestive :
1
∑ xn = 1 − x .
n ≥0

En revenant un instant au point de vue analytique, on retrouve bien le résultat naturel, si on

choisit | x | < 1.
On cherchera souvent à trouver ce genre de "formes closes" pour des séries génératrices,
c’est-à-dire les écrire comme un quotient Q P
de deux polynômes avec Q(0) 6= 0. Ce n’est pas
toujours possible, mais ça le sera dans les problèmes combinatoires abordés ici. En particulier,
si une suite vérifie une récurrence linéaire, sa série génératrice vérifiera une équation du pre-
mier degré, et on obtiendra une forme close. De plus si on cherche une forme close pour les
coefficients an de la série génératrice, on peut utiliser le développement en série entière de la
P
forme Q , après avoir effectué une décomposition en éléments simples, pour obtenir le résul-
tat voulu. Évidemment pour pouvoir identifier les coefficients des deux séries il faut veiller à
ce que le rayon de convergence soit strictement positif, ce qui sera le plus souvent le cas, en
combinatoire.

3.1.2 Opérations sur les séries génératrices

Somme : La somme de deux séries génératrices A et B se définit de manière naturelle en
sommant les suites correspondantes : A + B = ∑ ( an + bn ) x n .
n ≥0
Produit : Le produit de deux séries
 génératrices
 s’obtient en effectuant le produit de Cauchy
n
des suites associées : A × B = ∑ ∑ a k bn − k xn .
n ≥0 k =0
Inverse : La série formelle ∑ ai xi a un inverse si et seulement si a0 6= 0, et cet inverse est
i ≥0
également une série formelle. En effet, on veut trouver une série formelle ∑ b j x j telle que :
j ≥0
! ! !
k
∑ ai x i ∑ bj x j = ∑ ∑ a i bk − i x k = 1.
i ≥0 j ≥0 k ≥0 i =0

Il suffit alors d’identifier les coefficients, ce qui donne une infinité d’équations pour les ai et les
b j . La première est a0 b0 = 1, qui nous dit que la condition a0 6= 0 est effectivement nécessaire.
On choisit alors b0 = a10 . La deuxième équation est a0 b1 + a1 b0 = 0, et comme a0 6= 0, on obtient
b1 = − aa1 b0 0 . On peut effectuer une récurrence sur n pour obtenir le coefficient bn , connaissant
les coefficients b0 , . . . , bn−1 . L’équation ∑in=0 ai bn−i = 0 avec la condition a0 6= 0, nous donne
P
alors bn . En particulier, les fraction rationnelles de la forme Q avec P et Q des polynômes et
Q(0) 6= 0 peuvent s’écrire comme des séries formelles.
Dérivée : La dérivée au sens formel d’une série génératrice se définit, par analogie avec les
polynômes, avec :
!0
∑ an x n = ∑ nan xn−1 .
n ≥0 n ≥1

Exemple 48. Soit G la série géométrique définie ci-dessus. Par définition, sa dérivée est ∑ nx n−1 ,
n ≥1
1
et en dérivant 1− x , on obtient :
1
∑ nxn−1 = (1 − x)2 .
n ≥1

17
 Si on continue de cette manière, on va pouvoir obtenir des formules pour (1 − x )−k pour
tout entier naturel k. En généralisant la formule du coefficient binomial, on va pouvoir étendre
la formule du binôme aux exposants quelconques.
Définition 49. Soient r un réel et k un entier naturel. Alors on définit le coefficient binomial
généralisé (kr ), par :  
r r (r − 1) . . . (r − k + 1)
= .
k k!
Évidemment, cette formule coïncide avec la formule connue des coefficients binomiaux.
Proposition 50 (Formule du binôme généralisée). Pour tout entier relatif k, on a :
 
k i
(1 + x ) k = ∑ x.
i ≥0
i

En particulier, sachant que par définition, on a pour tout i :

   
−1 (−1)(−2) . . . (−i ) i −2 (−2)(−3) . . . (−2 − i + 1)
= = (−1) et = = (−1)i (i + 1)
i i! i i!
on retrouve les expressions obtenues pour (1 − x )−1 et (1 − x )−2 . Puisque les coefficients de la
forme (−in) avec i et n deux entiers naturels jouent un rôle particulièrement important quand
on travaille avec des séries formelles, il peut être utile d’avoir la formule suivante, qui les relie
aux coefficients binomiaux usuels.
Proposition 51. Soient n et i deux entiers naturels. Alors :
   
−n n+k−1
= (−1)k .
k k

3.2 Applications
On présente dans cette section des exemples qui font intervenir les séries formelles, que ce
soit pour simplement simplifier les calculs ou bien obtenir une formule close pour les coeffi-
cients d’une série donnée.

3.2.1 Un exemple typique : les partitions

Une partition d’un entier strictement positif n est une représentation de n comme somme
d’autres entiers strictement positifs, regardée à permutation des termes près. Par exemple 4
peut être partitionné en 1 + 1 + 1 + 1, en 1 + 1 + 2 , en 2 + 2, et en 4. Les séries génératrices
constituent un outil très puissant et particulièrement adapté pour traiter les problèmes sur les
partitions.
Intéressons-nous au problème suivant : combien y a-t-il de manières de payer n euros avec
des pièces de 1 et 2 euros (sans tenir compte de l’ordre) ?
Soit n un entier. Notons an le nombre recherché. Chaque manière de payer n euros avec r
pièces de 1 et s pièces de 2 peut être encodée sous la forme x1r x2s = x n , où r et s peuvent être
des entiers naturels quelconques. La série génératrice de la suite ( an ) s’écrit donc :
! !
1 1 1
∑ an x = ∑ x
n r
∑ x = 1 − x 1 − x 2 = (1 − x )2 (1 + x )
2s
n ≥0 r ≥0 s ≥0

18
 F IGURE 1 – Illustration des triangulations possibles du pentagone.

Une décomposition en éléments simples nous donne alors :

1 1 1
1 4 2 4
= + + .
(1 − x )2 (1 + x ) 1 − x (1 − x )2 1 + x
Ceci nous donne :
  !
1 1 1 1
∑ an x n = 2 (1 − x ) 2
+
1 − x2
=
2 ∑ (i + 1)xi + ∑ x2j
n ≥0 i ≥0 j ≥0
1
= ∑ (2k + 2)( x2k + x2k+1 ) = ∑ (k + 1)( x2k + x2k+1 )
2 k ≥0 k ≥0
j n k 
= ∑ + 1 xn .
n ≥0 2
 
On a donc finalement an = n2 + 1. Bien entendu, on aurait très bien pu répondre à la
question en calculant les premiers termes de la suite, puis conjecturer l’expression de an et
la démontrer par récurrence. Cependant, la méthode des séries génératrices a l’avantage de
se généraliser à tous les problèmes de ce type, même quand la formule est beaucoup moins
devinable.

3.2.2 Triangulations d’un n-gone

Soit n ≥ 3, un entier. Soit Pn un polygone convexe à n sommets s1 , . . . , sn . Dans le cas de
la recherche du nombre de triangulations de Pn , on peut supposer sans perte de généralité
que le polygone est régulier. On appelle triangulation de Pn , une partition de Pn en triangles.
Notons tn le nombre de triangulations possibles du polygone Pn . On voit immédiatement que
t3 = 1 et que t4 = 2. Par convention, on choisit t2 = 1 pour la suite. Établissons une formule
de récurrence pour le (n + 1)-gone convexe. Choisissons une arête de Pn+1 comme base du
premier triangle. En fonction du troisième sommet on peut construire plusieurs triangles. Le
choix d’un triangle coupe le polygone en deux polygones plus petits de tailles k et n + 2 − k.
La figure 1 illustre la méthode utilisée. Le nombre total de triangulations possibles est alors :
n
t n +1 = ∑ t k t n +2− k .
k =2

Il est plus commode de commencer à numéroter la suite à partir de 0 plutôt qu’à partir de 2.
Donc en posant cn = tn+2 , on a :
n
c0 = 1 et cn+1 = ∑ ck cn−k .
k =0

19
Les nombres cn sont appelés nombres de Catalan. Considérons la série génératrice associée aux
cn :
+∞
C(x) = ∑ cn x n .
n =0
Déterminons à présent une équation vérifiée par C. D’après la formule du produit de Cau-
chy de deux séries, on a :
+∞ n
C ( x )2 = ∑ ∑ ck cn−k x n
n =0 k =0
+∞
= ∑ c n +1 x n .
n =0
+∞
Ceci nous donne 1 + xC ( x )2 = 1 + ∑ cn+1 x n+1 = C ( x ). L’idée est alors de résoudre l’équation
n =0
polynomiale de degré 2 : 1 − C ( x ) + xC ( x )2 = 0, pour deviner le résultat à montrer. On trouve :
√
? 1± 1−4x
C(x) = 2x Ici, comme f (0) = c0 = 1, on va montrer le résultat suivant :
.
√
1 − 1 − 4x
C(x) = = ϕ ( x ).
2x
√
Déterminons dans un premier la série formelle associée à 1 − 4x :
√ +∞
(1/2 − 1) . . . (1/2 − n + 1)
1 − 4x = ∑ n!
(−1)n 4n x n
n =0
+∞
(−1)n+1
= ∑ 2 n n! (2n − 1)
(1 × . . . × (2n − 1))(−1)n 4n x n
n =0
+∞
1 (2n)! n n
=− ∑
2 n n! (2n − 1) 2n n!
4 x
n =0
+∞  
2n xn
= 1− ∑ .
n =1
n (2n − 1)
De cela, on déduit la série formelle associée à ϕ :
  +∞   +∞  
1 +∞ 2n xn 2n x n −1 2n + 2 xn
ϕ( x ) = ∑
2x n=1 n (2n − 1)
= ∑
n (4n − 2)
= ∑
n + 1 (4n + 2)
.
n =1 n =0

Les séries C et ϕ vérifient la même équation fonctionnelle, en identifiant les coefficients des
séries formelles associées, on obtient :
   
∗ 1 2n + 2 1 2n
∀n ∈ N , cn = = .
4n + 2 n + 1 n+1 n

4 Méthodes algébriques
Lorsqu’il est question de géométrie, l’algèbre n’est en général jamais très loin. Les pro-
blèmes de coloriage n’échappent pas à la règle. En effet, la difficulté majeure dans un pro-
blème de coloriage est qu’il ne faut pas compter deux fois le même coloriage. Pour résoudre ce
problème, la manière classique est de raisonner sur les isométries de la figure (qui forment un
groupe), puis de faire agir ce groupe sur la partie de la figure que l’on veut colorier. On dispose
alors de résultats sur les actions de groupe, qui nous permettent de nous en sortir. Cette partie
est inspirée de trois livres [1], [5] et [6].

20
4.1 Actions de groupe
Cette section sert principalement de rappels en ce qui concerne les actions de groupe. Les
notations sont introduites, et plusieurs résultats utilisés dans la suite sont présentés. Dans la
suite, on notera E un ensemble non vide et S( E) le groupe des permutations de E.

Définition 52. Une action à gauche du groupe G sur l’ensemble E est une application :

f : G×E → E
( g, x ) 7→ g · x

telle que : pour tout x ∈ E, 1 · x = x et pour tout ( g, g0 , x ) ∈ G2 × E, g · ( g0 · x ) = ( gg0 ) · x.

Une telle application est également appelée action à gauche de G sur E.

Exemple 53. Le groupe G agit sur lui-même par translation à gauche :

( g, h) ∈ G × G 7→ g · h = gh.

Définition 54. Soit G un groupe opérant sur un ensemble E. Pour tout x ∈ E, le sous-ensemble :

G · x = { g · x| g ∈ G}

de E est appelé orbite de x sous l’action de G.

On vérifie facilement que la relation x ∼ y si, et seulement si, il existe g ∈ G tel que y = g · x
est une relation d’équivalence sur E. La classe de x pour cette relation est l’orbite de x. Il en
résulte que les orbites forment une partition de E.

Exemple 55. Pour l’action de S( E) sur E, il y a une seule orbite. En effet, pour tout x ∈ E, on
a S( E) · x = {σ( x )|σ ∈ S( E)} = E, car tout y ∈ E s’écrit y = τ ( x ), où τ est la transposition
τ = ( x, y) si y 6= x, τ = id si y = x.

Définition 56. L’action de G sur E est dite transitive s’il existe une seule orbite (égale à E). Cela
signifie que pour tout couple ( x, y) d’éléments de E il existe g ∈ G tel que g · x = y. Elle est
simplement transitive lorsque le g précédent est unique.

Définition 57. L’action est libre si pour tout couple ( x, y) d’éléments de E il existe au plus un
élément g de G tel que g · x = y (il en existe exactement un si x et y sont dans la même orbite
et aucun sinon).

Définition 58. On dit que l’action de G sur E est fidèle si le morphisme de groupes :

ϕ : g ∈ G 7→ (ϕ( g) : x 7→ g · x ) ∈ S( E).

est injectif, ce qui signifie que :

( g ∈ G ) et ∀ x ∈ E, g · x = x ) ⇐⇒ ( g = 1)

Une action fidèle permet d’identifier G à un sous-groupe de S( E).

Théoreme 59 (Cayley). L’action de G sur lui-même par translation à gauche est fidèle et G est
isomorphe à un sous-groupe de S( G ).

21
Définition 60. Soit G un groupe opérant sur un ensemble non vide E. Pour tout x ∈ E, le
sous-ensemble :
Gx = { g ∈ G | g · x = x }
de G est le stabilisateur de x sous l’action de G.
On vérifie facilement que ces stabilisateurs Gx sont des sous-groupes de G (en général non
distingués).
On présente maintenant un résultat liant les cardinaux de l’orbite et du stabilisateur d’un
élément.

Théoreme 61. Soit ( G, ·) un groupe opérant sur un ensemble E. Pour tout x ∈ E l’application :

ϕx : G/Gx → G·x
ḡ = gGx 7→ g · x

est bien définie et bijective. Dans le cas où G est fini, on a :

Card( G )
Card( G · x ) = [ G : Gx ] = .
Card( Gx )

Du résultat précédent, et du fait que E soit partitionné en orbites, on déduit le résultat

suivant.

Théoreme 62 (Equation aux classes). Soit ( G, ·) un groupe fini opérant sur un ensemble fini E.
En notant Gx1 , . . . , Gxr toutes les orbites deux à deux distinctes, on a :
r r
Card( G )
Card( E) = ∑ Card(G · xi ) = ∑ Card(Gx ) .
i =1 i =1 i

Exemple 63. Employons les résultats obtenus jusqu’à présent pour dénombrer les matrices
diagonalisables sur un corps fini. On note Fq = {α1 , . . . , αq } un corps à q = pr éléments, p
premier, r ≥ 0. Notons Dn (q) l’ensemble des matrices diagonalisables de Mn (q) = Mn (Fq ).
Alors, avec la convention | GL0 (q)| = 1, on a le résultat suivant :

| GLn (q)|
| Dn (q)| = ∑  q

m1 ,...,mq ∈N
m1 +...+mq =n
∏ | GLmi (q)|
i =1

Démonstration. Le groupe GLn (q) agit par conjugaison sur Dn (q). Commençons par décrire
les orbites de cette action. Pour M ∈ Dn (q), on a :

GLn (q) · M = { PMP−1 | P ∈ GLn (q)}.

M est diagonalisable donc il existe m = (m1 , . . . , mq ) ∈ Nq tel que Dm ∈ GLn (q) · M, avec :
 
α1 Im1 0
 .. 
Dm =  . .
0 αq Imq

22
De plus si Dm0 ∈ GLn (q) · Dm , alors les polynômes caractéristiques de Dm0 et Dm sont égaux
q
et : χ Dm0 = χ Dm = ∏ ( X − αi )mi , et donc m = m0 . Finalement, comme les orbites forment une
i =1
partition de l’ensemble Dn (q), on obtient :
G
Dn ( q ) = GLn (q) · Dm .
m1 +...+mq =n

Il reste à trouver le cardinal des orbites. Pour cela on va utiliser la relation entre l’orbite et le
stabilisateur d’un élément :
| GLn (q)
| GLn (q) · Dm | = .
| GLn (q) Dm |
Si P ∈ GLn (q) Dm alors PDm = Dm P, i.e. P est dans le commutant de Dm . Notons Eλ ( Dm ) le
sous-espace propre de Dm associé à la valeur propre λ. Soit X ∈ Eλ ( Dm ). On a : Dm PX =
PDm X = λPX et donc PX ∈ Eλ ( Dm ). Donc P laisse stable tous les sous espaces propre de Dm .
L
Or Kn = Eλ ( Dm ), donc :
λ  
P1 0
 .. 
P= . 
0 Pq
avec Pi ∈ GLmi (q).
Réciproquement, si P est de cette forme alors on a bien PDm = Dm P.
q
Finalement, pour chaque choix de Pi il y a | GLmi (q)| possibilités, d’où | GLn (q) Dm | = ∏ | GLmi (q)|.
i =1
On en déduit le résultat voulu en passant aux cardinaux dans l’expression de Dn (q)

4.2 Problèmes de coloration

Dans cette partie nous allons dans un premier temps établir la formule de Burnside, que
nous appliquerons ensuite au problème du nombre de coloriages du cube.

4.2.1 La formule de Burnside

La formule de Burnside permet de compter le nombre d’orbites distinctes en fonction des
ensembles f ix ( g) = { x ∈ E| g · x = x } des éléments de E fixes par g ∈ G.
Théoreme 64 (Formule de Burnside). Soit G un groupe fini qui agit sur un ensemble fini E. Le
nombre d’orbites de cette action est donnée par :
1
k=
|G| ∑ | f ix( g)|.
g∈ G

Démonstration. Notons O1 , . . . , Ok les k orbites de cette action. Pour obtenir la formule vou-
lue il suffit de calculer le cardinal de F = {( g, x ) ∈ G × E| g · x = x } de deux façons :
card( F ) = ∑ ∑ card({( g, x)| g · x = x}) = ∑ card( f ix( g))
g∈ G x ∈ E g∈ G

|G| k
|G|
card( F ) = ∑ | Gx | = ∑ =∑ ∑
| G · x | i=1 x∈Oi | G · x |
x∈E x∈E
k k
1
= |G| ∑ ∑ = |G| ∑ 1 = k|G|
i =1 x ∈Oi
card(Oi i =1

23
D’où le résultat en divisant par | G |.
Cette formule est particulièrement utile pour des dénombrements en géométrie puisqu’en
faisant agir le groupe des isométries directes (i.e. des déplacements) d’une figure sur la figure
elle-même, on peut facilement déterminer le cardinal de f ix ( g), du moins en dimensions 2 et 3
car cela reste assez visuel. Une application typique de cette formule correspond au dénombre-
ment de colliers de perles, qui ne sera pas présenté ici, mais dont un exemple est présent dans
le livre [1]. Mais l’idée reste la même que celle présentée dans l’application qui suit.

4.2.2 Coloriages du cube

On dispose d’un cube C, représenté par un ensemble de huit sommets, et l’on souhaite
colorer ses 6 faces en sachant que l’on dispose de k couleurs. On veut déterminer le nombre
de façons différentes qu’il y a de colorier le cube. En remarquant que si deux colorations s’ob-
tiennent via un déplacement du cube, alors elles vont correspondre à la même coloration, cela
revient à déterminer le nombre d’orbites de l’action des déplacements du cube sur le cube
lui-même. En notant Is+ (C ) les déplacements du cube, on admet le résultat suivant :

Proposition 65. Is+ (C ) est isomorphe à S4 .

Pour chaque type de déplacement, on va préciser leur nombre, ainsi que le nombre de
coloriages laissés fixes. Comme S4 = 24, il y a 24 déplacements du cube.
— L’identité Id laisse fixe tous les coloriages du cube, comme il y a k couleurs possibles
pour chacune des 6 faces cela fait k6 coloriages ;
— Il y a 6 rotations d’angle ± π2 autour des trois axes passant par les milieux de deux faces
opposées. Chacune de ces rotations laisse fixe deux faces et ont chacune un 4-cycle. Un
coloriage fixé par ce déplacement, doit garder la même couleur sur chacune des 4 faces
du 4-cycle. On doit donc choisir 3 couleurs, cela fait donc k3 coloriages possibles pour
chaque rotation ;
— Il y a 3 rotations d’angle π autour des trois axes passant par les milieux de deux faces
opposés. Chacune de ces rotations laisse fixe deux faces, et ont chacune deux 2-cycles.
Un coloriage fixé par un tel déplacement doit avoir la même couleur sur les deux faces
du 2-cycle. On doit donc choisir 4 couleurs, cela fait k4 coloriages possibles ;
— Il y a 6 rotations d’angle π autour des six axes joignant les milieux de deux arêtes diago-
nalement opposées. Elles ont chacune trois 2-cycles. Un coloriage fixé par cette rotation
est constitué de 3 couleurs (une pour chaque 2-cycle). Cela fait donc k3 coloriages pos-
sibles ;
— Enfin, il y a les 8 rotations d’angle ± 2π
3 autour des quatre axes joignant deux sommets
diagonelement opposés. Ces rotations ont chacune deux 3-cycles. Un coloriage fixé par
cette rotation est constitué de 2 couleurs, ce qui nous fait un total de k2 coloriages pos-
sibles.
En appliquant la formule de Burnside on obtient alors, en notant C (k ) le nombre de colo-
riages possibles avec k couleurs :

1 k2 (k4 + 3k2 + 12k + 8)

C (k) = (k6 + 6k3 + 3k4 + 6k3 + 8k2 ) = .
|S4 | 24

En particulier, si on veut colorier le cube avec k = 3 couleurs, on a C (3) = 57 manières de

le colorier.

24
5 Questions posées lors de l’oral
5.1 Sur le développement
Le développement présenté était celui de la probabilité que deux nombres soient premiers
entre eux.
— Comment peut-on interpréter le résultat obtenu en utilisant la fonction ζ de Riemann ?
∞
→ En utilisant l’expression de ζ comme produit eulérien on a : ζ (s) = ∏ 1
1− pi−s
. D’où :
i =1
∞
1
ζ (2)
= 6
π2
= ∏ (1 − pi−2 ). On peut interpréter la quantité (1 − pi−2 ), comme la probabi-
i =1
lité que le pgcd de deux nombres ne soit pas divisible par pi . De ce fait, le produit infini
exprime que le pgcd des deux nombres n’est divisible par aucun nombre premier, et
donc qu’ils sont premiers entre eux.
— A-t-on tendance à tirer des nombres premiers entre eux ? → Oui, car π62 > 0.5.
— Questions sur les étapes de calcul dans l’étape 1. → Des détails ont été apportés dans la
démonstration en section 2.2.1.
— Démontrer que la fonction de Möbius est inversible. → La démonstration est rédigée en
section 2.2.1.

5.2 Sur le plan

— Déterminer une formule pour le nombre de surjections d’un ensemble à p éléments dans
un ensemble à n éléments. → La démonstration a été faite en section 1 en exemple 12.
— Déterminer le nombre de mots primitifs sur un alphabet à 8 lettres. → C’est un cas
particulier de l’application 44 sur les mots primitifs, réalisée en section 2.2.1.
— Combien y a-t-il de manières de colorier un collier de 5 perles avec 3 couleurs diffé-
rentes ? → On fait agir le groupe diédral sur les sommets d’un pentagone régulier, puis
on applique la formule de Burnside. Le groupe diédral est engendré par la rotation
d’angle 2π 5 et la symétrie d’axe (OS ) où O est le centre de la figure, et S un sommet du
pentagone. Le groupe diédral contient 10 éléments : l’identité (qui laisse fixe 35 colo-
riages), 4 rotations (qui laissent fixe 3 coloriages), et 5 réflexions (qui laissent fixe une
perle, et deux 2-cycles, donc 33 coloriages). La formule de Burnside nous dit alors qu’il
1
y a : 10 (35 + 4 · 3 + 5 · 33 ) = 39 colliers de perles possibles.

Références
[1] François Combes. Algèbre et géométrie, volume 51. Bréal, 1998.
[2] Arthur Engel and Jean-Christophe Trad Novelli. Solutions d’expert. V. 1. Cassini, Pole Paris,
2007 Collection : Enseignement des mathématiques Format .
[3] Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University
press, 2009.
[4] Dominique Foata, Aimé Fuchs, and Jacques Franchi. Calcul des probabilités-3e édition : Cours,
exercices et problèmes corrigés. Dunod, 2012.
[5] Daniel Guin and Thomas Hausberger. Algebre, volume 1. EDP sciences, 2012.
[6] Jean-Etienne Rombaldi. Mathématiques pour l’Agrégation : Algèbre & géométrie. De Boeck
Superieur, 2017.

25