Generating Functions 4.1 Choosing distinct Items from a Set The generating function for binomial coefficients follows directly from the Binomial The- ,0,0,0, r+ 0 t ar Thus, the coefficient of z" in(1 +r)is the number of ways to choose n distinct items om a k-element set. For example, the coefficient of 2 is ) the number of ways to choose 2 items from a k-element set. Similarly, the coefficient of t is the number of ways to choose k+ l items from a k-element set, which is zero 4.2 Building Generating Functions that Count Often we can translate the description of a counting problem directly into a generating function for the solution. For example, we could figure out that(1+a) generates the number of ways to select n distinct items from a k-element subset without resorting to the binomial Theorem or even fussing with binomial coefficients! Here is how. First, consider a single-element set a1. The generating function for the number of ways to choose n elements from this set is simply 1 +r: we have 1 way to choose zero elements, 1 way to choose one element, and o ways to choose more than one element. Similarly, the number of ways to choose n elements from the set a2 is also given by the generating function 1+a. The fact that the elements differ in the two cases is irrelevant Now here is the the main trick: the generating function for choosing elements from a union of disjoint sets is the product of the generating functions for choosing from each set. We'll justify this in a moment, but let's first look at an example. According to this principle, the generating function for the number of ways to choose n elements from the (a1, a2) (1 +ar (1+x)=(1+ 1+2 OGF for OGF for a2 Sure enough, for the set (a1, a2), we have 1 way to choose zero elements, 2 ways to choose one element, 1 way to choose two elements and o ways to choose more than two ele- Repeated application of this rule gives the generating function for choosing n items from a k-element set a1, a2, .. ak H (1+x)·(1+x)…(1+x) OGF for OGF for OGF for OGF fo {a}{a2}� � Generating Functions 9 4.1 Choosing Distinct Items from a Set The generating function for binomial coefficients follows directly from the Binomial The￾orem: �� � � � � � � � � � � � � � � � � k k k k k k k 2 k k , , , . . . , , 0, 0, 0, . . . + x + x + x 0 1 2 k ←→ 0 1 2 + · · · k = (1 + x) k Thus, the coefficient of xn in (1 + x)k is the number of ways to choose n distinct items k from a k­element set. For example, the coefficient of x2 is , the number of ways to 2 choose 2 items from a k­element set. Similarly, the coefficient of xk+1 is the number of ways to choose k + 1 items from a k­element set, which is zero. 4.2 Building Generating Functions that Count Often we can translate the description of a counting problem directly into a generating function for the solution. For example, we could figure out that (1 + x)k generates the number of ways to select n distinct items from a k­element subset without resorting to the Binomial Theorem or even fussing with binomial coefficients! Here is how. First, consider a single­element set {a1}. The generating function for the number of ways to choose n elements from this set is simply 1 + x: we have 1 way to choose zero elements, 1 way to choose one element, and 0 ways to choose more than one element. Similarly, the number of ways to choose n elements from the set {a2} is also given by the generating function 1 + x. The fact that the elements differ in the two cases is irrelevant. Now here is the the main trick: the generating function for choosing elements from a union of disjoint sets is the product of the generating functions for choosing from each set. We’ll justify this in a moment, but let’s first look at an example. According to this principle, the generating function for the number of ways to choose n elements from the {a1, a2} is: (1 + x) (1 + x) = (1 + x) 2 = 1 + 2x + x 2 � �� � · � �� � � �� � OGF for OGF for OGF for {a1} {a2} {a1, a2} Sure enough, for the set {a1, a2}, we have 1 way to choose zero elements, 2 ways to choose one element, 1 way to choose two elements, and 0 ways to choose more than two ele￾ments. Repeated application of this rule gives the generating function for choosing n items from a k­element set {a1, a2, . . . , ak}: (1 + x) (1 + x) (1 + x) = (1 + x) k � �� � · � �� � · · · � �� � � �� � OGF for OGF for OGF for OGF for {a1} {a2} {ak} {a1, a2, . . . , ak}