X Informatique MP 2012

Thème de l'épreuve Arbres combinatoires
Principaux outils utilisés arbres, combinatoire, programmation récursive, complexité
Mots clefs arbres, pavage, mémorisation, table de hachage, dénombrement

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                          

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE ­ ECOLES NORMALES SUPERIEURES

FILIERE

CONCOURS D'ADMISSION 2012

MP SPECIALITE INFO

COMPOSITION D'INFORMATIQUE ­ A ­ (XULC)
(Duree : 4 heures)
L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.
Le langage de programmation choisi par le candidat doit etre specifie en tete 
de la copie.

Arbres combinatoires
On etudie dans ce probleme des outils pour la combinatoire, qui peuvent etre 
utilises en
particulier pour repondre a des questions telles que : Combien existe-t-il de 
facons de paver un
echiquier 8 × 8 par 32 dominos de taille 2 × 1 ?
La partie I introduit la structure d'arbre combinatoire, qui permet de 
representer un ensemble
d'ensembles d'entiers. La partie II etudie quelques fonctions elementaires sur 
cette structure. La
partie III propose ensuite un principe de memorisation, pour definir des 
fonctions plus complexes
sur les arbres combinatoires. La partie IV utilise les resultats precedents 
pour repondre au
probleme de denombrement ci-dessus. Enfin, les deux dernieres parties 
expliquent comment
construire et manipuler efficacement des arbres combinatoires, a l'aide de 
tables de hachage.
Les parties peuvent etre traitees independamment. Neanmoins, chaque partie 
utilise des
notations et des fonctions introduites dans les parties precedentes. Les 
tableaux sont indexes a
partir de 0 et la notation t[i] est utilisee dans les questions pour designer 
l'element d'indice i du
tableau t, independamment du langage de programmation choisi.
La complexite, ou le cout, d'un programme P (fonction ou procedure) est le 
nombre
d'operations elementaires (addition, soustraction, multiplication, division, 
affectation, etc...)
necessaires a l'execution de P . Lorsque cette complexite depend d'un parametre 
n, on dira
que P a une complexite en O(f (n)), s'il existe K > 0 tel que la complexite de 
P est au plus
Kf (n), pour tout n. Lorsqu'il est demande de garantir une certaine complexite, 
le candidat
devra justifier cette derniere si elle ne se deduit pas directement de la 
lecture du code.
Dans l'ensemble de ce probleme, on se fixe une constante entiere n, avec n  1.
On note E l'ensemble {0, 1, . . . , n - 1}.

1

Partie I. Arbres combinatoires
Dans cette partie, on etudie les arbres combinatoires, une structure de donnees 
pour
representer un element de P(P(E)), c'est-a-dire un ensemble de parties de E. Un 
arbre combinatoire est un arbre binaire dont les noeuds sont etiquetes par des 
elements de E et les feuilles
par  ou . Voici un exemple d'arbre combinatoire :
0
1

1

2

2

Un noeud etiquete par i, de sous-arbre gauche A1 et de sous-arbre droit A2 sera 
note i  A1 , A2 .
L'arbre ci-dessus peut donc egalement s'ecrire sous la forme
0  (1  (2  , ), ), (1  , (2  , )).

(1)

Dans ce sujet, on impose la double propriete suivante sur tout (sous-)arbre 
combinatoire de la
forme i  A1 , A2 : d'une part
A1 et A2 ne contiennent pas d'element j avec j  i

(ordre)

et d'autre part
A2 6= .

(suppression)

Ainsi les deux arbres
0

0

1
2

2

1
1

2

1

2

ne correspondent pas a des arbres combinatoires, car celui de gauche ne verifie 
pas la condition
(ordre) et celui de droite ne verifie pas la condition (suppression).
A tout arbre combinatoire A on associe un ensemble de parties de E, note S(A), 
defini par
S() = 
S() = {}
S(i  A1 , A2 ) = S(A1 )  {{i}  s | s  S(A2 )}
L'interpretation d'un arbre A de la forme i  A1 , A2 est donc la suivante : i 
est le plus petit
element appartenant a au moins un ensemble de S(A), A1 est le sous-ensemble de 
S(A) des
ensembles qui ne contiennent pas i, et A2 est le sous-ensemble de S(A) des 
ensembles qui
contiennent i auxquels on a enleve i. Ainsi, l'arbre
0
1

