Content deleted Content added
m →Labelled structures: Graph (mathematics) is now a disambiguation link; please fix., replaced: labelled graph{{dn|date=January 2016}} → labelled graph using AWB |
Link suggestions feature: 3 links added. |
||
| (60 intermediate revisions by 29 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]], [[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 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=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=}}</ref>
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 8 ⟶ 21:
The [[Pólya enumeration theorem]] solves this problem in the unlabelled case. Let ''f''(''z'') be the [[ordinary generating function]] (OGF) of the objects, then the OGF of the configurations is given by the substituted [[cycle index]]
:<math>Z(G)(f(z), f(z^2), \ldots, f(z^n)).
In the labelled case we use an [[exponential generating function]] (EGF) ''g''(''z'') of the objects and apply the [[Labelled enumeration theorem]], which says that the EGF of the configurations is given by
Line 14 ⟶ 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>
where the term <math>X^n/G</math> is used to denote the set of orbits under ''G'' and <math>X^n = X \times \
:<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.
:<math> E_2 + E_3 \
for the classes mentioned above.
Line 48 ⟶ 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
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>
=== The cycle operator
This operator corresponds to the class
:<math>C = C_1 + C_2 + C_3 + \cdots
i.e., cycles containing at least one object. We have
Line 76 ⟶ 89:
:<math>
F(z) = \sum_{n\ge 1} Z(C_n)(f(z), f(z^2), \ldots, f(z^n)) =
\sum_{n\ge 1} \frac{1}{n} \sum_{d
or
Line 89 ⟶ 102:
\log \frac{1}{1-g(z)}.</math>
This operator, together with the set operator
The labelled even cycle operator
:<math>C_2 + C_4 + C_6 + \cdots
which yields
Line 100 ⟶ 113:
\frac{1}{2} \log \frac{1}{1-g(z)^2}.</math>
This implies that the labelled odd cycle operator
:<math>C_1 + C_3 + C_5 + \cdots</math>
Line 109 ⟶ 122:
\frac{1}{2} \log \frac{1+g(z)}{1-g(z)}.</math>
=== The multiset/set operator
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
:<math>\mathfrak{M}(f(z)) = M(f(z), 1).
Evaluating <math>M(f(z), 1)</math> we obtain
:<math> F(z) = \exp \left( \sum_{
For the labelled case we have
Line 134 ⟶ 147:
\sum_{n\ge 0} \frac{g(z)^n}{n!} = \exp g(z).</math>
In the labelled case we denote the operator by
:<math> F(z) = \exp \left( \sum_{\ell\ge 1} (-1)^{\ell-1} \frac{f(z^\ell)} \ell \right).</math>
==Procedure==
Line 153 ⟶ 168:
==Unlabelled structures==
With unlabelled structures, an [[ordinary generating function]] (OGF) is used. The OGF of a sequence <math>
:<math>A(x)=\sum_{n=0}^
===Product===
The [[Cartesian product|product]] of two combinatorial classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is specified by defining the size of an ordered pair as the sum of the sizes of the elements in the pair. Thus we have for <math>a \in \mathcal{A}</math> and <math>b \in \mathcal{B}</math>, <math>|(a,b)| = |a| + |b|</math>. This should be a fairly intuitive definition. We now note that the number of elements in <math>\mathcal{A} \times \mathcal{B}</math> of size <var>n</var> is
:<math>\sum_{k=0}^
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 183 ⟶ 198:
:<math>\begin{align}A(z) &{} = \prod_{\beta \in \mathcal{B}}(1 + z^{|\beta|}) \\
&{} = \prod_{n=1}^
&{} = \exp \left ( \ln \prod_{n=1}^{\infty}(1 + z^
&{} = \exp \left ( \sum_{n = 1}^
&{} = \exp \left ( \sum_{n = 1}^
&{} = \exp \left ( \sum_{k = 1}^
&{} = \exp \left ( \sum_{k = 1}^
\end{align}</math>
where the expansion
:<math>\ln(1 + u) = \sum_{k = 1}^
was used to go from line 4 to line 5.
Line 205 ⟶ 220:
:<math>\begin{align} A(z) &{} = \prod_{\beta \in \mathcal{B}} (1 - z^{|\beta|})^{-1} \\
&{} = \prod_{n = 1}^
&{} = \exp \left ( \ln \prod_{n = 1}^
&{} = \exp \left ( \sum_{n=1}^
&{} = \exp \left ( \sum_{k=1}^
\end{align}
</math>
where, similar to the above set construction, we expand <math>\ln (1 - z^
===Other elementary constructions===
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 227 ⟶ 242:
|-
|<math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>
|<math>A(z) = \sum_{k=1}^
|-
|<math>\mathcal{A} = \Theta\mathcal{B}</math>
Line 233 ⟶ 248:
|-
|<math>\mathcal{A} = \mathcal{B} \circ \mathcal{C}</math>
|<math>A(z) = B(C(z))
|}
Line 239 ⟶ 254:
Many combinatorial classes can be built using these elementary constructions. For example, the class of plane [[tree (graph)|tree]]s (that is, trees [[embedding|embedded]] in the plane, so that the order of the subtrees matters) is specified by the [[recursion|recursive]] relation
:<math>\mathcal{G} = \mathcal{Z} \times \
In other words, a tree is a root node of size 1 and a sequence of subtrees. This gives
Line 245 ⟶ 260:
:<math>G(z) = \frac{z}{1 - G(z)}</math>
we solve for ''G''(''z'') by multiplying <math>1 - G(z)</math> to get
<math>G(z) - G(z)^2 = z</math>
Line 255 ⟶ 270:
Another example (and a classic combinatorics problem) is [[integer partition]]s. First, define the class of positive integers <math>\mathcal{I}</math>, where the size of each integer is its value:
:<math>\mathcal{I} = \mathcal{Z} \times \
The OGF of <math>\mathcal{I}</math> is then
Line 263 ⟶ 278:
Now, define the set of partitions <math>\mathcal{P}</math> as
:<math>\mathcal{P} = \
The OGF of <math>\mathcal{P}</math> is
Line 269 ⟶ 284:
:<math>P(z) = \exp \left ( I(z) + \frac{1}{2} I(z^{2}) + \frac{1}{3} I(z^{3}) + \cdots \right ). </math>
Unfortunately, there is no closed form for <math>P(z)</math>; however, the OGF can be used to derive a [[recurrence relation]], or
===Specification and specifiable classes===
The elementary constructions mentioned above allow us to define the notion of ''specification''. This specification allows 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.
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' depth is even (respectively, odd) can be defined using the specification with two classes <math>\mathcal A_\text{even}</math> and <math>\mathcal A_\text{odd}</math>. Those classes should satisfy the equation <math>\mathcal A_\text{odd}=\mathcal Z\times \operatorname{Seq}_{\ge1}\mathcal A_\text{even}</math> and <math>\mathcal A_\text{even} = \mathcal Z\times \operatorname{Seq}\mathcal A_\text{odd}</math>.
==Labelled structures==
An object is ''weakly labelled'' if each of its atoms has a nonnegative integer label, and each of these labels is distinct. An object is (''strongly'' or ''well'') ''labelled'', if furthermore, these labels comprise the consecutive integers <math>[1 \ldots n]</math>. ''Note: some combinatorial classes are best specified as labelled structures or unlabelled structures, but some readily admit both specifications.'' A good example of labelled structures is the class of [[Graph (discrete mathematics)|labelled graph]]s.
With labelled structures, an [[exponential generating function]] (EGF) is used. The EGF of a sequence <math>
:<math>A(x)=\sum_{n=0}^
===Product===
Line 285 ⟶ 309:
To aid this development, let us define a function, <math>\rho</math>, that takes as its argument a (possibly weakly) labelled object <math>\alpha</math> and relabels its atoms in an order-consistent way so that <math>\rho(\alpha)</math> is well labelled. We then define the labelled product for two objects <math>\alpha</math> and <math>\beta</math> as
:<math>\alpha \star \beta = \{(\alpha',\beta'): (\alpha',\beta') \
Finally, the labelled product of two classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is
Line 293 ⟶ 317:
The EGF can be derived by noting that for objects of size <math>k</math> and <math>n-k</math>, there are <math>{n \choose k}</math> ways to do the relabelling. Therefore, the total number of objects of size <math>n</math> is
:<math>\sum_{k=0}^
This ''binomial convolution'' relation for the terms is equivalent to multiplying the EGFs,
:<math>A(z) \cdot B(z).
===Sequence===
Line 307 ⟶ 331:
===Set===
In labelled structures, a set of <math>k</math> elements corresponds to exactly <math>k!</math> sequences. This is different from the unlabelled case, where some of the permutations may coincide. Thus for <math>\mathcal{A} = \mathfrak{P}\{\mathcal{B}\}</math>, we have
:<math>A(z) = \sum_{k = 0}^
===Cycle===
Cycles are also easier than in the unlabelled case. A cycle of length <math>k</math> corresponds to <math>k</math> distinct sequences. Thus for <math>\mathcal{A} = \mathfrak{C}\{\mathcal{B}\}</math>, we have
:<math>A(z) = \sum_{k = 0}^
===Boxed product===
In labelled structures, the min-boxed product <math>\mathcal{A}_{\min} = \mathcal{B}^{\square}\star \mathcal{C}</math> is a variation of the original product which requires the element of <math>\mathcal{B}</math> in the product with the minimal label. Similarly, we can also define a max-boxed product, denoted by <math>\mathcal{A}_{\max} = \mathcal{B}^
:<math>A_{\min}(z)=A_{\max}(z)=\int^
or equivalently,
:<math>A_{\min}'(t)=A_{\max}'(t)=B'(t)C(t).</math>
===Example===
An increasing Cayley tree is a labelled non-plane and rooted tree whose labels along any branch stemming from the root form an increasing sequence. Then, let <math>\mathcal{L}</math> be the class of such trees. The recursive specification is now <math>\mathcal{L}=\mathcal{Z}^\square\star \operatorname{SET}(\mathcal{L}).</math>
===Other elementary constructions===
The operators
CYC{{sub|even}},
▲:<math>
CYC{{sub|odd}},
SET{{sub|even}},}}
and
SET{{sub|odd}}
}}
▲</math>
represent cycles of even and odd length, and sets of even and odd cardinality.
Line 340 ⟶ 363:
[[Stirling numbers of the second kind]] may be derived and analyzed using the structural decomposition
:<math> \
The decomposition
:<math> \
is used to study unsigned [[Stirling numbers of the first kind]], and in the derivation of the [[Random permutation statistics|statistics of random permutations]]. A detailed examination of the [[exponential generating function]]s associated to Stirling numbers within symbolic combinatorics may be found on the page on [[Stirling numbers and exponential generating functions in symbolic combinatorics]].
==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).
| |||