Combinatoire et aléa autour des rectangulations - lecture 1
By Eric Fusy
Les rectangulations (partitions d'un rectangle en rectangles) apparaissent naturellement dans différents contextes en informatique (conception de circuits, cartogrammes, quadtrees) et problèmes mathématiques récréatifs (squaring the square). D'un point de vue combinatoire, on les regroupe par classes d'équivalence, soit selon les incidences entre segments (équivalence faible) ou selon les adjacences entre régions (équivalence forte). Dans ce cours on montrera comment leur énumération peut être effectuée en exploitant des connexions avec les cartes planaires, les permutations, et les marches dans le quart de plan. On évoquera aussi des résultats récents en lien avec les rectangulations aléatoires.