X Informatique MP 2012

Thème de l'épreuve Arbres combinatoires
Principaux outils utilisés arbres, combinatoire, programmation récursive, complexité
Mots clefs 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 .