Content deleted Content added
JustAMuggle (talk | contribs) Copy edit. |
Link suggestions feature: 3 links added. |
||
| (33 intermediate revisions by 19 users not shown) | |||
Line 1:
{{Short description|Mathematical technique}}
{{About|the method in analytic combinatorics|the method in invariant theory|Symbolic method}}
In [[combinatorics]]
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]], [[Leonhard Euler|Euler]], [[Arthur Cayley]], [[Ernst Schröder (mathematician)|Schröder]],
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-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-82|ref=joy}}</ref>.▼
[[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 book|last1=Foata|first1=Dominique|authorlink1=Dominique Foata|last2=Schützenberger|first2=Marcel-P.|authorlink2=Marcel-Paul Schützenberger|title=Théorie Géométrique des Polynômes Eulériens|series=Lecture 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=
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 [[Asymptotic distribution|limit laws]], to [[random generation]], all of them being suitable to automatization via [[computer algebra]].
== Classes of combinatorial structures ==
Line 17 ⟶ 27:
:<math>\frac{g(z)^n}{|G|}.</math>
We are able to enumerate filled slot configurations using either
:<math> X^2/E_2 \; + \; X^3/E_3 </math>
Line 25 ⟶ 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{
:<math>\mathcal{C} = \sum_{n \ge 1} \sum_{G\in \operatorname{Cl}(S_n)} c_G (X^n/G)</math>
where <math>\mathfrak{
In the following we will simplify our notation a bit and write e.g.
Line 51 ⟶ 61:
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}}}} ===
Line 57 ⟶ 67:
This operator corresponds to the class
:<math>L = \frac{1}{1 - X} = 1 +
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(
1 + \sum_{n\ge 1} f(z)^n = \frac{1}{1-f(z)}</math>
and
:<math> G(z) = 1 + \sum_{n\ge 1}
\frac{1}{1-g(z)}.</math>
Line 73 ⟶ 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 116 ⟶ 126:
The series is
:<math>E = 1 +
i.e., the symmetric group <math>S_n = E_n</math> is applied to the
The unlabelled case is done using the function
:<math>M(f(z), y) = \sum_{n\ge 0} y^n Z(
so that
Line 167 ⟶ 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 222 ⟶ 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
*''substitution'' (<math>\mathcal{B} \circ \mathcal{C}</math>), in which each atom in a member of
The derivations for these constructions are too complicated to show here. Here are the results:
{| class="wikitable"
|-
! Construction
Line 277 ⟶ 287:
===Specification and specifiable classes===
The elementary constructions mentioned above allow us to define the notion of ''specification''.
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 283 ⟶ 293:
A class of combinatorial structures is said to be ''constructible'' or ''specifiable'' when it admits a specification.
For example, the set of trees whose leaves'
==Labelled structures==
Line 363 ⟶ 373:
==See also==
*[[Combinatorial species]]
* [[Analytic combinatorics]]
==References==
{{reflist}}
* François Bergeron, Gilbert Labelle, Pierre Leroux, ''Théorie des espèces et combinatoire des structures arborescentes'', LaCIM, Montréal (1994). English version: ''Combinatorial Species and Tree-like Structures'', Cambridge University Press (1998).
* Philippe Flajolet and Robert Sedgewick, ''[[Analytic Combinatorics]]'', Cambridge University Press (2009). (available online: http://algo.inria.fr/flajolet/Publications/book.pdf)
* Micha Hofri, ''Analysis of Algorithms: Computational Methods and Mathematical Tools'', Oxford University Press (1995).
| |||