Eulerian digraphs and Dyck words, a bijection

2014/07/09 by Pietro Codara, Codara, Pietro, Ottavio M. D’Antona +4
Computer Science · Mathematics · #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #Advanced Mathematical Identities #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1407.2461

arxiv created 2014/07/09 · arxiv updated 2014/07/10

Abstract

The main goal of this work is to establish a bijection between Dyck words and a family of Eulerian digraphs. We do so by providing two algorithms implementing such bijection in both directions. The connection between Dyck words and Eulerian digraphs exploits a novel combinatorial structure: a binary matrix, we call Dyck matrix, representing the cycles of an Eulerian digraph.

Related

• Dyck Numbers, III. Enumeration and bijection with symmetric Dyck paths
• Eulerian-Catalan Numbers
• A bijection on Dyck paths and its cycle structure
• Words, Dyck paths, Trees, and Bijections
• Bijections on Dyck tilings: DTS/DTR bijections, Dyck tableaux and tree-like tableaux