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.

Corrigé du problème 1 –

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

1. Notons Eℓ,k pnq l’ensemble des parties de v1, nw constitués d’éléments séparés les uns des autres par au moins ℓ
autres éléments, et soit Φ l’application de Pk pn ´ pk ´ 1qℓq dans Eℓ,k pnq définie sur tout E “ tx1 ă . . . ă xk u
par :
ΦpEq “ txi ` pi ´ 1qℓ, i P v1, kwu

Alors, on a bien, pour tout i P v1, k ´ 1w,

xi`1 ` iℓ ´ xi ´ pi ´ 1qℓ “ xi`1 ´ xi ` ℓ ą ℓ,

donc les éléments sont séparés d’au moins ℓ autres éléments, et de plus, on obtient bien un sous-ensemble de
v1, nw. Ainsi, Φ est bien à valeurs dans Eℓ,k pnq.
Soit Ψ de Eℓ,k pnq dans Pk pn ´ pk ´ 1qℓq définie pour tout F “ ty1 ă . . . ă yk u de Eℓ,k pnq par :

ΨpF q “ txi “ yi ´ pi ´ 1qℓ, i P v1, kwu

De même que dans la partie I, puisque les éléments yi sont séparés les uns des autres par au moins ℓ autres
points, la famille pxi qiPv1,kw est croissante, et on vérifie facilement que x1 ě 1 et xk ď n ´ pk ´ 1qℓ. Ainsi, ΨpF q
est bien un sous-ensemble à k éléments de v1, n ´ pk ´ 1qℓw.
Les applications Φ et Ψ sont clairement réciproques l’une de l’autre, donc Φ est une bijection, puis :
ˆ ˙
n ´ pk ´ 1qℓ
bn,k “ |Eℓ,k pnq| “ |Pk pn ´ pk ´ 1qℓq| “ .
k

2. Soit n ě ℓ ` 1 ; bn est donc le nombre de sous-ensembles de v1, nw constitués d’éléments séparés d’au moins
ℓ autres. Notons Fℓ pnq l’ensemble de ces sous-ensembles, et Fℓ1 pnq le sous-ensemble de Fℓ pnq contitué des
ensembles contenant n, et Fℓ2 celui contitué des ensembles ne contenant pas n. Ainsi :

|Fℓ pnq| “ |Fℓ1 pnq| ` |Fℓ2 pnq|.

‚ Un élément de Fℓ1 pnq est constitué de n, et d’autres éléments, forcément dans v1, n ´ ℓ ´ 1w, puisqu’ils sont
éloignés de l’élément n de plus de ℓ. Ces autres éléments forment alors un sous-ensemble de v1, n ´ ℓ ´ 1w
constitué d’éléments séparés par au moins ℓ. Ainsi :

|Fℓ1 pnq| “ |Fℓ pn ´ ℓ ´ 1q| “ bn´ℓ´1 .

‚ De façon évidente, Fℓ2 pnq “ Fℓ pn ´ 1q, donc |Fℓ2 pnq| “ |Fℓ pn ´ 1q| “ bn´1 .
Par conséquent, pour tout n ě ℓ ` 1, bn “ bn´1 ` bn´ℓ´1 .
Trouvons les valeurs initiales. Soit i P v0, ℓw. Tous les éléments de v1, iw étant proches de moins de ℓ, un sous-
ensemble de v1, iw contitué d’éléments séparés d’au moins ℓ autres ne peut pas avoir plus d’un élément : ces
ensembles sont donc les singletons (qui conviennent effectivement), au nombre de i, et l’ensemble vide. Ainsi,
bi “ i ` 1 .

1
Partie II – Lemme de Kaplansky (cas circulaire)
1. Construisons un élément pE, xq de Bpn, k, ℓq.
‚ On choisit x quelconque sur le cercle, ce qui nous laisse n possibilité.
‚ On complète x en un ensemble E en ajoutant k ´ 1 points. Puisque x est séparé des autres points par au
moins ℓ points, ces k ´ 1 autres points ne peuvent pas être choisis parmi les ℓ points à droite de x, ni parmi
les ℓ points à gauche de x ; il reste donc le choix parmi n ´ 2ℓ ´ 1 éléments (éventuellement 0 si cette quantité
est négative, mais cela est pris en compte par la nullité du coefficient binomiale dans ce cas). Ces n ´ 2ℓ ´ 1
éléments sont des éléments consécutifs sur le cercle (n et 1 sont consécutifs sur le cercle, même s’il ne s’agit
pas d’entiers consécutifs). Ainsi, il nous faut choisir k ´ 1 éléments parmi n ´ 2ℓ ´ 1 éléments consécutifs,
les éléments choisis étant séparés les uns ˆ des autres par au moins˙ ℓˆ autres points.
˙ On est ramené au cas
n ´ 2ℓ ´ 1 ´ pk ´ 2qℓ n ´ kℓ ´ 1
linéaire : le nombre de choix possibles est “ .
k´1 k´1
Ces deux choix étant successifs, on en déduit que :
ˆ ˙
n ´ kℓ ´ 1
|Bpn, k, ℓq| “ n .
k´1

