Illinois State University Mathematics Department

Earlier in the course we solved the following problem:

Seth has a collection of 10 baseball cards. How many different ways could Seth select 6 cards from that set?

We solved the problem by treating this as a particular case of the general combinations problem:

How many k-element subsets are there in an n-element set?

We calculated , or, in general, .

We later related such combinations to the coefficients in the binomial expansion, where K = C(n,k) was the coefficient of the term in the expansion of . We note here that if y = 1, then C(n,k) is the coefficient of the term with variable in the expansion of .

Because of the capacity for such expressions to generate solutions to questions involving combinatorics, they have come to be called generating functions. Our focus here is on understanding what a generating function is, how to write a generating function, and how to use it to solve a combinatorics problem. Because we will not delve into great depth or detail about generating functions, you are encouraged to read one of the many resources that more fully describes and illustrates generating functions. Discrete mathematics textbooks provide a good starting point.

Let's begin by exploring how the expression is a generating function for the problem involving Seth's cards.

First we note that applications of generating functions take advantage of an important and well-known property of exponents: When multiplying variable expressions, exponents of like variables are added. For instance, . We will use this extensively for counting purposes with generating functions.

Now, think of each of the ten factors in associated with each of Seth's 10 cards. Specifically, think of the expression (1+ x) equivalent to

As we expand and choose the term "1" we are also saying EXCLUDE THIS CARD. When we choose the term "x" from a factor, as we expand, we are saying, INCLUDE THIS CARD.

Thus, in the expansion, , the term indicates that there are 210 different ways to select 6 of the phrases INCLUDE THIS CARD.

Another problem we've already solved is the following:

On a local election ballot, 6 funding issues were to be voted on. On each of the 6 issues, a voter could support the proposal by voting YES, diapprove of the proposal by voting NO, or simply ABSTAIN from expressing a position by not voting. How many different ways exist for a voter to mark YES 4 times?

The expression Y + N + A represents the three choices on each issue, and represents that the choice is to be made 6 times. Then is a generating function for this situation, and we seek the sum of all possible values c, where c is a coefficient of the expanded term , where a + b = 2. From our work with multinomial coefficients, we know that , with a + b = 2. You should be able to show that the sum of all possible values c is 60.

Neither of these two problem situations is new to us, and you may be thinking that generating functions are not necessary and in fact add another layer of complexity to the solution strategy. In these two cases that may be so. Here's another example to help illustrate the use, and perhaps, the efficiency, of generating functions.

Determine the number of ways to select a 4-letter combination from the set {A,B,C} if A can be included at most once, B at most twice, and C at most three times.

For most of us, this problem requires enumeration through some organized listing of all cases. We might proceed as follows:

Because the set must contain 4 letters, there must be at least one C.

If there is only one C, there must be two Bs. Let us begin with that:

{C,B,B,A}

What if there are two Cs?

{C,C,B,B} or {C,C,B,A}

What if there are three Cs?

{C,C,C,B} or {C,C,C,A}

This concludes the enumeration of the 5 possible cases.

How could we have modeled this situation with a generating function?

We could express each letter's possibilities with a polynomial. For instance:

represents A occurring 0 times or 1 time.

represents B occurring 0, 1, or 2 times.

represents C occurring 0, 1, 2, or 3 times.

Then the expansion of will list for us all the ways we can create k-element sets with A, B, or C within the restrictions of the problem situation. For instance, one term in the expansion is . This represents a 5-element set with one A, two Bs, and two Cs.

Because the problem does not require us to list all the possibilities, the following generating function is more efficient to use in determining the answer:

When we expand this to get

,

we need to identify the coefficient of the term with , for this represents the number of ways to create 4-element sets under the restrictions of the problem.

Here's another problem you explored at the very beginning of the course.

With an adequate supply of pennies, nickels, dimes, and quarters, how many ways exist to give someone 47 cents in change?

We note that the change can include up to four different coins but does not require every coin be represented.

The generating function below will provide a solution. It is the product of four polynomials.

After expansion, we need to identify the coefficient of the term with . You should convince yourself that the desired coefficient is 39. This represents the number of ways to use pennies, nickels, dimes, or quarters to create 47 cents in change.

One more illustration, this time extending our function beyond finite limits.

At a small ski chalet, sandwiches sell for $2 and soup is $3 a bowl. For r dollars, how many different ways can soup and sandwich be ordered?

To help clarify the problem, we note that there are two orders that can be placed for $8: (i) one sandwich and two soups or (ii) four sandwiches and no soup.

A generating function that provides a solution is

whose expansion is

How many orders cost $14? Exactly 3 orders do.