Symbolic method (combinatorics): Difference between revisions

Revision as of 19:52, 23 August 2019

Revision as of 05:16, 28 October 2019

Line 3:

In [[combinatorics]], especially in analytic combinatorics, the '''symbolic method''' is a technique for [[enumerative combinatorics|counting combinatorial objects]]. It uses the internal structure of the objects to derive formulas for their [[generating function]]s. The method is mostly associated with [[Philippe Flajolet]] and is detailed in Part A of his book with [[Robert Sedgewick (computer scientist)|Robert Sedgewick]], ''Analytic Combinatorics''.

Similar languages for specifying combinatorial classes and their generating functions are found in work by

Bender and Goldman,<ref>{{cite journal|last1=Bender|first1=E.A.|last2=Goldman|first2=J.R.|title=Enumerative uses of generating functions|journal=Indiana Univ. Math. J.|date=1971|volume=20|pages=753-764753–764}}</ref>, Foata and Schützenberger,<ref name="fs">{{cite journal|last1=Foata|first1=D.|last2=Schützenberger|first2=M.|title=Théorie géométrique des polynômes Eulériens|journal=Lectures Notes in Math.|date=1970|volume=138}}</ref>, and Joyal.<ref>{{cite journal|last1=Joyal|first1=Andre|title=Une théorie combinatoire des séries formelles|journal=Adv. Math.|date=1981|volume=42|pages=1-821–82|ref=joy}}</ref>.

The presentation in this article borrows somewhat from Joyal's [[combinatorial species]].

Line 51:

In the labelled case we have the additional requirement that ''X'' not contain elements of size zero. It will sometimes prove convenient to add one to <math>G(z)</math> to indicate the presence of one copy of the empty set. It is possible to assign meaning to both <math>\mathcal{C}\in\mathbb{Z}[\mathfrak{A}]</math> (the most common example is the case of unlabelled sets) and <math>\mathcal{C}\in\mathbb{Q}[\mathfrak{A}].</math> To prove the theorem simply apply PET (Pólya enumeration theorem) and the labelled enumeration theorem.

The power of this theorem lies in the fact that it makes it possible to construct operators on generating functions that represent combinatorial classes. A structural equation between combinatorial classes thus translates directly into an equation in the corresponding generating functions. Moreover, in the labelled case it is evident from the formula that we may replace <math>g(z)</math> by the atom ''z'' and compute the resulting operator, which may then be applied to EGFs. We now proceed to construct the most important operators. The reader may wish to compare with the data on the [[cycle index]] page.

=== The sequence operator {{nobold|{{math|SEQ}}}} ===