2. Supposons dans un premier temps k ‰ 0.

Soit f : Bpn, k, ℓq ÝÑ Apn, k, ℓq l’application consistant à oublier le pointage. Ainsi, pour tout pE, xq P Bpn, k, ℓq,
f pE, xq “ E.
Soit E P Apn, k, ℓq. L’image réciproque de E par f est contitué de tous les couples pE, xq où x P E ; il y en a
donc autant que de façons de choisir x P E. Ainsi,

|f ´1 pEq| “ |E| “ k.

Comme k ‰ 0, on en déduit que les images réciproques ne sont jamais vides (donc f est surjectives) et ont
toutes même cardinal k. Ainsi, d’après le lemme du berger,
ˆ ˙ ˆ ˙
1 n n ´ kℓ ´ 1 n n ´ kℓ
|Apn, k, ℓq| “ |Bpn, k, ℓq| “ donc: |Apn, k, ℓq| “ .
k k k´1 n ´ kℓ k

Supposons maintenant que k “ 0. Alors Apn, k, ℓq “ t∅u, donc |Apn, k, ℓq| “ 1. Or,
ˆ ˙ ˆ ˙
n n ´ kℓ n n
“ “ 1,
n ´ kℓ k n 0

donc la formule est encore valable dans ce cas.

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

1. Le placement des dames consiste en une permutation de v1, nw, donc il y a n! façons de faire .
2. ‚ Un placement des messieurs correspond également à une permutation σ de v1, nw, où, pour tout i P v1, nw,
σpiq est la place occupée par le monsieur no i.
Or, pour tout i, le monsieur no i ne doit pas être assis aux places voisines de celle de sa femme, donc aux
places i et i ` 1. Par conséquent, pour tout i, il faut σpiq ‰ i et σpiq ‰ i ` 1 (modulo n). Ainsi, pour
tout j P v1, 2nw, σ R Ei . Il n’y a pas d’autre contrainte, donc les placements admissibles correspondent aux
permutations de E1 X ¨ ¨ ¨ X E2n . Ainsi, le nombre de façons de placer les hommes est |E1 X ¨ ¨ ¨ X E2n | .
‚ Montrons d’abord que si parmi les indices i1 , . . . , ik , deux sont consécutifs (modulo n), alors Ei1 X¨ ¨ ¨XEik “
2
∅. Soit pi, jq P v1, 2nw , tel que i ă j.
˚ Supposons que j “ i ` 1. Supposons qu’il existe σ P Ei X Ej . Alors :
— Si i est pair, notons i “ 2k, alors σpkq “ k ` 1, et, puisque σ P E2k`1 “ Ej , σpk ` 1q “ σpk ` 1q.
Ainsi, k ` 1 admet deux images réciproques distinctes, ce qui contredit son injectivité.
— Si i est impair, notons i “ 2k ´ 1, alors σpkq “ k, et puisque σ P E2k “ Ej , σpkq “ k ` 1. Cela ne se
peut pas, car k ne peut pas avoir deux images différentes.
Ainsi, si deux indices parmi i1 , . . . , ik sont consécutifs (modulo n), alors Ei1 X ¨ ¨ ¨ X Eik “ ∅.

2
 ˚ Supposons que i “ 1 et j “ 2n. Alors σp1q “ 1, et σpnq “ 1, d’où encore une contradiction (il faut
supposer que n ą 1).
‚ Soit alors pi1 , . . . , ik q P v1, 2nw formé d’indices´Y
deux à]¯ deux non consécutifs sur le cercle. Alors l’appartenance
ij `1
de σ à Ei1 X ¨ ¨ ¨ X Eik impose la valeur de σ 2 pour tout j P v1, kw.
Y ]
i `1
˚ Comme les indices sont deux à deux non consécutifs, les entiers j 2 sont deux à deux distincts, donc
on ne définit pas deux fois l’image du même élément. ´Y ]¯
ij `1
˚ De plus, les différentes valeurs imposées de σ 2 sont deux à deux distinctes. En effet, si deux
indices ij et iℓ imposent la même valeur i comme image d’un élément de v1, nw par σ, cela signifie qu’on
considère les deux ensembles E2i´1 et E2i´2 (si i ą 1), ou E1 et E2n (si i “ 1), qui correspondent à des
indices consécutifs sur le cercle. Ce cas de figure n’est donc pas possible ;
Ainsi, un élément de Ei1 X ¨ ¨ ¨ X Eik est une permutation quelconque pour laquelle on a déjà k valeurs
imposées (et cohérentes). Il nous reste à attribuer une image pour les n ´ k autres, à prendre parmi les
images possibles restantes : il s’agit donc de faire une permutation de n ´ k éléments. Ainsi,

