2022/05/23 by Pierre Lescanne, Lescanne, Pierre
Computer Science · Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Theoretical and Computational Physics #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.2205.11982
openalex publication_date 2022/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Holonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects. Rémy showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees. I extend this paradigm to Motzkin trees and Schröder trees and show that despite slight differences my algorithm that generates random Schröder trees has linear expected complexity and my algorithm that generates Motzkin trees is in O(n) expected complexity, only if we can implement a specific oracle with a O(1) complexity. For Motzkin trees, I propose a solution which works well for realistic values (up to size ten millions) and yields an efficient algorithm.