Discrete Mathematics (H) Lecture 15 Notes

Generating Functions

We may use generating functions to characterize sequences.

Definition: Generating Function

The generating function for the sequence of real numbers is the infinite series

A finite sequence can be easily extended by setting . Then the generating function for this extended sequence is a polynomial of degree , i.e.,

Example

1. , for
2. , for
3. , for
4. (for a fixed ),

Solution 1. So

Solution 3. So

Operations of Generating Functions

Theorem

Let , and , then

This theorem can be used to find sequences for complex generating functions from its components. For example, consider the generating function and We have

Counting with Generating Functions

Convolution Rule

Let be the generating function for selecting items from a set , and let be the generating function for selecting items from a set disjoint from . The the generating function for selecting items from the union is the product .

Maclaurin’s Theorem

Extended Binomial Theorem

Example

Find the number of ways to select balls with colors.

Solutions. For each color, the generating function representing the number of balls chosen is So the generating functions for colors is We need to find the underlying sequence of , this is equivalent to finding the coefficient of in . We can either apply the extended binomial theorem (which can expand binomials with negative exponents) or the Maclaurin’s Theorem:

Extended Binomial Theorem: Maclaurin’s Theorem:
Compute the derivatives of :

Evaluating at :

Thus, the coefficient of is

Problem

Find the number of solutions of where are nonnegative integers with , , .

Solution. This is equivalent of finding the coefficient of in the expansion of Factor out powers of : We need the coefficient of in , which is the coefficient of in . Express as: Expand: The coefficient of in the product is:

• From
• From
• From
• From : no contribution.

Summing these gives . Thus, the number of solutions is .

Problem

In how many ways can 8 identical cookies be distributed among 3 distinct children if each child receives at least two cookies and no more than 4 cookies?

Solution. This is equivalent of finding the number of solutions of the equation where are nonnegative integers and . This can be further reduce to finding the coefficient of in the expansion of Factor out : Expand: So the number of solution is .

Useful Generating Functions

-Combinations From a Set

Definition: -Combination

A -combination with repetition allowed, or a multiset of size , chosen from a set of elements, is an unordered selection of elements with repetition allowed.

Example

Find the number of nonnegative solutions to

Solution. This is equivalent to finding the number of multisets of size from the set . The generating function for this count is Using the extended binomial theorem, we have The coefficient of is , thus the count is .

Problem

Use generating functions to find the number of -combinations of a set with elements, .

Solution. Each of the elements in the set contributes the term to the generating function Hence, . Then by the binomial theorem, we have .