|Ei1 X ¨ ¨ ¨ X Eik | “ pn ´ kq!

‚ On utilise pour terminer la formule du crible de Poincaré :

ˇ ˇ ˇ ˇ
ˇ 2n ˇ ˇď2n ˇ
ˇď ˇ
|E1 X ¨ ¨ ¨ X E2n | “ ˇˇ Ei ˇˇ “ |Sn | ´ ˇ Ei ˇ
ˇ ˇ
ˇi“1 ˇ ˇi“1
ˇ
2n
ÿ ÿ
“ n! ´ p´1qk |Ei1 X ¨ ¨ ¨ X Eik |
k“1 pi1 ă...ăik qPv1,2nwk
2 à 2 non consécutifs sur le cercle

On s’est limité aux indices 2 à 2 non consécutifs dans la somme, car, d’après 3a, si deux indices sont
consécutifs, l’intersection est vide, donc le cardinal est nul.
Or, si k ą n, il est bien entendu impossible de choisir des indices 2 à 2 non consécutifs, et par conséquent,
la somme interne est vide, donc de valeur nulle. Ainsi, on peut arrêter la sommation à k “ n :
n
ÿ ÿ
|E1 X ¨ ¨ ¨ X E2n | “ n! ´ p´1qk pn ´ kq!
k“1 pi1 ă...ăik qPv1,2nwk
2 à 2 non consécutifs sur le cercle

Ainsi, le terme général de la somme interne ne dépend pas de l’indice de sommation pi1 , . . . , ik q. Pour calculer
cette somme, il suffit de connaître le nombre de termes dans la somme, donc le nombre de sous-ensembles
ti1 ă . . . ă ik u de v1, 2nw constitués d’éléments deux à deux non consécutifs sur le cercle. Cela correspond
au cas circulaire du lemme de Kaplansky, pour ℓ “ 1. Ainsi, le nombre de termes dans la somme est :
ˆ ˙
2n 2n ´ k
.
2n ´ k k
On en déduit que le nombre de façons de placer les hommes est :
n ˆ ˙
ÿ
k´1 2n 2n ´ k
|E1 X ¨ ¨ ¨ X E2n | “ n! ´ p´1q pn ´ kq!
k“1
2n ´ k k

3. Tout d’abord, on remarque que dans la formule précédente, le n! correspond au terme k “ 0 de la somme. Ainsi,
le nombre de façon de placer les hommes est
n ˆ ˙
ÿ 2n 2n ´ k
p´1qk pn ´ kq!
k“0
2n ´ k k

Si la table est numérotée, on a à faire le choix du placement des femmes, puis du placement des hommes, ainsi,
le nombre de façons de faire est :
n ˆ ˙
ÿ 2n 2n ´ k
n! p´1qk pn ´ kq!
k“0
2n ´ k k

3
 Or, à chaque placement correspond n façons de numéroter la table (souvenez-vous que les femmes occupent les
places impaires, donc le début de la numérotation se fait toujours par l’une des n femmes). Ainsi, l’oubli de la
numérotation est une surjection de l’ensemble des placements avec numérotation vers l’ensemble des placements
sans numérotation, le cardinal de chaque image réciproque étant n. D’après le lemme du berger, le nombre de
placements sur une table non numérotée est donc obtenu en divisant le résultat précédent par n. Ainsi :
n ˆ ˙
ÿ 2n 2n ´ k
µpnq “ pn ´ 1q! p´1qk pn ´ kq!
k“0
2n ´ k k

