The Addition and Multiplication Principles of Generating Functions



If a_n is the number of widgets of size n and
A(q) = a_0 + a_1 q + a_2 q^2 + a_3 q^3 + ...
then we call A(q) a generating function for widgets (of size n).
Similarly if b_n = the number of doodles of size n and B(q) = b_0 + b_1 q + b_2 q^2 + ... is a generating function for doodles (of size n), then we have the following results:

The Additional Principle of generating functions:
A(q) + B(q) is the a generating function for the disjoint union of widgets and doodles (of size n).


The Mulitiplication Principle of generating functions:
A(q) B(q) is a generating function for pairs whose first element is a widget and second element is a doodle and the size of a pair is the sum of the size of the widget plus the size of the doodle.




This can be taken further. We can also look at other expressions of generating functions and say what they are in general:

A(q)/(1-q) is a generating function for the widgets of size less than or equal to n.

1/(1-qA(q)) is a generating function for 'sequences of widgets' (or k-tuples of widgets) where the size of a sequence of a widget is the number of widgets in the sequence (or k) plus the sum of the sizes of each of the widgets in the sequence.