Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K-8 Teachers |
Generating Functions |
|||
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.
|
|
|
|
|
|