Corrigé du problème 2 – Chemins de Dyck

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

1. Soit, conformément à la question suivante, Bn l’ensemble des chemins de longueur 2n ` 1 aboutissant en

p2n ` 1, 1q, et restant strictement au-dessus de l’axe, sauf en p0, 0q.
On a alors une bijection de Dn dans Bn en ajoutant un pas montant au début d’un chemin de Dyck : cela le
surélève et empêche un retour à l’axe des abscisses.
Réciproquement, un chemin de Bn commence nécessairement par un pas montant, sinon on ne peut plus
traverser d’axe pour se retrouver au dessus après le dernier pas. Puisque Bn est strictement au-dessus de l’axe,
en supprimant le premier pas, on obtient un chemin restant encore au-dessus de l’axe (au sens large cette fois),
et aboutissant en p2n ` 1, 0q, donc un chemin de Dyck.
Ces deux constructions étant réciproques l’une de l’autre, elle définissent bien une bijection, et dn “ |Bn1 | .
2. ‚ Tout chemin aboutissant en p2n ` 1, 1q commence par un pas vers le haut ou un pas vers le bas ; ceux
qui commence par un pas vers le haut peuvent recroiser ou non l’axe des abscisses. Ainsi, Bn , Bn1 et Bn2
énumèrent tous les cas possibles. Leur union est donc An
‚ Ces ensembles sont clairement disjoints, et non vides (on construit facilement un élément dans chacun d’eux).
Ainsi, tBn , Bn1 , Bn2 u est une partition de An .
3. Si Γ est un élément de Bn1 , il recroise l’axe des abscisses. Par conséquent, la portion entre p0, 0q et le premier
point de retour à l’axe est bien défini. Donc ΦpΓq est bien défini.
De plus, Γ commence par un pas montant, donc ΦpΓq commence par un pas descendant. Les derniers pas n’étant
pas modifiés, il aboutit toujours en p2n ` 1, 1q. Ainsi ΦpΓq est bien à valeurs dans Bn2
On peut faire la même construction en partant de Bn2 en symétrisant la portion définie par le premier retour
à l’axe (cette fois-ci, on la fait remonter). On peut remarquer que cette construction est définie sur tout
élément de Bn2 , puisqu’on commence par un pas vers le bas, et qu’on veut aboutir au-dessus de l’axe : on croise
nécessairement l’axe quelque part.
Ces constructions ne modifiant pas l’abscisse du premier retour sur l’axe, elles sont bien réciproques l’une de
l’autre.
Ainsi, Φ est bijective de Bn dans Bn2 .
4. Or, un chemin de Bn2 est la donnée d’un pas descendant, puis d’un chemin quelconque de longueur 2n avec
n ` 1 pas montants et n ´ 1 pas descendants. Ainsi
ˆ ˙
2n
|Bn1 | “ |Bn2 | “ .
n´1
On en déduit que ˆ ˙
2n
|An | “ 2 ` |Bn |,
n´1
c’est-à-dire, d’après la question 1 :
ˆ ˙ ˆ ˙ ˆ ˙
2n ` 1 2n 1 2n ` 1
dn “ ´2 “ .
n n´1 2n ` 1 n

La dernière égalité résulte d’une manipulation élémentaire sur les factorielles.

4
Partie II – Dénombrement par le lemme cyclique

1. Pour simplifier un peu les notations, on définit pour une permutation σ de v1, N w et Γ “ pa1 , . . . , aN q,

Γσ “ paσp1q , . . . , aσpN q q.

Ainsi, en notant σ la permutation circulaire directe, du fait que σ N “ id “ σ 0 , Γ2 est un conjugué de Γ1 si et

pσp q p q p`q
seulement s’il existe p P N tel que Γ2 “ Γ1 . On remarque que pΓσ qσ “ γ σ . On remarque que ceci s’étend
sans problème aux exposants néghatifs (y compris la caractérisation). Ainsi, la vérification du fait que c’est une
relation d’équivalence est alors immédiate :
0
‚ réflexivité : Γ “ Γpσ q
p ´p
‚ symétrie : si Γ2 “ Γσ1 , alors Γ1 “ Γσ2 ,
p q p`q
‚ transitivité : si Γ2 “ Γσ1 et Γ3 “ Γσ2 , alors Γ3 “ Γ1σ .
Ainsi, la relation de conjuguaison est une relation d’équivalence.
2. Les conjugués de p1, 1, 0, 0, 0q sont :
b

b b b b

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

