Skip to Main content Skip to Navigation
Conference papers

Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation

Bruno Salvy 1
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : 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 & Sedgewick, provides a set of high-level tools for their probabilistic analysis. Recursive combinatorial defini- tions 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Bruno Salvy Connect in order to contact the contributor
Submitted on : Monday, November 19, 2018 - 8:45:58 PM
Last modification on : Saturday, September 11, 2021 - 3:19:00 AM
Long-term archiving on: : Wednesday, February 20, 2019 - 4:35:20 PM


Publisher files allowed on an open archive




Bruno Salvy. Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation. STACS 2018 - 35th Symposium on Theoretical Aspects of Computer Science, Feb 2018, Caen, France. ⟨10.4230/LIPIcs.STACS.2018.1⟩. ⟨hal-01926094⟩



Record views


Files downloads