Symbolic method (combinatorics): Difference between revisions

Content deleted Content added
m typo, adding a link to combinatoric
Adding definition and example for specification, specifiable classes
Line 276:
 
Unfortunately, there is no closed form for <math>P(z)</math>; however, the OGF can be used to derive a [[recurrence relation]], or, using more advanced methods of analytic combinatorics, calculate the [[Generating function#Asymptotic growth of a sequence|asymptotic behavior]] of the counting sequence.
 
===Specification and specifiable classes===
The elementary constructions mentionned above allow to define the notion of ''specification''. Those specification allow 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 ''costructible'' or ''specifiable'' when it admits a specification.
 
For example, the set of trees whose leaves's depth is even (respectively, odd) can be defined using the specification with two classes <math>\mathcal A_{even}</math> and <math>\mathcal A_{odd}</math>. Those clasess should satisfy the equation <math>\mathcal A_{odd}=\mathcal Z\times \mathrm{Seq}_{\ge1}\mathcal A_{even}</math> and <math>\mathcal A_{even}=\mathcal Z\times \mathrm{Seq}\mathcal A_{odd}</math>.
 
==Labelled structures==