Symbolic method (combinatorics): Difference between revisions

Revision as of 14:28, 23 September 2021

Latest revision as of 08:39, 9 July 2025

(13 intermediate revisions by 11 users not shown)

Line 1:

{{Short description|Mathematical technique}}

{{About|the method in analytic combinatorics|the method in invariant theory|Symbolic method}}

In [[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]]'', 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 [[Daniel Bernoulli|Bernoulli]]{{disambiguation needed|date=April 2021}}, [[Leonhard Euler|Euler]], [[Arthur Cayley]], [[Ernst Schröder (mathematician)|Schröder]],

[[Srinivasa Ramanujan|Ramanujan]], [[John Riordan (mathematician)|Riordan]], [[Donald Knuth|Knuth]], {{ill|Louis Comtet|fr|lt=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 [[George Pólya|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 [[Dominique Foata|Foata]] and [[Marcel-Paul Schützenberger|Schützenberger]]<ref name="fs">{{cite journalbook|last1=Foata|first1=Dominique|authorlink1=Dominique Foata|last2=Schützenberger|first2=Marcel-P.|authorlink2=Marcel-Paul Schützenberger|title=Théorie géométriqueGéométrique des polynômesPolynômes Eulériens|journalseries=LecturesLecture Notes in Mathematics|date=1970|volume=138|doi=10.1007/BFb0060799|isbn=978-3-540-04927-2|doi-access=free|arxiv=math/0508232}}</ref> on permutations,

Bender and Goldman on prefabs,<ref>{{cite journal|last1=Bender|first1=Edward A.|last2=Goldman|first2=Jay R.|title=Enumerative uses of generating functions|journal=Indiana University Mathematics Journal|date=1971|volume=20|issue=8|pages=753–764|doi=10.1512/iumj.1971.20.20060|doi-access=free}}</ref> and [[André Joyal|Joyal]] on [[combinatorial species]].<ref>{{cite journal|last1=Joyal|first1=André|authorlink1=André Joyal|title=Une théorie combinatoire des séries formelles|journal=[[Advances in Mathematics]]|date=1981|volume=42|pages=1–82|ref=joy|doi=10.1016/0001-8708(81)90052-9|doi-access=free}}</ref>

Note that this symbolic method in enumeration is unrelated to "Blissard's symbolic method", which is just another old name for [[umbral calculus]].

Line 26 ⟶ 27:

:<math>\frac{g(z)^n}{|G|}.</math>

We are able to enumerate filled slot configurations using either PET[[Pólya enumeration theorem]] in the unlabelled case or the labelled enumeration theorem in the labelled case. We now ask about the generating function of configurations obtained when there is more than one set of slots, with a permutation group acting on each. Clearly the orbits do not intersect and we may add the respective generating functions. Suppose, for example, that we want to enumerate unlabelled sequences of length two or three of some objects contained in a set ''X''. There are two sets of slots, the first one containing two slots, and the second one, three slots. The group acting on the first set is the full symmetric group <math>E_2S_2</math>, andwhich in symbolic combinatorics is traditionally denoted <math>E_2</math>. The group acting on the second slotset is, analogously, <math>S_3 = E_3</math>. We represent this by the following formal [[power series]] in ''X'':

:<math> X^2/E_2 \; + \; X^3/E_3 </math>

Line 34 ⟶ 35:

:<math> X/C_1 \; + \; X^2/C_2 \; + \; X^3/C_3 \; + \; X^4/C_4 \; + \cdots.</math>

Clearly we can assign meaning to any such power series of quotients (orbits) with respect to permutation groups, where we restrict the groups of degree ''n'' to the conjugacy classes <math>\operatorname{Cl}(S_n)</math> of the symmetric group <math>S_n</math>, which form a [[unique factorization ___domain]]. (The orbits with respect to two groups from the same conjugacy class are isomorphic.) This motivates the following definition.

A class <math>\mathcal{C}\in \mathbb{N}[\mathfrak{AM}]</math> of combinatorial structures is a formal series

:<math>\mathcal{C} = \sum_{n \ge 1} \sum_{G\in \operatorname{Cl}(S_n)} c_G (X^n/G)</math>

where <math>\mathfrak{AM}</math> (the "AM" is for "atomsmolecules") is the set of primes of the UFD <math>\{\operatorname{Cl}(S_n)\}_{n\ge 1}</math> and <math>c_G \in \mathbb{N}.</math>

In the following we will simplify our notation a bit and write e.g.

Line 66 ⟶ 67:

This operator corresponds to the class

:<math>L = \frac{1}{1 - X} = 1 + E_1X + E_2X^2 + E_3X^3 + \cdots</math>

and represents sequences, i.e. the slots are not being permuted and there is exactly one empty sequence. We have

:<math> F(z) = 1 + \sum_{n\ge 1} Z(E_n1)(f(z), f(z^2), \ldots, f(z^n)) =

1 + \sum_{n\ge 1} f(z)^n = \frac{1}{1-f(z)}</math>

and

:<math> G(z) = 1 + \sum_{n\ge 1} \left(\frac{1}{|E_n|}\right) g(z)^n =

\frac{1}{1-g(z)}.</math>

Line 82 ⟶ 83:

This operator corresponds to the class

:<math>C = C_1 + C_2 + C_3 + \cdots</math>

i.e., cycles containing at least one object. We have

Line 125 ⟶ 126:

The series is

:<math>E = 1 + S_1E_1 + S_2E_2 + S_3E_3 + \cdots</math>

i.e., the symmetric group <math>S_n = E_n</math> is applied to the slots''n''th slot. This creates multisets in the unlabelled case and sets in the labelled case (there are no multisets in the labelled case because the labels distinguish multiple instances of the same object from the set being put into different slots). We include the empty set in both the labelled and the unlabelled case.

The unlabelled case is done using the function

:<math>M(f(z), y) = \sum_{n\ge 0} y^n Z(S_nE_n)(f(z), f(z^2), \ldots, f(z^n))</math>

so that

Line 176 ⟶ 177:

:<math>\sum_{k=0}^n A_k B_{n-k}.</math>

Using the definition of the OGF and some [[elementary algebra]], we can show that

:<math>\mathcal{A} = \mathcal{B} \times \mathcal{C}</math> implies <math>A(z) = B(z) \cdot C(z).</math>

Line 231 ⟶ 232:

Other important elementary constructions are:

*the ''cycle construction'' (<math>\mathfrak{C}\{\mathcal{B}\}</math>), like sequences except that cyclic rotations are not considered distinct

*''pointing'' (<math>\Theta\mathcal{B}</math>), in which each member of <math>\mathcal{{mathcal|B}</math>} is augmented by a neutral (zero size) pointer to one of its atoms

*''substitution'' (<math>\mathcal{B} \circ \mathcal{C}</math>), in which each atom in a member of <math>\mathcal{{mathcal|B}</math>} is replaced by a member of <math>\mathcal{{mathcal|C}</math>}.

The derivations for these constructions are too complicated to show here. Here are the results:

{| class="wikitable"

{|

|-

! Construction

Line 286 ⟶ 287:

===Specification and specifiable classes===

The elementary constructions mentioned above allow us to define the notion of ''specification''. ThoseThis specification allowallows us to use a set of recursive equations, with multiple combinatorial classes.

Formally, a specification for a set of combinatorial classes <math>(\mathcal A_1,\dots,\mathcal A_r)</math> is a set of <math>r</math> equations <math>\mathcal A_i=\Phi_i(\mathcal A_1,\dots,\mathcal A_r)</math>, where <math>\Phi_i</math> is an expression, whose atoms are <math>\mathcal E,\mathcal Z</math> and the <math>\mathcal A_i</math>'s, and whose operators are the elementary constructions listed above.

Line 372 ⟶ 373:

==See also==

*[[Combinatorial species]]

* [[Analytic combinatorics]]

==References==