Arbres binaires arbres non croises quadrangulations
68 pages
Français

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Arbres binaires arbres non croises quadrangulations

-

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
68 pages
Français
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

Informations

Publié par
Publié le 01 janvier 2010
Nombre de lectures 37
Langue Français

Exrait

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´enitiondesarbresbinaires
On commence avec lesarbres binaires(plans), dont on peut donneruned´enitionre´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`airesmesnelrasedelbn 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´eTT0si on passe deTa`T0par un changement local de la forme
−→
.
On a ainsi dans le cas deY3le graphe suivant :
use´.nYrseCgnutphraonecxeneegr´´drereelrgpaehonn-orient´eassociauutpeOnsionicsshpseofmrtnelgsarraphessodontcesgotyl,sepelliopedunteamefIls.isexneetcndietisraeˆtn1emenxactreaeianiberbratuot:1nceenalevrdieul
partiel partiel
sur est
l’ensemble un treillis,
idemsnoinn1.
Legrapheoriente´de´nitunerelationdordre Yn, en posantTT0siTT0. Cet ordre letreillis de Tamari.
Remarques
stepountolydepesatS.ehruoPc,nYupolresoesdeytopsesanolt`adeosicrˆsaleetes:cesetelrapse´stemmoss
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents