Content deleted Content added
CyborgTosser (talk | contribs) in progress |
CyborgTosser (talk | contribs) combinatorial sum |
||
Line 9:
It is trivial to show that the generating functions (either ordinary or exponential) for <math>\mathcal{E}</math> and <math>\mathcal{Z}</math> are <math>E(z) = 1</math> and <math>Z(z) = z</math>, respectively. The disjoint union is also simple — for disjoint sets <math>\mathcal{B}</math> and <math>\mathcal{C}</math>, <math>\mathcal{A} = \mathcal{B} \cup \mathcal{C}</math> implies <math>A(z) = B(z) + C(z)</math>. The relations corresponding to other operations depend on whether we are talking about labelled or unlabelled structures (and ordinary or exponential generating functions).
==Combinatorial sum==
The restriction of [[Union (sets)|unions]] to disjoint unions is an important one; however, in the formal specification of symbolic combinatorics, it is too much trouble to keep track of which sets are disjoint. Instead, we make use of a construction that guarantees there is no intersection (''be careful, however; this affects the semantics of the operation as well''). In defining the ''combinatorial sum'' of two sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math>, we mark members of each set with a distinct marker, for example <math>\circ</math> for members of <math>\mathcal{A}</math> and <math>\bullet</math> for members of <math>\mathcal{B}</math>. The combinatorial sum is then:
:<math>\mathcal{A} + \mathcal{B} = (\mathcal{A} \times \{\circ\}) \cup (\mathcal{B} \times \{\bullet\})</math>
This is the operation that formally corresponds to addition.
[[Category:combinatorics]]
| |||