Content deleted Content added
m →Labelled structures: punctuation |
m →Product: punctuation |
||
Line 130:
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') \mbox{ is well-labelled, } \rho(\alpha') = \alpha, \rho(\beta') = \beta \}.</math>
Finally, the labelled product of two classes <math>\mathcal{A}</math> and <math>\mathcal{B}</math> is
:<math>\mathcal{A} \star \mathcal{B} = \bigcup_{\alpha \in \mathcal{A}, \beta \in \mathcal{B}} (\alpha \star \beta).</math>
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}^{n}{n \choose k}A_{k}B_{n-k}.</math>
This ''binomial convolution'' relation for the terms is equivalent to multiplying the EGFs,
:<math>A(z) \cdot B(z).\,</math>
===Sequence===
| |||