Lycée Louis-Le-Grand, Paris Pour le 20/10/2023

MP2I – Mathématiques
A. Troesch

DM no 5 : Combinatoire

Suggestion de travail supplémentaire (à ne pas me rendre) : Le deuxième problème du DS2 de l’année dernière.

Problème 1 –
Dans tout le problème, n désigne un entier naturel. Le but de ce problème est de répondre au problème des ménages
de Lucas, qui se pose en ces termes :
On dispose d’une table circulaire de 2n places autour de laquelle on veut placer n couples de sorte que :
‚ on ait alternance entre les hommes et les femmes
‚ aucune femme ne soit assise à côté de son conjoint (et réciproquement bien sûr).
Combien existe-t-il de façons de faire ?
On appelle un placement une répartition des convives autour de la table satisfaisant ces deux critères. On suppose que
deux répartitions admissibles obtenues par rotation l’une de l’autre correspondent au même placement (autrement dit,
on n’a pas de repère initial sur la table ronde, les places sont indiscernables, à leur ordre près).
On note µpnq le nombre de placements. Le but du problème est de calculer µpnq.

Partie I – Lemme de Kaplansky (cas linéaire)

Soit ℓ P N, et n P N. Dans cette partie, on compte le nombre bn de sous-ensembles de v1, nw dont les éléments sont
séparés d’au moins ℓ autres éléments de v1, nw. Autrement dit, si i1 ă ¨ ¨ ¨ ă ik sont les éléments de E, rangés par
ordre croissant, on doit avoir, pour tout j P v1, k ´ 1w, ij`1 ´ ij ą ℓ.
Pour k P N, on appelle bn,k le nombre de ces sous-ensembles dont le cardinal est k.
ˆ ˙
n ´ pk ´ 1qℓ
1. Montrer que bn,k “ .
k
2. Montrer par un raisonnement combinatoire que pbn qnPN est la suite déterminée par :

@i P v0, ℓw , bi “ i ` 1, et @n ě ℓ ` 1, bn “ bn´1 ` bn´ℓ´1 .

Partie II – Lemme de Kaplansky (cas circulaire)

On considère maintenant n points répartis sur un cercle, numérotés de 1 à n dans le sens des aiguilles d’une montre.
On recherche maintenant le nombre de façons de choisir un sous-ensemble E constitué de k de ces points de sorte que
deux points quelconques de ce sous-ensemble soient séparés par au moins ℓ autres points (sur le cercle). Autrement dit,
si x0 , . . . , xk sont les k points de E, rangés par ordre croissant, il faut avoir, pour tout i P v1, k ´ 1w, xi`1 ´ xi ą ℓ,
mais il faut aussi avoir x1 ` pn ´ xk q ą ℓ (distance entre x1 et xk sur le cercle).
Pour tout n P N, k P v0, nw, et ℓ P N˚ , on note Apn, k, ℓq l’ensemble des sous-ensembles de v1, nw vérifiant ces
conditions. On note également
Bpn, k, ℓq “ tpE, xq où E P Apn, k, ℓq et x P Eu
ˆ ˙
n ´ kℓ ´ 1
1. Montrer que |Bpn, k, ℓq| “ n .
k´1
ˆ ˙
n n ´ kℓ
2. En déduire que |Apn, k, ℓq| “ .
n ´ kℓ k

Partie III – Le problème des ménages de Lucas

On suppose que n ą 1. Dans un premier temps, on suppose que les places autour de la table sont numérotées dans
le sens des aiguilles d’une montre (donc il y a un point de départ), et on décide d’attribuer les places impaires aux
dames, les places paires aux messieurs.

1
 1. On commence par placer les dames sur les places impaires, dans le sens des aiguilles d’une montre.
Combien y a-t-il de façons de faire ?
2. Les dames étant placées, il faut repartir les messieurs. On numérote les dames de 1 à n dans le sens des aiguilles
d’une montre ; on numérote également les messieurs en leur donnant le même numéro que leur épouse. Enfin,
on renumérote les places vides, en décrétant que pour tout i P v1, nw, la place située à droite de la dame i est la
place i. Ainsi, la place à gauche de la dame i est la place i ` 1 si i ă n, et la place 1 si i “ n.
On définit la famille de sous-ensembles de Sn suivante :

@i P v1, nw , E2i´1 “ tσ P Sn | σpiq “ iu

@i P v1, n ´ 1w , E2i “ tσ P Sn | σpiq “ i ` 1u et E2n “ tσ P Sn | σpnq “ 1u

