Content deleted Content added
m leaves's->leaves' - Fix a typo in one click |
Link suggestions feature: 3 links added. |
||
| (30 intermediate revisions by 17 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 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 363 ⟶ 373:
==See also==
*[[Combinatorial species]]
* [[Analytic combinatorics]]
==References==
| |||