Guillaume Chapuy
-
A new combinatorial identity for unicellular maps, via a direct bijective approach.
dmtcs:2747 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2009,
DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
-
https://doi.org/10.46298/dmtcs.2747
A new combinatorial identity for unicellular maps, via a direct bijective approach.Article
We give a bijective operation that relates unicellular maps of given genus to unicellular maps of lower genus, with distinguished vertices. This gives a new combinatorial identity relating the number $\epsilon_g(n)$ of unicellular maps of size $n$ and genus $g$ to the numbers $\epsilon _j(n)$'s, for $j \lt g$. In particular for each $g$ this enables to compute the closed-form formula for $\epsilon_g(n)$ much more easily than with other known identities, like the Harer-Zagier formula. From the combinatorial point of view, we give an explanation to the fact that $\epsilon_g(n)=R_g(n) \mathrm{Cat}(n)$, where $\mathrm{Cat}(n$) is the $n$-th Catalan number and $R_g$ is a polynomial of degree $3g$, with explicit interpretation.
Combinatorial methods, from enumerative topology to random discrete structures and compact data representations.; Funder: European Commission; Code: 208471
Angèle M. Foley;Alejandro H. Morales;Amarpreet Rattan;Karen Yeats, 2022, Combinatorial and Algebraic Enumeration: a survey of the work of Ian P. Goulden and David M. Jackson, Algebraic Combinatorics, 5, 6, pp. 1205-1226, 10.5802/alco.269, https://doi.org/10.5802/alco.269.
Houcine Ben Dali, 2022, Generating series of non-oriented constellations and marginal sums in the Matching-Jack conjecture, Algebraic Combinatorics, 5, 6, pp. 1299-1336, 10.5802/alco.207, https://doi.org/10.5802/alco.207.
Jesse Campion Loth;Kevin Halasz;Tomáš Masařík;Bojan Mohar;Robert Šámal, 2022, Random 2-cell embeddings of multistars, Proceedings of the American Mathematical Society, 150, 9, pp. 3699-3713, 10.1090/proc/15899, https://doi.org/10.1090/proc/15899.
Valentin Féray;Baptiste Louf;Paul Thévenin, 2022, Random generation and scaling limits of fixed genus factorizations into transpositions, Probability Theory and Related Fields, 184, 3-4, pp. 681-748, 10.1007/s00440-022-01170-9, https://doi.org/10.1007/s00440-022-01170-9.
Ricky X. F. Chen;Christian M. Reidys, 2016, Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations, arXiv (Cornell University), 30, 3, pp. 1660-1684, 10.1137/15m1023646, https://arxiv.org/abs/1502.07674.
Alejandro H. Morales;Ekaterina A. Vassilieva, 2013, Direct Bijective Computation of the Generating Series for 2 and 3-Connection Coefficients of the Symmetric Group, The Electronic Journal of Combinatorics, 20, 2, 10.37236/3226, https://doi.org/10.37236/3226.
Fenix W.D. Huang;Markus E. Nebel;Christian M. Reidys, 2013, Generation of RNA pseudoknot structures with topological genus filtration, Mathematical Biosciences, 245, 2, pp. 216-225, 10.1016/j.mbs.2013.07.014.