tailieunhanh - Báo cáo toán học: "Bijective counting of tree-rooted maps and shuffles of parenthesis systems"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Bijective counting of tree-rooted maps and shuffles of parenthesis systems. | Bijective counting of tree-rooted maps and shuffles of parenthesis systems Olivier Bernardi Submitted Jan 24 2006 Accepted Nov 8 2006 Published Jan 3 2006 Mathematics Subject Classifications 05A15 05C30 Abstract The number of tree-rooted maps that is rooted planar maps with a distinguished spanning tree of size n is CnCn 1 where Cn n T 2n is the nth Catalan number. We present a long awaited simple bijection which explains this result. Then we prove that our bijection is isomorphic to a former recursive construction on shuffles of parenthesis systems due to Cori Dulucq and Viennot. 1 Introduction In the late sixties Mullin published an enumerative result concerning planar maps on which a spanning tree is distinguished 3 . He proved that the number of rooted planar maps with a distinguished spanning tree or tree-rooted maps for short of size n is CnCn 1 where Cn n rCn is the nth Catalan number. This means that tree-rooted maps of size n are in one-to-one correspondence with pairs of plane trees of size n and n 1 respectively. But although Mullin asked for a bijective explanation of this result no natural mapping was found between tree-rooted maps and pairs of trees. Twenty years later Cori Dulucq and Viennot exhibited one such mapping while working on Baxter permutations 1 . More precisely they established a bijection between pairs of trees and shuffles of two parenthesis systems that is words on the alphabet a ã b b such that the subword consisting of the letters a ã and the subword consisting of the letters b b are parenthesis systems. It is known that tree-rooted maps are in one-to-one correspondence with shuffles of two parenthesis systems 3 6 hence the bijection of Cori et al. somehow answers Mullin s question. But this answer is quite unsatisfying in the world of maps. Indeed the bijection of Cori et al. is recursively defined on the set of prefixes of shuffles of parenthesis systems and it was not understood how this bijection could be interpreted on maps. The