above the Cartesian product (pair) of the two families () has generating function F(x)G(x). Sequences A (finite) sequence generalizes the idea of the pair as defined above. Sequences are arbitrary Cartesian products of a combinatorial object with itself. Formally: To put the above in words: An empty sequence or a sequence of one element or a sequence of two elements or a sequence of three elements, etc. The generating function would be: Combinatorial structures The above operations can now be used to enumerate common combinatorial objects including trees (binary and plane), Dyck paths and cycles. A combinatorial structure is composed of atoms. For example, with trees the atoms would be the nodes. The atoms which compose the object can either be labeled or unlabeled. Unlabeled atoms are indistinguishable from each other, while labelled atoms are distinct. Therefore, for a combinatorial object consisting of labeled atoms a new object can be formed by simply swapping two or more atoms. Binary and plane trees Binary and plane trees are examples of an unlabeled combinatorial structure. Trees consist of nodes linked by edges in such a way that there are no cycles. There is generally a node called the root, which has no parent node. In plane trees each node can have an arbitrary number of children. In binary trees, a special case of plane trees, each node can have either two or no children. Let denote the family of all plane trees. Then this family can be recursively defined as follows: In this case represents the family of objects consisting of one node. This has generating function x. Let P(x) denote the generating function . Putting the above description in words: A plane tree consists of a node to which is attached an arbitrary number of subtrees, each of which is also a plane tree. Using the operation on families of combinatorial structures developed earlier, this translates to a recursive generating function: After solving for P(x): An explicit formula for the number of plane trees of size n can now be determined by extracting the coefficient of xn: Note: The notation [xn] f(x) refers to the coefficient of xn in f(x). The series expansion of the square root is based on Newton's generalization of the binomial theorem. To get from the fourth to fifth line manipulations using the generalized binomial coefficient is needed. The expression on the last line is equal to