A simple formula for bipartite and quasi-bipartite maps with boundaries

Abstract

We obtain a very simple formula for the generating function of bipartite (resp. quasi-bipartite) planar maps with boundaries (holes) of prescribed lengths, which generalizes certain expressions obtained by Eynard in a book to appear. The formula is derived from a bijection due to Bouttier, Di Francesco and Guitter combined with a process (reminiscent of a construction of Pitman) of aggregating connected components of a forest into a single tree.

Keywords

• planar maps
• enumeration
• bijections
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]