b b b b

b
|

|
Du fait de la période de p0, 1, 1, 0, 1, 1q, ce chemin n’a que 3 conjugués différents : b

b b b b b b

b b b b b b b

b b b b b b
| | |
b
|

|
p
3. Soit Γ “ pa1 , . . . , aN q un chemin de longueur N . Montrons que les Γσ sont deux à deux distincts pour p P v1, N w
(ou de façon équivalente pour p P v0, N ´ 1w). Pour cela, on suppose que ce n’est pas le cas, et on se donne
p q
p et q distincts dans v0, N ´ 1w tels que Γσ “ Γσ . On étend la définition de pan q aux indices dans Z, par
q q
N -périodicité. Ainsi, l’égalité Γσ “ Γσ se réécrit an`p “ an`q pour tout n P N. Ainsi, pan q est q ´p-périodique.
Elle est aussi N -périodique. L’ensemble des périodes d’une suite indexée sur Z étant un sous-groupe de Z, il est
de la forme aZ. Ainsi, a divise q ´ p et N , donc leur pgcd d, qui est aussi période, et vérifie d ď q ´ p ă N et
d | N . On a donc trouvé une période de pan q divisant strictement N , il s’agit donc aussi d’une période stricte
de pan qnPv1,N w (la divisibilité permet de s’assurer qu’on a un nombre entier de périodes dans la séquence). Ceci
est une contradiction.
Ainsi, si Γ n’admet pas de période, son nombre de conjugués est égal à sa longueur.
4. Si Γ est un chemin de Dyck, Γ ne peut pas présenter de périodicité. En effet, sinon, on aurait une période T
répétée k fois, avec k ą 1. Si la période T nous amène en position pa, bq, alors Γ obtenue en mettant bout-à-bout
des périodes T nous amène en pka, kbq “ p2n ` 1, ´1q. Ceci signifierait que k divise ´1, ce qui est impossible.
Ainsi, d’après la question précédente, Γ admet 2n ` 1 conjugués .
5. ‚ Soit Γ1 un chemin aboutissant en p2n ` 1, ´1q. On note p l’abscisse du point en lequel Γ1 atteint pour la
première fois son ordonnée la plus basse. Considérons Γ2 le conjugué d’ordre p de Γ1 . Le chemin Γ2 est la
concaténation de Γ2 et Γ1 où Γ1 est le chemin des p premiers pas de Γ1 et Γ2 la fin.
˚ Puisqu’on a coupé Γ1 en son point le plus bas, Γ2 ne descend pas en dessous de l’axe des abscisses.
˚ Le chemin Γ2 termine en une hauteur de k ´ 1, où ´k est l’ordonnée minimale atteinte par le chemin Γ1
(en effet, depuis cette ordonnée, on remonte jusqu’à l’ordonnée ´1). Puisqu’on coupe au premier point
minimal, le chemin Γ1 ne fait pas descendre de plus de k ´ 1, sauf sur son dernier pas. Ainsi, en recollant
Γ1 à Γ2 (ce qui le surélève de k ´ 1), cette portion reste au-dessus de l’axe des abscisses, sauf le dernier
pas, aboutissant en ´1.
˚ Le chemin obtenu en enlevant le dernier pas de Γ2 est donc bien un chemin de Dyck Γ, et Γ2 “ Γ.
Ainsi, il existe au moins un chemin de Dyck dans la classe d’équivalence de Γ1 . Alors le conjugué d’ordre p
de Γ

5
 ‚ Réciproquement, soit Γ1 “ Γ, obtenu en prolongeant vers le bas un chemin de Dyck. Considérons-en un
conjugué strict, obtenu en coupant Γ1 en deux chemins Γ1 et Γ2 non vides. Le sous-chemin Γ2 commence
au-dessus de l’axe, et termine strictement en-dessous. Un chemin de Dyck ne peut donc pas commencer par
le chemin Γ2 .
Ainsi, Γ1 n’admet pas d’autre conjugué que lui-même obtenu d’un chemin de Dyck.
‚ On en déduit que dans chaque classe d’équivalence, il existe un et un seul chemin issu d’un chemin de Dyck .
6. L’application qui à un chemin de Dyck Γ associe la classe d’équivalence de Γ est donc une bijection de Dn
dans l’ensemble des classes d’équivalence des chemins aboutissant en p2n ` 1, ´1q. ˆ Ces chemins
˙ sont en nombre
`2n`1˘ 1 2n ` 1
n , et toutes les classes d’équivalence ont 2n`1 éléments. Il y a donc classes d’équivalence.
2n ` 1 n
On en déduit que : ˆ ˙
1 2n ` 1
dn “ “ Γn .
2n ` 1 n

Partie III – Bijection de Rémy

1. Il suffit de vérifier, à l’aide de l’expression factorielle. Pour n P N˚ :

Cn 2n ´ 1 p2n ` 1q!n!pn ´ 1q! p2n ´ 1qp2nq 2p2n ´ 1q
“ “ “ .
Cn´1 2n ` 1 n!pn ` 1q!p2n ´ 1q! npn ` 1q n`1

