Exam (elaborations)
Generating Functions
- Course
- Institution
Generating Functions
[Show more]
Seller
Follow
modockochieng06
Content preview
Mathematical DatabaseGENERATING FUNCTIONS
1. Introduction
The concept of generating functions is a powerful tool for solving counting problems.
Intuitively put, its general idea is as follows. In counting problems, we are often interested in
counting the number of objects of ‘size n’, which we denote by an . By varying n, we get different
values of an . In this way we get a sequence of real numbers
a0 , a1 , a2 , …
from which we can define a power series (which in some sense can be regarded as an ‘infinite-
degree polynomial’)
G ( x) = a0 + a1 x + a2 x 2 + .
The above G ( x) is the generating function for the sequence a0 , a1 , a2 , ….
In this set of notes we will look at some elementary applications of generating functions.
Before formally introducing the tool, let us look at the following example.
Example 1.1.
(IMO 2001 HK Preliminary Selection Contest) Find the coefficient of x17 in the expansion of
(1 + x 5 + x 7 ) 20 .
Solution.
The only way to form an x17 term is to gather two x5 and one x 7 . Since there are C220 = 190 ways
to choose two x 5 from the 20 multiplicands and 18 ways to choose one x 7 from the remaining 18
multiplicands, the answer is 190 × 18 = 3420 .
To gain a preliminary insight into how generating functions is related to counting, let us
describe the above problem in another way. Suppose there are 20 bags, each containing a $5 coin
and a $7 coin. If we can use at most one coin from each bag, in how many different ways can we
pay $17, assuming that all coins are distinguishable (i.e. the $5 coin from the first bag is considered
to be different from that in the second bag, and so on)? It should be quite clear that the answer is
again 3420 — to pay $17, one must use two $5 coins and one $7 coin. There are C220 = 190 ways to
choose two $5 coins from the 20 bags, and 18 ways to choose a $7 coin from the remaining 18 bags.
Using the notations we introduced at the very beginning, we could say that a17 = 3420 .
Page 1 of 17
, Mathematical Database
2. Techniques of Computation
Let us once again give the definition of a generating function before we proceed.
Definition. Given a sequence a0 , a1 , a2 , …, we define the generating function of the
sequence {an } to be the power series
G ( x) = a0 + a1 x + a2 x 2 + .
Let us look at a few examples.
Example 2.1.
Find the generating functions for the following sequences. In each case, try to simplify the answer.
(a) 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, …
(b) 1, 1, 1, 1, 1, …
(c) 1, 3, 3, 1, 0, 0, 0, 0, …
(d) C02005 , C12005 , C22005 , …, C2005
2005
, 0, 0, 0, 0, …
Solution.
(a) The generating function is
G ( x) = 1 + 1x + 1x 2 + 1x 3 + 1x 4 + 1x 5 + 0 x 6 + 0 x 7 +
= 1 + x + x 2 + x3 + x 4 + x5
1 − x6
We can apply the formula for the sum of a geometric series to rewrite G ( x) as G ( x) = .
1− x
(b) The generating function is
G ( x) = 1 + x + x 2 + x3 + x 4 + .
When | x | < 1 , we can apply the formula for the sum to infinity of a geometric series to rewrite
1
G ( x) as G ( x) = . In working with generating functions, we shall ignore the question of
1− x
1
convergence and simply say G ( x) = .
1− x
(c) The generating function is G ( x) = 1 + 3x + 3x 2 + 1 , and of course, the binomial theorem enables
us to simplify the answer as G ( x) = (1 + x)3 .
Page 2 of 17
, Mathematical Database
(d) The generating function is
G ( x) = C02005 + C12005 x + C22005 x 2 + + C2004 x + C2005
2005 2004 2005 2005
x ,
and the binomial theorem once again enables us to simplify the answer as G ( x) = (1 + x) 2005 .
When dealing with computations of generating functions, we are particularly interested with
two things, namely, whether the generating function can be written in closed form and whether we
can find the coefficient of a certain power of x easily.
To write a generating function in ‘closed form’ means, in general, writing it in a ‘direct’ form
without summation sign nor ‘ ’. For instance, in Example 2.1 (b), G ( x) = 1 + x + x 2 + x3 + x 4 +
1
is not in closed form while G ( x) = is. The reason for trying to put a generating function in
1− x
closed form is as follows. In the more advanced theory of generating functions (beyond the level of
this set of notes), we will find that certain combinations of problems correspond to certain
operations (e.g. addition, multiplication or more complicated operations) on generating functions. If
we can find a generating function in closed form, the computations can be greatly simplified and
easily carried out.
On the other hand, we are interested in knowing the coefficient of a certain power of x because,
as we have remarked at the very beginning, it often refers to the number of objects of size n, which
is usually the thing we wish to find in counting problems.
Clearly, if a generating function is given in ‘explicit form’, such as
∞
n −1 n
G ( x) = x + 2 x 2 + 3 x3 + 4 x 4 + or G ( x) = ∑ x ,
n = 0 2n + 1
then finding a specific coefficient will be easy. However, if a generating function is given in closed
form, ingenious tricks are sometimes required in determining certain coefficients. The following
example illustrates some common tricks.
Example 2.2.
In each of the following, find the coefficient of x 2005 in the generating function G ( x) .
(a) G ( x) = (1 − 2 x)5000
1
(b) G ( x) =
1 + 3x
1
(c) G ( x) =
(1 + 5 x) 2
Solution.
Page 3 of 17
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller modockochieng06. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $7.99. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
79978 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now