Thus we have for and , . This should be a fairly intuitive definition. We now note that the number of elements in of size n is Using the definition of the OGF and some elementary algebra, we can show that implies Sequence The sequence construction, denoted by is defined as In other words, a sequence is the neutral element, or an element of , or an ordered pair, ordered triple, etc. This leads to the relation Set The set (or powerset) construction, denoted by is defined as which leads to the relation where the expansion was used to go from line 4 to line 5. Multiset The multiset construction, denoted is a generalization of the set construction. In the set construction, each element can occur zero or one times. In a multiset, each element can appear an arbitrary number of times. Therefore, This leads to the relation where, similar to the above set construction, we expand , swap the sums, and substitute for the OGF of . Other elementary constructions Other important elementary constructions are: the cycle construction (), like sequences except that cyclic rotations are not considered distinct pointing (), in which each member of is augmented by a neutral (zero size) pointer to one of its atoms substitution (), in which each atom in a member of is replaced by a member of . The derivations for these constructions are too complicated to show here. Here are the results: Examples Many combinatorial classes can be built using these elementary constructions. For example, the class of plane trees (that is, trees embedded in the plane, so that the order of the subtrees matters) is specified by the recursive relation In other words, a tree is a root node of size 1 and a sequence of subtrees. This gives we solve for G(z) by multiplying to get subtracting z and solving for G(z) using the quadratic formula gives Another example (and a classic combinatorics problem) is integer partitions. First, define the class of positive integers , where the size of each integer is its value: The OGF of is then Now, define the set of partitions as The OGF of is Unfortunately, there is no closed form for ; however, the OGF can be used to derive a recurrence relation, or using more advanced methods of analytic combinatorics, calculate the asymptotic behavior of the counting sequence. Specification and specifiable