Asymptotic enumeration of non-crossing partitions on surfaces

作者：Rue Juanjo^*; Sau Ignasi; Thilikos Dimitrios M

来源：Discrete Mathematics, 2013, 313(5): 635-649.

DOI：10.1016/j.disc.2012.12.011

• Analytic combinatorics
• Symbolic method
• Map enumeration
• Bijective techniques

We generalize the notion of non-crossing partition on a disk to general surfaces with boundary. For this, we consider a surface Sigma and introduce the number C-Sigma(n) of non-crossing partitions of a set of n points lying on the boundary of Sigma. Our main result is an asymptotic estimate for C-Sigma(n). The proofs use bijective techniques arising from map enumeration, joint with the symbolic method and singularity analysis on generating functions. An outcome of our results is that the exponential growth of C-Sigma (n) is the same as the one of the n-th Catalan number, i.e., does not change when we move from the case where Sigma is a disk to general surfaces with boundary.

• 出版日期2013-3-6