Content deleted Content added
m →Sequence: punctuation |
m →Unlabelled structures: punctuation |
||
Line 19:
==Unlabelled structures==
With unlabelled structures, an [[ordinary generating function]] (OGF) is used. The OGF of a sequence <math>A_{n}</math> is defined as
:<math>A(x)=\sum_{n=0}^{\infty}A_{n}x^{n}.</math>
===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}^{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>
===Sequence===
| |||