Arbres binaires arbres non croises quadrangulations

Frédéric Chapoton

Description

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

Sujets

• Arbre binaire

Informations

• Publié par: profil-urra-2012
• Publié le: 01 janvier 2010
• Nombre de lectures: 37
• Langue: Français

Extrait

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 (T 1 ,T 2 ) d’arbres binaires. Symboliquement

T=|+ (T 1 ,T 2 ).

Les premiers arbres binaires sont

{ | } { } {,} {, ,

Voici un exemple d’arbre binaire plus grand :

.

,

,

}.

´ E´erationparlesnombresdeCatalan num

On noteY n binabres`airesmesne’lrasedelbn feuilles. Ces+ 1 arbres binaires ontnsommets internes.

Y 0 ={ | }Y 1 ={ }Y 2 ={

Y 3 ={, , , ,

Le cardinal de l’ensembleY n est #Y n = n+1 1  2n n  ,

,

}

}

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→T 0 si on passe deTa`T 0 par un changement local de la forme

−→

.

On a ainsi dans le cas deY 3 le graphe suivant :

use´. n Yr se’Cgnutphraonecxeneegr´ ´drereelrgpaehonn-orient´eassociauutpeOnsionicss hpseofmr tnel g s ar raphessodontcesgotyl,sepelliopedunteamefIl s. isex neetcndietisraeˆtn−1emenxactreaeianib erbratuot:1n−ceenalevrdieul

partiel partiel

sur est

l’ensemble un treillis,

idemsnoinn1−.

Legrapheoriente´de´finitunerelationd’ordre Y n , en posantT≥T 0 siT→T 0 . Cet ordre letreillis de Tamari.

Remarques

st’e po un tolydepe satS.ffehruoPc, n Yupolresoesdeytop se sa nolt `adeosic rˆsaleetes:cesetelrapse´stemmoss