On a bien pn ` 1qCn “ 2p2n ´ 1qCn´1 . Par ailleurs, on vérifie facilement que C0 “ 1

Une récurrence immédiate montre que cette relation détermine pCn q (c’est une relation de récurrence d’ordre
1).
1
2. On s’assure bien que cette construction donne bien un élément de Dn´1 .
On exhibe une réciproque de Ψ. Soit Γ dans Fn . On repère le pas descendant marqué d.
‚ S’il est précédé d’un pas montant, on supprime la séquence 10, et on marque le pas suivant, et on définit
ε“0
‚ S’il est précédé d’un pas descendant, on repère la séquence s la plus longue précédent ces deux pas descen-
dents, et telle que les deux points extrémaux de s aient même hauteur, et soient la hauteur minimale de
s. Ainsi, la séquence s est précédée d’un pas montant (sinon elle pourrait être prolongée). On a donc une
séquence 1s00, où les extrémités de s ont même hauteur et les points intermédiaires ne descendent pas en
dessous. On remplace cette séquence par s0, et on marque le premier pas de s (si s est vide, on marque le
seul pas de cette séquence, à savoir 0). On pose ε “ 1.
Il apparaît assez facilement que cette construction est réciproque de Ψ, donc Ψ est bijective .
3. Ainsi, |Sn´1 ˆ t0, 1u| “ |Fn |. Or :
‚ L’ajout d’un dernier pas descendant (et dans l’autre sens, la suppression du dernier pas, nécessairement
déscendant) donne une bijection de Dn dans Dn1 . Ainsi, |Dn1 | “ |Dn | “ dn .
1
‚ un élément de Sn´1 est déterminé par le choix d’un chemin de Dn´1 , et d’un pas quelconque marqué parmi
les 2n ´ 1 pas possibles. D’après le lemme du berger et la question II

|Sn´1 | “ p2n ´ 1qdn´1 .

‚ De même, un élément de Fn est déterminé par le choix d’un chemin de Dn1 et d’un des n ` 1 pas descendant,
d’où :
|Fn | “ ndn .
On en déduit que 2p2n ´ 1qdn´1 “ ndn . Comme de plus, d0 “ 1, on déduit de III-1 que dn “ Cn , pour tout
n P N.
Question subsidiaire
Partant d’un arbre binaire complet, faire un parcours en profondeur, en notant 1 pour chaque noeud qu’on rencontre
pour la première fois, et 0 pour chaque feuille. On ne recompte pas le 2e passage sur un noeud. Vérifiez que ceci définit
une bijection de l’ensemble des arbres binaires complets à n noeuds dans Dn1 . L’ensemble Sn correspond via cette

6
bijection aux arbres avec un sommet marqué (feuille ou noeud) et Fn aux arbres avec une feuille marquée. Tiens, la
notation s’éclaire.
Vérifiez que la bijection Ψ consiste alors à dédoubler le sommet marqué s de la façon suivante :

s
b
s1
b

‚ Si ε “ 0 : b b ÞÝÑ b b
s
A1 A2 F b b

A1 A2
s
b
s1
b

‚ Si ε “ 1 : b b ÞÝÑ s b b

A1 A2 b b
F
A1 A2
Ainsi on dédouble le noeud, en un noeud s1 dont l’un des fils sera s avec toute sa descendance, et l’autre sera une
feuille ajoutée. La valeur de ε détermine la latéralisation de cette construction. Remarquez que si s est une feuille,
cette construction a un sens aussi : dans ce cas, la feuille s est remplacée par un noeud s1 auquel sont attachées deux
feuilles, l’une des 2 étant marquée, suivant la valeur de ε.
C’est sous cette forme qu’a été décrite la bijection de Rémy. C’est évidemment un peu moins tiré par les cheveux que
sur les chemins de Dyck.