2026-08-17T11:25:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8535 2024-03-06T10:42:15Z ddc:004 open_access

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation Salvy, Bruno Analytic Combinatorics Generating Functions Random Generation In a probabilistic context, the main data structures of computer science are viewed as random combinatorial objects. Analytic Combinatorics, as described in the book by Flajolet and Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial definitions lead to generating function equations from which efficient algorithms can be designed for enumeration, random generation and, to some extent, asymptotic analysis. With a focus on random generation, this tutorial first covers the basics of Analytic Combinatorics and then describes the idea of Boltzmann sampling and its realisation. The tutorial addresses a broad TCS audience and no particular pre-knowledge on analytic combinatorics is expected. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno Salvy 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.1 urn:nbn:de:0030-drops-85352 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.1 eng https://creativecommons.org/licenses/by/3.0/legalcode