Generating functions This is the same generating function that we obtained by using the Binomial Theorem But this time around we translated directly from the counting problem to the generating function We can extend these ideas to a general principle Rule 5( Convolution Rule). Let A(r) be the generating function for selecting items from set A and let b(a) be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union A U B is the product A(). B(a) This rule is rather ambiguous: what exactly are the rules governing the selection of items from a set? Remarkably, the Convolution Rule remains valid under many inter pretations of selection. For example, we could insist that distinct items be selected or we might allow the same item to be picked a limited number of times or any number of times. Informally, the only restrictions are that (1) the order in which items are selected is disregarded and(2)restrictions on the selection of items from sets A and B also apply in selecting items from AU B.(Formally, there must be a bijection between n-element selections from AUB and ordered pairs of selections from A and B containing a total of n elements. Proof. Define B()=∑hnx,C()=A(x)·B(x)=∑cnx Let's first evaluate the product A(a). B(ar)and express the coefficient cn in terms of the a and b coefficients. We can tabulate all of the terms in this product in a table a1.l a1bzl a1b1.2 a1b2. a300.0 Notice that all terms involving the same power of r lie on a/-sloped diagonal. Collecting these terms together, we find that the coefficient of z" in the product is Cn= abn +a1bn-1+a2bn-2+..+anbo� � � 10 Generating Functions This is the same generating function that we obtained by using the Binomial Theorem. But this time around we translated directly from the counting problem to the generating function. We can extend these ideas to a general principle: Rule 5 (Convolution Rule). Let A(x) be the generating function for selecting items from set A, and let B(x) be the generating function for selecting items from set B. If A and B are disjoint, then the generating function for selecting items from the union A ∪ B is the product A(x) · B(x). This rule is rather ambiguous: what exactly are the rules governing the selection of items from a set? Remarkably, the Convolution Rule remains valid under many inter￾pretations of selection. For example, we could insist that distinct items be selected or we might allow the same item to be picked a limited number of times or any number of times. Informally, the only restrictions are that (1) the order in which items are selected is disregarded and (2) restrictions on the selection of items from sets A and B also apply in selecting items from A ∪ B. (Formally, there must be a bijection between n­element selections from A ∪ B and ordered pairs of selections from A and B containing a total of n elements.) Proof. Define: ∞ ∞ ∞ A(x) = anx n , B(x) = bnx n , C(x) = A( B(x) = cnx n x) · . n=0 n=0 n=0 Let’s first evaluate the product A(x) B(x) and express the coefficient cn · in terms of the a and b coefficients. We can tabulate all of the terms in this product in a table: b0x0 b1x1 b2x2 b3x3 . . . a0x0 a0b0x0 a0b1x1 a0b2x2 a0b3x3 . . . a1x1 a1b0x1 a1b1x2 a1b2x3 . . . a2x2 a2b0x2 a2b1x3 . . . a3x3 a3b0x3 . . . . . . . . . Notice that all terms involving the same power of x lie on a /­sloped diagonal. Collecting these terms together, we find that the coefficient of xn in the product is: cn = a0bn + a1bn−1 + a2bn−2 + · · · + anb0