Arbres binaires arbres non croises quadrangulations
68
pages
Français
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
68
pages
Français
Documents
2010
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Arbres binaires, arbres non-croises, quadrangulations Frederic Chapoton janvier 2010
Voir
- definition des arbres binaires
- bijection avec les parenthesages
- mots de dyck
- arete orientee
- arbre binaire
- contexte algebrique
Arbres
binaires,arbresnon-crois´es, quadrangulations
Fre´de´ricChapoton
janvier
2010
Plan
1
2
3
4
5
6
Les arbres binaires
Lesarbresnon-crois´es
La relation entre les deux
Dualite´etrotation
Les intervalles
Lecontextealge´brique
D´efinitiondesarbresbinaires
On commence avec lesarbres binaires(plans), dont on peut donneruned´efinitionre´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+112nn,
,
}
}
qui sont lesnombres de Catalan: 1,1,2,5,14,42,132,429, . . . Bijectionaveclesparenth´esages,lesmotsdeDyck,etc,etc.
Le
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 :
partiel partiel
sur est
l’ensemble un treillis,
idemsnoinn1−.
Legrapheoriente´de´finitunerelationd’ordre Yn, en posantT≥T0siT→T0. Cet ordre letreillis de Tamari.
Remarques
st’epountolydepesatS.ffehruoPc,nYupolresoesdeytopsesanolt`adeosicrˆsaleetes:cesetelrapse´stemmoss