Exprimer le nombre N de façons de placer les hommes en fonction des Ei , et en déduire :

n ˆ ˙
ÿ 2n 2n ´ k
N “ n! ´ p´1qk´1 pn ´ kq!.
k“1
2n ´ k k

3. Montrer que le nombre de placements possibles sur une table non numérotée est :
n ˆ ˙
ÿ 2n 2n ´ k
µpnq “ pn ´ 1q! p´1qk pn ´ kq! (Formule de Touchard, 1953)
k“0
2n ´ k k

Problème 2 – Chemins de Dyck.

L’objet de ce problème est de dénombrer de plusieurs façons les chemins de Dyck, constitués de pas montants ou
descendants, en nombre égal, tels qu’à aucun moment du chemin, on n’ait effectué davantage de pas descendants que
de pas montants. Ainsi, si on se déplace sur un axe orienté positivement vers le haut, le chemin débute et termine en
l’origine, et reste entièrement dans la partie positive de l’axe.
Par commodité, on associe ce déplacement vers le haut ou le bas à un déplacement vers la droite, de sorte à mieux
visualiser le chemin dans un plan, plutôt que sur une droite. Ainsi, les pas sont des pas diagonaux, progressant de 1
en abscisse et de 1 ou ´1 en ordonnée. Un chemin de Dyck de longueur 2n est alors un chemin dans le plan reliant
p0, 0q à p2n, 0q par des pas diagonaux vers la droite, montant ou descendant, de sorte à ce que le chemin reste toujours
au-dessus (au sens large) de l’axe des abscisses.
Par exemple, la première figure ci-dessous est un chemin de Dyck, mais pas la deuxième.

b b b

b b b b b b b

b b b b b b b b
| |
b b

b
|

Le but du problème est de dénombrer de plusieurs façons le nombre de chemins de Dyck de longueur 2n. On note Dn
l’ensemble des chemins de Dyck de longueur 2n, et dn son cardinal.
Tous les chemins considérés dans cet énoncé partent de l’origine p0, 0q, et sont constitués de pas diago-
naux vers la droite.

Partie I – Dénombrement par principe de symétrie