est interprete comme l'ensemble {, {0, 1}}.
2

Question 1 Donner l'ensemble defini par l'arbre combinatoire de l'exemple (1).
Question 2 Donner les trois arbres combinatoires correspondant aux trois 
ensembles {{0}},
{, {0}} et {{0, 2}}.
Question 3 Soit A un arbre combinatoire different de . Montrer que A contient 
au moins
une feuille .
Question 4 Combien existe-t-il d'arbres combinatoires distincts (en fonction de 
n) ? On justifiera soigneusement la reponse.

Partie II. Fonctions elementaires sur les arbres combinatoires
On se donne le type ac suivant pour representer les arbres combinatoires.
(* Caml *)
type ac = Zero | Un
| Comb of int * ac * ac;;

{ Pascal }
type ac = ^noeud;
noeud = record element : integer;
gauche : ac; droit : ac; end;

Le constructeur Zero represente  et le constructeur Un represente . En Pascal, 
on suppose
que deux constantes Zero et Un de type ac ont ete definies. On se donne une 
fonction cons pour
construire un noeud de la forme i  A1 , A2 .
(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Cette fonction suppose que les proprietes (ordre) et (suppression) sont 
verifiees. On suppose que
cette fonction a un cout O(1).

Dans les questions suivantes, une partie de E est representee par la liste de 
ses elements,
triee par ordre croissant. On note ensemble le type correspondant, c'est-a-dire
(* Caml *)
type ensemble == int list;;

{ Pascal }
type ensemble =
record tete: integer; queue: ^ensemble; end;

Question 5 Ecrire une fonction un elt qui prend en argument un arbre 
combinatoire A,
suppose different de , et qui renvoie un ensemble s  S(A) arbitraire. On 
garantira une
complexite au plus egale a la hauteur de A.
(* Caml *) un elt: ac -> ensemble
{ Pascal } procedure un elt(a: ac; var v: ensemble);
3

Question 6 Ecrire une fonction singleton qui prend en argument un ensemble 5 
EUR P(E)
et qui renvoie l'arbre combinatoire représentant le singleton { 5} On garantira 
une complexité

O(n).

(* Caml *) singleton: ensemble --> ac
{ Pascal } function singleton(s: ensemble) : ac;

Question 7 Écrire une fonction appartient qui prend en arguments un ensemble 3 
EUR P(E) et
un arbre combinatoire A et qui teste si 3 appartient à S (A) On garantira une 
complexité O(n).

(* Caml *) appartient: ensemble --> ac --> bool
{ Pascal } function appartient(s: ensemble; a: ac) : boolean;

Question 8 Écrire une fonction cardinal qui prend en argument un arbre 
combinatoire A et
qui renvoie ca7'd(S(À))7 le cardinal de S (A) On garantira une complexité 
O(card(S(A))).

(* Caml *) cardinal: ac --> int
{ Pascal } function cardinal(az ac) : integer;

Partie III. Principe de mémorisation

Taille d'un arbre combinatoire. On définit l'ensemble des sous--arbres d'un 
arbre combi--
natoire A, noté LI(A)7 par

uc) : ...
Z/{('*) = {T}
M(i-->A1,A2) {i-->A;,Ag}UM(AÙUU(A2)

La taille d'un arbre combinatoire A, notée T(A), est définie comme le cardinal 
de M(A), c'est--
êrdirc comme le nombre de ses sous--arbres distincts.

Question 9 Quelle est la taille de l'arbre combinatoire de l'exemple (1) 7

Principe de mémorisation. Pour écrire efficacement une fonction sur les arbres 
combina--
toires7 on va mémoriser tous les résultats obtenus par cette fonction, de 
manière à ne pas refaire
deux fois le même calcul. Pour cela, on suppose donnée une structure de table 
d'association
indexée par des arbres combinatoires. Plus précisément, on suppose donné un 
type tablel
représentant une table associant à des arbres combinatoires des valeurs d'un 
type quelconque et
les quatre fonctions suivantes :

* creel() renvoie une nouvelle table7 initialement vide;

* aj oute1(t, a, v) ajoute l'association de la valeur 11 à l'arbre a dans la 
table t;

­ present1(t, a) renvoie un booleen indiquant si l'arbre a est associe a une 
valeur dans la
table t ;
­ trouve1(t, a) renvoie la valeur associee a l'arbre a dans la table t, en 
supposant qu'elle
existe.
On suppose que les trois fonctions ajoute1, present1 et trouve1 ont toutes un 
cout constant
O(1). On suppose de meme l'existence d'un type table2 representant des tables 
d'association
indexees par des couples d'arbres combinatoires et quatre fonctions similaires 
cree2, ajoute2,
present2 et trouve2, egalement de cout constant. (Les parties V et VI 
expliqueront comment
de telles tables peuvent etre construites.)
Question 10 Reecrire la fonction cardinal de la question 8 a l'aide du principe 
de
memorisation pour garantir une complexite O(T (A)). Justifier soigneusement la 
complexite du
code propose.
(* Caml *) cardinal: ac -> int
{ Pascal } function cardinal(a: ac) : integer;

Question 11 Ecrire une fonction inter qui prend en arguments deux arbres 
combinatoires A1
et A2 et qui renvoie l'arbre combinatoire representant leur intersection, 
c'est-a-dire l'arbre A tel
que S(A) = S(A1 )  S(A2 ).
(* Caml *) inter: ac -> ac -> ac
{ Pascal } function inter(a1: ac; a2: ac) : ac;

Question 12 Montrer que, pour tous arbres combinatoires A1 et A2 , on a
T (inter(A1 , A2 ))  T (A1 ) × T (A2 ).

Partie IV. Application au denombrement
On en vient maintenant au probleme de denombrement evoque dans l'introduction. 
Soit p
un entier pair superieur ou egal a 2. On cherche a determiner le nombre de 
facons de paver un
2
echiquier de dimensions p × p avec p2 dominos de taille 2 × 1. Voici un exemple 
de tel pavage
pour p = 8 :

5

Pour cela, on va construire un arbre combinatoire A tel que le cardinal de S 
(A) est exactement
le nombre de pavages possibles.

Question 13 Combien existe-til de façons différentes de placer un domino 2 >< 1 
sur l'échiquier '?

Dans ce qui suit, on suppose que n est égal à la réponse a la question 
précédente, et que
chaque élément i E E représente un placement possible de domino. Chaque case de 
l'échiquier
est représentée par un entier j tel que 0 5 j < 102, les cases étant numérotées 
de gauche à droite,
puis de haut en bas. On se donne une matrice de booléens m de taille n >< 112. 
Le booléen m...-
vaut true si et seulement si la ligne i correspond a un placement de domino qui 
occupe la case
j . (On suppose avoir rempli ainsi la matrice m, qui est une variable globale.)

Un élément s de P(P(E)) représente un ensemble de lignes de la matrice m. Il 
correspond à
un pavage si et seulement si chaque case de l'échiquier est occupée par 
exactement un domino,
i,e. si et seulement si pour toute colonnej il existe une unique ligne 71 EUR 3 
telle que m['i] [j] = true.
On parle alors de couverture exacte de la matrice 111.

Question 14 Ecrire une fonction colonne qui prend en argument un entier j' avec 
0 S j < p2,
et qui renvoie un arbre combinatoire A tel que, pour tout 87

3 & S(A) si et seulement si il existe un unique i EUR 3 tel que m[i][j] = true.

On garantira une complexité O(n).

(* Caml *) colonne: int --> ac
{ Pascal } function colonne(j: integer) : ac;

Question 15 En déduire une fonction pavage qui renvoie un arbre combinatoire A 
tel que le
cardinal de S (A) est égal au nombre de façons de paver l'échiquier, et majorer 
le coût de pavage
en fonction de n.

(* Caml *) pavage: unit --> ac
{ Pascal } function pavage : ac;

Partie V. Tables de hachage

Dans cette partie, on explique comment réaliser les structures de données 
tablel et table2,
qui ont notamment permis d'obtenir des fonctions inter et cardinal efficaces. 
L'idée consiste

a utiliser des tables de hachage.

On abstrait le problème en considérant qu'on cherche a construire une structure 
de table
d'association pour des clés d'un type clé et des valeurs d'un type valeur, ces 
deux types étant
supposés déjà définis. On se donne un entier H > 1 et on suppose l'existence 
d'une fonction
hache de coût constant, des clés vers les entiers7 telle que pour toute clé k

0 5 hache(k) < H.

L'idee consiste alors a utiliser un tableau de taille H et a stocker dans la 
case i les entrees
correspondant a des cles k pour lesquelles hache(k) = i. Chaque case du tableau 
est appelee un
seau. Comme plusieurs cles peuvent avoir la meme valeur par la fonction hache, 
un seau est une
liste d'entrees, c'est-a-dire une liste de couples (cle, valeur). On adopte 
donc le type suivant :
{ Pascal }
type table = array[0..H-1] of ^seau;
type seau = record k: cle; v: valeur;
suivant: ^seau; end;

(* Caml *)
type table == (cle * valeur) list
vect;;

On suppose par ailleurs qu'on peut comparer deux cles a l'aide d'une fonction 
egal a valeurs
dans les booleens, egalement de cout constant, telle que pour toutes cles k1 et 
k2
si egal(k1 , k2 ) alors hache(k1 ) = hache(k2 ).

(2)

Question 16 Ecrire une fonction ajoute qui prend en argument une table de 
hachage t, une
cle k et une valeur v, et ajoute l'entree (k, v) a la table t. On ne cherchera 
pas a tester si l'entree
(k, v) existe deja dans t et on garantira une complexite O(1).
(* Caml *) ajoute: table -> cle -> valeur -> unit
{ Pascal } procedure ajoute(t: table; k: cle; v: valeur);

Question 17 Ecrire une fonction present qui prend en argument une table de 
hachage t et
une cle k, et qui teste si la table t contient une entree pour la cle k.
(* Caml *) present: table -> cle -> bool
{ Pascal } function present(t: table; k: cle) : boolean;

Question 18 Ecrire une fonction trouve qui prend en argument une table de 
hachage t et une
cle k, et qui renvoie la valeur associee a la cle k dans t, en supposant 
qu'elle existe.
(* Caml *) trouve: table -> cle -> valeur
{ Pascal } function trouve(t: table; k: cle) : valeur;

Question 19 Sous quelles hypotheses sur la valeur de H et la fonction hache 
peut-on esperer
que le cout des fonctions ajoute, present et trouve soit effectivement O(1) ?

Partie VI. Construction des arbres combinatoires
Il reste enfin a expliquer comme realiser une fonction de hachage, une fonction 
d'egalite et
une fonction cons sur les arbres combinatoires, qui soient toutes les trois de 
complexite O(1).

7

L'idee consiste a associer un entier unique a chaque arbre combinatoire A, note 
unique(A), et
a garantir la propriete suivante pour tous arbres combinatoires A1 et A2 :
A1 = A2 si et seulement si unique(A1 ) = unique(A2 ).

(3)

Pour cela, on pose unique(Zero) = 0 et unique(Un) = 1. Pour un arbre A de la 
forme i  A1 , A2 ,
on choisira pour unique(A) une valeur arbitraire superieure ou egale a 2, 
stockee dans le noeud
de l'arbre. On modifie donc ainsi la definition du type ac :
(* Caml *)
type unique == int;;
type ac = Zero | Un
| Comb of unique * int * ac *
ac;;

{ Pascal }
type ac = ^noeud;
noeud = record unique: integer;
element: integer; gauche: ac; droit: ac;
end;

On propose alors la fonction hache suivante sur les arbres combinatoires :
hache() = 0,
hache() = 1,
hache(i  A1 , A2 ) = (192 × i + 19 × unique(A1 ) + unique(A2 ))

mod H.

(Le choix de cette fonction, et du coefficient 19 en particulier, releve de 
considerations pratiques
uniquement.) De meme, on propose la fonction egal suivante sur les arbres 
combinatoires :
egal(, ) = true,
egal(, ) = true,
egal((i1  L1 , R1 ), (i2  L2 , R2 )) = i1 = i2 et unique(L1 ) = unique(L2 )
et unique(R1 ) = unique(R2 ),
egal(A1 , A2 ) = false, sinon.

Question 20 Montrer que les fonctions hache et egal ci-dessus verifient bien la 
propriete (2).
Question 21 Proposer un code pour la fonction cons qui garantisse la propriete 
(3), en supposant que les arbres combinatoires sont exclusivement construits a 
partir de Zero, Un et de la
fonction cons. On garantira un cout O(1) en utilisant une table globale de type 
table1 contenant les arbres combinatoires deja construits. (On suppose que le 
type table1 et ses operations
ont ete adaptes au nouveau type ac.)
(* Caml *) cons: int -> ac -> ac -> ac
{ Pascal } function cons(i: integer; a1: ac; a2: ac) : ac;

Pour resoudre le probleme de pavage de la partie IV, on construit au total 22 
518 arbres
combinatoires. Si on prend H = 19 997 et la fonction de hachage proposee 
ci-dessus, la longueur
des seaux dans la table utilisee par la fonction cons n'excede jamais 7. Plus 
precisement, les
arbres se repartissent dans cette table de la maniere suivante :
8

longueur du seau
nombres de seaux
de cette longueur

0

1

2

3

4

5

6

7

6450

7340

4080

1617

400

96

11

3

Question 22 Quel est, dans cet etat, le nombre moyen d'appels a la fonction 
egal realises par
un nouvel appel a la fonction cons
1. dans le cas ou l'arbre doit etre construit pour la premiere fois ;
2. dans le cas ou l'arbre apparaissait deja dans la table ?
On donnera les valeurs avec deux decimales, en les justifiant soigneusement.

Note : La solution au probleme du pavage est obtenue en quelques secondes avec 
la
technique proposee ici ; on trouve 12 988 816. L'interet de cette technique est 
qu'elle
s'applique facilement a d'autres problemes de combinatoire. Par ailleurs, le 
probleme
de la couverture exacte peut etre attaque par d'autres techniques, telle que 
les  liens
dansants  de Knuth.

9

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique MP 2012 -- Corrigé
Ce corrigé est proposé par Benjamin Monmege (ENS Cachan) ; il a été relu par
Guillaume Batog (Professeur agrégé) et Vincent Puyhaubert (Professeur en CPGE).

Ce problème étudie les arbres combinatoires, souvent connus dans la littérature
sous le nom de diagrammes de décision binaire : il s'agit d'arbres permettant de
représenter des ensembles de parties d'un ensemble E = {0, 1, . . . , n - 1}. 
Ici, ces
arbres sont utilisés pour compter le nombre de façons de paver un échiquier 8 × 
8 par
32 dominos de taille 2 × 1. Le sujet est composé de six parties.
· La partie I établit la correspondance entre arbres combinatoires et ensembles
de parties de E.
· La partie II fait écrire des fonctions élémentaires sur les arbres 
combinatoires
pour extraire un ensemble d'un arbre, trouver l'arbre représentant un singleton,
tester l'appartenance d'un ensemble donné dans un arbre ou calculer le cardinal
d'un arbre.
· La fonction calculant le cardinal d'un arbre est hautement inefficace. La 
partie III introduit donc le concept de mémorisation, qui permet d'améliorer la
complexité de cette fonction. Ce principe est également appliqué à la 
réalisation
d'une fonction calculant l'intersection de deux arbres combinatoires. Cette 
partie nécessite l'utilisation de tables d'association, qui sont développées 
plus loin
dans le sujet : elles permettent de stocker efficacement des valeurs associées à
un nombre fini d'arbres combinatoires (ou de paires d'arbres combinatoires).
· La partie IV propose une application des arbres combinatoires au dénombrement 
des pavages de l'échiquier : il s'agit de construire l'intersection de plusieurs
arbres combinatoires, puis de prendre le cardinal de l'arbre ainsi obtenu, ce 
que
l'on peut faire efficacement en utilisant les fonctions de la partie III.
· La partie V explique comment créer des tables d'association, telles 
qu'utilisées
dans la partie III. L'idée est d'utiliser des tables de hachage contenant des
couples clés/valeurs (les clés seront ensuite interprétées comme des arbres ou 
des
paires d'arbres). On associe à chaque clé une case d'un tableau de longueur 
fixée
à l'avance, puis on maintient dans chaque case du tableau une liste des couples
clés/valeurs déjà insérés. Sous certaines conditions étudiées en détail dans la
partie VI, cela représente une implémentation efficace des tables d'association.
· Finalement, la partie VI construit des arbres de façon efficace, à l'aide de 
tables
d'association, ce qui permet enfin de répondre à la question de dénombrement
de manière rapide et élégante.
Il s'agit d'un sujet très varié : les parties sont globalement indépendantes, 
mais les
parties III à VI reposent sur des fonctions qui seront implémentées plus loin, 
ce qui est
un peu perturbant. Ce sujet s'inscrit dans la tradition des sujets de l'X, 
contenant des
arbres, quelques questions théoriques et beaucoup de questions de programmation,
récursive ou itérative. Cela en fait un bon outil de révision sur les arbres 
binaires et
les calculs de complexité des algorithmes. À noter que les diagrammes de 
décision
binaire ont déjà été abordés dans un sujet de l'X, lors de la session 1999 ; 
l'objectif
était alors de les appliquer à la résolution d'un problème logique.

Indications
Partie I
3 Montrer le résultat par récurrence sur la hauteur de l'arbre combinatoire.
4 Commencer par montrer que l'application S, qui à un arbre combinatoire A 
associe
l'ensemble de parties S(A), est une bijection.
Partie II
5 Utiliser l'idée de la question 3 pour exhiber un élément de S(A).
7 S'inspirer de l'interprétation d'un arbre A de la forme i  A1 , A2 donnée dans
l'introduction de la partie I.
Partie III
9 Au sens classique, le nombre de noeuds de l'arbre de l'exemple (1) vaut 11.
Ce n'est donc pas la réponse à la question...
10 Utiliser une fonction auxiliaire récursive qui possède la même structure que 
la
fonction de la question 8 en employant une table de type table1 pour mémoriser
les résultats déjà calculés.
11 Donner une définition récursive de S(A1 )S(A2 ), en commençant par S()S(A)
et S()  S(A). Utiliser cette définition pour écrire une fonction récursive, en 
employant une table de type table2 pour mémoriser les résultats déjà calculés.
12 Compter le nombre de paires d'arbres stockées dans la table de type table2
utilisée dans la fonction inter à la fin de l'exécution de la fonction.
Partie IV
13 Commencer par trouver le nombre de façons de placer un domino 
horizontalement.
14 Réaliser une boucle for qui maintient une référence vers deux arbres : le 
premier
est l'arbre attendu, l'autre est l'arbre contenant l'ensemble des parties s 
telles
qu'aucun i  s ne vérifie m[i][j] = true.
15 Pour majorer le coût de pavage, il est utile de connaître la taille d'un 
arbre
renvoyé par la fonction colonne. Utiliser également la question 12 pour majorer
le coût de la fonction inter en fonction des tailles des arbres en entrée.
Partie V
19 Trouver une condition nécessaire sur la taille des seaux de la table pour 
que les
fonctions present et trouve soient effectivement O(1).
Partie VI
21 Maintenir une valeur unique etiquette dans une référence globale, qu'on 
utilise
pour donner un champ unique nouveau lorsqu'un arbre i  A1 , A2 est construit
pour la première fois. Pour des arbres déjà rencontrés, utiliser une table 
d'association de type table1.

I. Arbres combinatoires
1 Soit A = 0  A1 , A2 l'arbre combinatoire de l'exemple (1), avec

A1 = 1  (2  , ), 
A2 = 1  , (2  , )

En appliquant la définition, il vient directement

S(2  , ) = S()  {{2}  s | s  S()} = {{2}}
d'où l'on en déduit S(A1 ) = {{2}, {1}} et S(A2 ) = {, {1, 2}}. Finalement, S(A)
est composé des ensembles de S(A1 ) et des ensembles de S(A2 ) auxquels on 
ajoute
l'élément 0.
S(A) = {{2}, {1}, {0}, {0, 1, 2}}
Attention à ne pas confondre les ensembles  (ensemble vide) et {}
(singleton contenant la partie vide) : par exemple, si A ne contient pas la
partie vide,   A = A alors que {}  A 6= A.
2 L'arbre combinatoire associé à l'ensemble {{0}} est 0  , . Celui associé à
l'ensemble {, {0}} est 0  , . Enfin, l'arbre associé à l'ensemble {{0, 2}} est
0  , (2  , ). Ces trois arbres sont représentés ci-dessous de gauche à droite.
0

0

0

2

Plus généralement, afin de construire l'arbre associé à un singleton contenant
une seule partie s  P(E), on construit un « peigne droit » contenant comme
noeuds internes les éléments de s classés dans l'ordre croissant, dont les fils
gauches sont les feuilles  et dont la feuille la plus à droite est l'unique
feuille .
3 Montrons par récurrence sur la hauteur de l'arbre A que la propriété
P(A) :

« A contient au moins une feuille  »

est vraie pour tout arbre combinatoire A différent de .
·  est le seul arbre réduit à sa racine qui contient au moins une feuille  et
P() est vraie par définition.
· P(A) : soit A = i  A1 , A2 un arbre combinatoire (différent de ). Grâce à
la condition de suppression, l'arbre A2 est différent de . Ainsi, par hypothèse
d'induction, A2 contient au moins une feuille . Il en est donc de même pour
l'arbre A.
· Conclusion :
Tout arbre A différent de  contient au moins une feuille .

4 Montrons qu'il y a autant d'arbres combinatoires distincts qu'il y a 
d'ensembles
n
de parties de E, c'est-à-dire 22 . Notons A l'ensemble des arbres combinatoires 
et
introduisons l'application
(
A - P(P(E))
S:
A 7- S(A)
Montrons que S est bijective. Pour P  P(P(E)), on appelle support de P le 
sousensemble de E des éléments apparaissant dans au moins un ensemble de P. 
Montrons
que pour tout ensemble P  P(P(E)), il existe un unique arbre A tel que S(A) = P,
par récurrence sur le cardinal du support de P.
Considérons d'abord le cas où le support de P est vide. Alors, on a 
nécessairement
P = . Pour tout arbre A, à chaque feuille  de A correspond un unique élément
de S(A) obtenu en parcourant le chemin dans l'arbre de la racine à la feuille en
question avec une liste initialement vide : à chaque fois que l'on descend à 
droite
d'un noeud le long du chemin, sa valeur est ajoutée à la liste, et lorsque l'on 
descend
à gauche, on ne la rajoute pas. Ainsi, grâce au résultat de la question 3, 
l'unique
arbre A tel que S(A) =  est l'arbre .
Dans le cas où le support de P est non vide, soit i le plus petit élément du 
support de P. Grâce à la propriété d'ordre, un arbre A tel que S(A) = P doit 
être de
la forme i  A1 , A2 avec A1 et A2 deux arbres combinatoires. Soient P1 le 
sousensemble de P des ensembles qui ne contiennent pas i et P2 le sous-ensemble 
de P
des ensembles qui contiennent i auxquels on a enlevé i : nécessairement S(A1 ) 
= P1
et S(A2 ) = P2 . Comme P1 (respectivement P2 ) a un support strictement inclus 
dans
celui de P, l'hypothèse de récurrence permet de conclure à l'existence et 
l'unicité
des arbres A1 et A2 . De plus, A2 est différent de , puisque P2 est non vide. 
Ainsi,
l'arbre A = i  A1 , A2 vérifie la condition de suppression : il s'agit d'un 
arbre combinatoire tel que S(A) = P. Finalement, il existe un unique arbre A 
tel que S(A) = P.
Par récurrence, on en déduit que cette propriété est vraie pour tout P  P(P(E)).
n

Le nombre d'arbres combinatoires distincts sur E = {0, 1, . . . , n - 1} est 22 
.