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. 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, Comtet, 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (3)

Related units (1)

Related concepts (7)

Related courses (2)

Related lectures (11)

Organocatalysis has evolved significantly over the last decades, becoming a pillar of synthetic chemistry, but traditional theoretical approaches based on quantum mechanical computations to investigate reaction mechanisms and provide rationalizations of ca ...

EPFL2023

Method and device for mixing two streams of droplets

Matthias Lütolf, Yoji Tabata, Andrea Negro

The invention relates to a method for mixing a first stream of droplets (1) with at least one second stream of droplets (2) to obtain a third stream of fused droplets (3), by collision and fusion of at least one droplet of the first stream (1) with at leas ...

2016

Correlation properties of binary sequences generated by the logistic map-application to DS-CDMA

In this paper, we will show that a simple one dimension non-linear map allows generating symbolic sequences that have better statistical properties then classical pseudo random ones. Using performance criterion that is suitable for CDMA application, the pe ...

2002

Stirling numbers of the second kind

In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.

Stirling numbers of the first kind

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind.

Enumerative combinatorics

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n.

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

MATH-260(b): Discrete mathematics

Applications of Ergodic Theory to Combinatorics

Explores the applications of ergodic theory to combinatorics and number theory, including Szemerédi's Theorem and the Erdős-Kac Theorem.

Alchemical Practices and Lab Notebooks HUM-402: Experimental history of science I

Delves into the historical significance of alchemical practices, recipe books, and lab notebooks as forms of knowledge transmission.

Ergodic properties of low complexity symbolic systems

Explores the influence of complexity on ergodic properties of symbolic systems, presenting the Curtis-Hedlund-Lyndon Theorem and constructions of minimal subshifts.