Soit n P N.
1. Montrer qu’il y a autant de chemins de Dyck de longueur 2n que de chemins de longueur 2n ` 1 aboutissant
en p2n ` 1, 1q et ne rencontrant jamais l’axe des abscisses, sauf au point initial.
Soit :
‚ An l’ensemble de tous les chemins aboutissant en p2n ` 1, 1q,
‚ Bn l’ensemble des chemins de An qui ne rencontrent l’axe des abscisses qu’en l’origine,

2
 ‚ Bn1 l’ensemble des chemins de An commençant par un pas montant, et rencontrant l’axe des abscisses ailleurs
qu’en l’origine
‚ Bn2 l’ensemble des chemins de An débutant par un pas descendant.
2. Montrer que tBn , Bn1 , Bn2 u est une partition de An .
Soit Γ P Bn1 . On construit ΦpΓq le chemin obtenu en prenant le symétrique par rapport à l’axe des abscisses de la
portion de Γ comprise entre p0, 0q et le premier point de retour sur l’axe des abscisses et en laissant le reste du chemin
inchangé. Dans l’exemple ci-dessous, la seconde figure représente l’image de la première par Φ.
b b

b b b b b b b b b

b b b b b b b b
| |
b b b

b b
|

|
3. Montrer que Φ est une bijection de Bn1 dans Bn2 .
4. Déterminer |Bn2 | et en déduire que ˆ ˙
1 2n ` 1
dn “ .
2n ` 1 n
Ce nombre est appelé nombre de Catalan et sera par la suite noté Cn .

Partie II – Dénombrement par le lemme cyclique

Soit Γ et Γ1 deux chemins, représentés par des suites pa1 , . . . , aN q et pb1 , . . . , bN q de 1 (pas montant) et de 0 (pas
descendant). On dit que Γ1 est un conjugué de Γ s’il existe p P t0, . . . , N ´ 1u tel que Γ1 “ pap`1 , . . . , aN , a1 , . . . , ap q.
On remarquera que quitte à prolonger la suite des pas par périodicité, ou à voir les indices dans Z{pZ, ceci est équivalent
à considérer p P Z
1. Montrer que la relation « être conjugué » est une relation d’équivalence. Une classe d’équivalence pour cette
relation est appelée classe de conjugaison.
2. Trouver et représenter graphiquement tous les conjugués de p1, 1, 0, 0, 0q ainsi que ceux de p0, 1, 1, 0, 1, 1q.
3. Soit Γ un chemin de longueur N . On dit que Γ est srtictement périodique si Γ peut être découpée en un nombre
ℓ ą 1 de séquences toutes égales. Ainsi, Γ est constitué d’un nombre strictement supérieur à 1 de périodes
entières. On remarquera que cela impose que la longueur de la période divise N .
Montrer que si Γ n’est pas strictement périodique, alors il admet exactement N conjugués 2 à 2 distincts.
4. Soit Γ un chemin de Dyck de longueur 2n. On lui associe un chemin Γ en lui rajoutant un dernier pas descendant.
Par exemple, si Γ “ p1, 0, 1, 0q, alors Γ “ p1, 0, 1, 0, 0q.
Déterminer en fonction de la longueur 2n de Γ le cardinal de la classe de conjugaison de Γ.
5. Soit n P N. Soit Γ1 un chemin quelconque de p0, 0q à p2n ` 1, ´1q.
Montrer qu’il existe un et un seul chemin de Dyck Γ de longueur 2n tel que Γ soit dans la classe de conjugaison
de Γ1 .
6. En déduire dn le nombre de chemins de Dyck de longueur 2n.

Partie III – Bijection de Rémy

1. Montrer que les nombres de Catalan Cn vérifient la relation de récurrence :

C0 “ 1 et @n P N˚ , pn ` 1qCn “ 2p2n ´ 1qCn´1

et que réciproquement cette relation détermine Cn .

3
Soit, pour n P N, Dn1 l’ensemble des chemins de longueur 2n ` 1 aboutissant en p2n ` 1, ´1q et dont les 2n premiers pas
forment un chemin de Dyck. Soit Sn l’ensemble des chemins de Dn1 , munis d’un pas marqué (i.e. un couple pΓ, iq, où
Γ est dans Dn1 , et i P v1, 2n ` 1w est l’indice d’un pas que l’on distingue des autres). On note de même Fn l’ensemble
des chemins de Dn1 avec un pas descendant marqué (i.e. l’indice i ci-dessus doit correspondre à l’indice d’un pas
descendant)
Soit n P N˚ . On construit une application Ψ de Sn´1 ˆ t0, 1u Ñ Fn de la manière suivante : étant donné Γ un élément
de Sn de pas marqué p, et ε P t0, 1u :
‚ si ε “ 0, on remplace dans le chemin Γ, le pas p par une séquence 10p le pas souligné étant le pas descendant
marqué.
‚ si ε “ 1, on repère la séquence s la plus longue commençant au pas p (inclus) et ne descendant pas en-dessous
de l’ordonnée initiale (juste avant d’effectuer le pas p). On remarquera que :
˚ cette séquence s est alors immédiatement suivie d’un pas descendant 0. C’est ce pas descendant qu’on marque.
˚ cette séquence s est vide si (et seulement si) le pas p est un pas descendant.
On remplace alors la séquence s dans le mot Γ par 1s0 (autrement dit on « surélève » la séquence s). Ainsi, la
séquence s0 est remplacée par 1s00.

2. Montrer que Ψ est une bijection.

3. En déduire encore une fois que dn “ Cn .

Question subsidiaire hors-barême

Établir une bijection entre l’ensemble des chemins de Dyck et l’ensemble des arbres binaires complets (chaque noeud
a exactement 2 fils). À quoi correspond la bijection Ψ ci-dessus sur les arbres ? (bijection de Rémy)