Content deleted Content added
Cleaned up a lot of misconceptions: (1) SEQ is constructed from X^n/1, not X^n/E_n. E_n is the symmetric group, not the trivial group. (2) Molecules, not atoms. Molecules are products of atoms. |
Link suggestions feature: 3 links added. |
||
| (One intermediate revision by one other user 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]],
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{M}]</math> of combinatorial structures is a formal series
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>
| |||