Symbolic method (combinatorics)
In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.
- Comment
- enIn combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions.
- Has abstract
- enIn combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet and is detailed in Part A of his book with Robert Sedgewick, Analytic Combinatorics, while the rest of the book explains how to use complex analysis in order to get asymptotic and probabilistic results on the corresponding generating functions. During two centuries, generating functions were popping up via the corresponding recurrences on their coefficients (as can be seen in the seminal works of Bernoulli, Euler, Arthur Cayley, Schröder, Ramanujan, Riordan, Knuth, , etc.).It was then slowly realized that the generating functions were capturing many other facets of the initial discrete combinatorial objects, and that this could be done in a more direct formal way: The recursive nature of some combinatorial structures translates, via some isomorphisms, into noteworthy identities on the corresponding generating functions. Following the works of Pólya, further advances were thus done in this spirit in the 1970s with generic uses of languages for specifying combinatorial classes and their generating functions, as found in works by Foata and Schützenberger on permutations, Bender and Goldman on prefabs, and Joyal on combinatorial species. Note that this symbolic method in enumeration is unrelated to "Blissard's symbolic method", which is just another old name for umbral calculus. The symbolic method in combinatorics constitutes the first step of many analyses of combinatorial structures, which can then lead to fast computation schemes, to asymptotic properties and limit laws, to random generation, all of them being suitable to automatization via computer algebra.
- Is primary topic of
- Symbolic method (combinatorics)
- Label
- enSymbolic method (combinatorics)
- Link from a Wikipage to an external page
- algo.inria.fr/flajolet/Publications/book.pdf)
- Link from a Wikipage to another Wikipage
- Algebra
- Analytic Combinatorics
- André Joyal
- Arthur Cayley
- Asymptotic distribution
- Cartesian product
- Category:Combinatorics
- Combinatorial class
- Combinatorial species
- Combinatorics
- Computer algebra
- Cycle index
- Daniel Bernoulli
- Disjoint union
- Dominique Foata
- Donald Knuth
- Embedding
- Enumerative combinatorics
- Ernst Schröder (mathematician)
- Euler totient function
- Exponential generating function
- Generating function
- George Pólya
- Graph (discrete mathematics)
- Integer partition
- John Riordan (mathematician)
- Labelled enumeration theorem
- Leonhard Euler
- Marcel-Paul Schützenberger
- Multiset
- Ordinary generating function
- Philippe Flajolet
- Pólya enumeration theorem
- Random generation
- Random permutation statistics
- Recurrence relation
- Recursion
- Robert Sedgewick (computer scientist)
- Sequence
- Set (mathematics)
- Set theory
- Srinivasa Ramanujan
- Stirling numbers and exponential generating functions in symbolic combinatorics
- Stirling numbers of the first kind
- Stirling numbers of the second kind
- Tree (graph)
- Umbral calculus
- Union (set theory)
- SameAs
- 2mW3x
- Combinatoire analytique
- Combinatoria analitica
- Combinatòria analítica
- Q2985062
- Subject
- Category:Combinatorics
- WasDerivedFrom
- Symbolic method (combinatorics)?oldid=1059232078&ns=0
- WikiPageLength
- 28730
- Wikipage page ID
- 986932
- Wikipage revision ID
- 1059232078
- WikiPageUsesTemplate
- Template:About
- Template:Ill
- Template:Math
- Template:Mathcal
- Template:Nobold
- Template:Reflist
- Template:Sub