Arbres binaires arbres non croises quadrangulations

pages

Français

Documents

2010

Écrit par
Frédéric Chapoton

Publié par
profil-urra-2012

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

2010

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Publié le

01 janvier 2010

Nombre de lectures

Langue

Français

Arbres binaires, arbres non-croises, quadrangulations Frederic Chapoton janvier 2010

definition des arbres binaires

bijection avec les parenthesages

mots de dyck

arete orientee

arbre binaire

contexte algebrique

Voir

Publié par

profil-urra-2012

Publié le

01 janvier 2010

Nombre de lectures

Langue

Français

Arbre binaire

Arbres

binaires,arbresnon-crois´es, quadrangulations

Fre´de´ricChapoton

janvier

2010

Plan

Les arbres binaires

Lesarbresnon-crois´es

La relation entre les deux

Dualite´etrotation

Les intervalles

Lecontextealge´brique

D´eﬁnitiondesarbresbinaires

On commence avec lesarbres binaires(plans), dont on peut donneruned´eﬁnitionre´cursive. Un arbre binaireTest soit l’arbre binaire trivial|soit une paire (T1,T2) d’arbres binaires. Symboliquement

T=|+ (T1,T2).

Les premiers arbres binaires sont

{ | } { } {,} {, ,

Voici un exemple d’arbre binaire plus grand :

´ E´erationparlesnombresdeCatalan num

On noteYnbinabres`airesmesne’lrasedelbn feuilles. Ces+ 1 arbres binaires ontnsommets internes.

Y0={ | }Y1={ }Y2={

Y3={, , , ,

Le cardinal de l’ensembleYnest #Yn=n+112nn,

}

qui sont lesnombres de Catalan: 1,1,2,5,14,42,132,429, . . . Bijectionaveclesparenth´esages,lesmotsdeDyck,etc,etc.

grapheoriente´desarbresbinaires

Les arbres binaires ne forment pas seulement un ensemble, mais aussi ungraphe oriente. ´ Onaunearˆeteoriente´eT→T0si on passe deTa`T0par un changement local de la forme

−→

On a ainsi dans le cas deY3le graphe suivant :

use´.nYrse’Cgnutphraonecxeneegr´´drereelrgpaehonn-orient´eassociauutpeOnsionicsshpseofmrtnelgsarraphessodontcesgotyl,sepelliopedunteamefIls.isexneetcndietisraeˆtn−1emenxactreaeianiberbratuot:1n−ceenalevrdieul

partiel partiel

sur est

l’ensemble un treillis,

idemsnoinn1−.