High School Mathematics Extensions/Counting and Generating Functions
< High School Mathematics ExtensionsBefore we begin: This chapter assumes knowledge of
 Ordered selection (permutation) and unordered selection (combination) covered in Basic counting,
 Method of Partial Fractions and,
 Competence in manipulating Summation Signs
Some Counting Problems
..more to come
Generating functions
..some motivation to be written
To understand this section you need to see why this is true:
For a more detailed discussion of the above, head to Infinity and infinite processes.
Generating functions, otherwise known as Formal Power Series, are useful for solving problems like:
where
 ; n = 1, 2, 3
how many unique solutions are there if ?
Before we tackle that problem, let's consider the infinite polynomial:
We want to obtain a closed form of this infinite polynomial. The closed form is simply a way of expressing the polynomial so that it involves only a finite number of operations.
To find the closed form we starting with our function:
We multiply both sides of the function by x to get:
Next we subtract SxS to get
S  xS = 1 + x + x^2 + x^3 ...  x  x^2  x^3 ...
Grouping like terms we get
(1  x)S = 1 + (x  x) + (x^2  x^2) + (x^3  x^3)
Which simplifies to
(1  x)S = 1
Dividing both sides by we get
So the closed form of
 1 + x + x^{2} + x^{3} + ...
is
For convenience we can write, although this isn't true for any particular value of x.
info  Infinite sums
The two expressions are not equal. It's just that for certain values of x (1 < x < 1), we can approximate the right hand side as closely as possible by adding up a large number of terms on the left hand side. For example, suppose x = 1/2, RHS = 2; we approximate the LHS using only 5 terms we get LHS equals 1 + 1/2 + 1/4 + 1/8 + 1/16 = 1.9375, which is close to 2, as you can imagine by adding more and more terms, we will get closer and closer to 2.
Anyway we really only care about its nice algebraic properties, not its numerical value. From now on we will omit the condition for equality to be true when writing out generating functions.
Consider a more general case:
where A and B are constants.
We can derive the closedform as follows:
The following identity as derived above is worth investing time and effort memorising.
Exercises
1. Find the closedform:
 (a)
 (b)
 (c)
 (d)
 (e)
2. Given the closedform, find a function f(n) for the coefficients of x^{n}:
 (a) (Hint: note the plus sign in the denominator)
 (b) (Hint: substitute A=1 and B=2 into )
 (c) (Hint: multiply all the terms in by z)
Method of Substitution
We are given that:
 1 + z + z^{2} + ... = 1/(1  z)
and we can obtain many other generating functions by substitution. For example: letting z = x^{2} we have:
 1 + x^{2} + x^{4} + ... = 1/(1  x^{2})
Similarly
 A + ABx + A(Bx)^{2} + ... = A/(1  Bx)
is obtained by letting z = Bx then multiplying the whole expression by A.
Exercises
1. What are the coefficients of the powers of x:
 1/(1  2x^{3})
2. What are the coefficients of the powers of x (Hint: take out a factor of 1/2):
 1/(2  x)
Linear Recurrence Relations
The Fibonacci series
 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...
where each and every number, except the first two, is the sum of the two preceding numbers. We say the numbers are related if the value a number takes depends on the values that come before it in the sequence. The Fibonacci sequence is an example of a recurrence relation, it is expressed as:
where x_{n} is the (n+ 1)th number in the sequence. Note that the first number in the sequence is denoted x_{0}. Given this recurrence relation, the question we want to ask is "can we find a formula for the (n+1)th number in the sequence?". The answer is yes, but before we come to that, let's look at some examples.
Example 1
The expressions
define a recurrence relation. The sequence is: 1, 1, 5, 13, 41, 121, 365... Find a formula for the (n+1)th number in the sequence.
Solution Let G(z) be generating function of the sequence, meaning the coefficient of each power (in ascending order) is the corresponding number in the sequence. So the generating functions looks like this
Now, by a series of algebraic manipulations, we can find the closed form of the generating function and from that the formula for each coefficient
by definition x_{n}  2x_{n  1}  3x_{n  2} = 0
by the method of partial fractions we get:
each part of the sum is in a recognisable closedform. We can conclude that:
the reader can easily check the accuracy of the formula.
Example 2
Find a nonrecurrent formula for x_{n}.
Solution Let G(z) be the generating function of the sequence described above.
Therefore x_{n} = 1, for all n.
Example 3
A linear recurrence relation is defined by:
Find the general formula for x_{n}.
Solution Let G(z) be the generating function of the recurrence relation.
Therefore
Exercises
1. Derive the formula for the (n+1)th numbers in the sequence defined by the linear recurrence relations:
2. Derive the formula for the (n+1)th numbers in the sequence defined by the linear recurrence relations:
3. (Optional) Derive the formula for the (n+1)th Fibonacci numbers.
Further Counting
Consider the equation
 a + b = n; a, b ≥ 0 are integers
For a fixed positive integer n, how many solutions are there? We can count the number of solutions:
 0 + n = n
 1 + (n  1) = n
 2 + (n  2) = n
 ...
 n + 0 = n
As you can see there are (n + 1) solutions. Another way to solve the problem is to consider the generating function
 G(z) = 1 + z + z^{2} + ... + z^{n}
Let H(z) = G(z)G(z), i.e.
 H(z) = (1 + z + z^{2} + ... + z^{n})^{2}
I claim that the coefficient of z^{n} in H(z) is the number of solutions to a + b = n, a, b > 0. The reason why lies in the fact that when multiplying like terms, indices add.
Consider
 A(z) = 1 + z + z^{2} + z^{3} + ...
Let
 B(z) = A^{2}(z)
it follows
 B(z) = (1 + z + z^{2} + z^{3} + ...) + z(1 + z + z^{2} + z^{3} + ...) + z^{2}(1 + z + z^{2} + z^{3} + ...) + z^{3}(1 + z + z^{2} + z^{3}) + ...
 B(z) = 1 + 2z + 3z^{2} + ...
Now the coefficient of z^{n} (for n ≥ 0) is clearly the number of solutions to a + b = n (a, b > 0).
We are ready now to derive a very important result: let t_{k} be the number solutions to a + b = n (a, b > 0). Then the generating function for the sequence t_{k} is
 T(z) = (1 + z + z^{2} + ... + z^{n} + ...)(1 + z + z^{2} + ... + z^{n} + ...)
i.e.
Counting Solutions to a_{1} + a_{2} + ... + a_{m} = n
Consider the number of solutions to the following equation:
 a_{1} + a_{2} + ... + a_{m} = n
where a_{i} ≥ 0; i = 1, 2, ... m. By applying the method discussed previously. If t_{k} is the number of solutions to the above equation when n = k. The generating function for t_{k} is
but what is t_{k}? Unless you have learnt calculus, it's hard to derive a formula just by looking at the equation of T(z). Without assuming knowledge of calculus, we consider the following counting problem.
"You have three sisters, and you have n (n ≥ 3) lollies. You decide to give each of your sisters at least one lolly. In how many ways can this be done?"
One way to solve the problem is to put all the lollies on the table in a straight line. Since there are n lollies there are (n  1) gaps between them (just as you have 5 fingers on each hand and 4 gaps between them). Now get 2 dividers, from the (n  1) gaps available, choose 2 and put a divider in each of the gaps you have chosen! There you have it, you have divided the n lollies into three parts, one for each sister. There are ways to do it! If you have 4 sisters, then there are ways to do it. If you have m sisters there are ways to do it.
Now consider: "You have three sisters, and you have n lollies. You decide to give each of your sisters some lollies (with no restriction as to how much you give to each sister). In how many ways can this be done?"
Please note that you are just solving:
 a_{1} + a_{2} + a_{3} = n
where a_{i} ≥ 0; i = 1, 2, 3.
You can solve the problem by putting n + 3 lollies on the table in a straight line. Get two dividers and choose 2 gaps from the n + 2 gaps available. Now that you have divided n + 3 lollies into 3 parts, with each part having 1 or more lollies. Now take back 1 lollies from each part, and you have solved the problem! So the number of solutions is . More generally, if you have m sisters and n lollies the number of ways to share the lollies is
 .
Now to the important result, as discussed above the number of solutions to
 a_{1} + a_{2} + ... + a_{m} = n
where a_{i} ≥ 0; i = 1, 2, 3 ... m is
i.e.
Example 1
The closed form of a generating function T(z) is
and t_{k} in the coefficient of z^{k} is T(z). Find an explicit formula for t_{k}.
Solution
Therefore t_{k} = k
Example 2
Find the number of solutions to:
 a + b + c + d = n
for all positive integers n (including zero) with the restriction a, b, c ,d ≥ 0.
Solution By the formula
so
 the number of solutions is
More Counting
We turn to a slightly harder problem of the same kind. Suppose we are to count the number of solutions to:
 2a + 3b + c = n
for some integer , with a, b, also c greater than or equal zero. We can write down the closed form straight away, we note the coefficient of x^{n} of:
is the required solution. This is due to, again, the fact that when multiplying powers, indices add.
To obtain the number of solutions, we break the expression into recognisable closedforms by method of partial fraction.
Example 1
Let s_{k} be the number of solutions to the following equation:
 2a + 2b = n; a, b ≥ 0
Find the generating function for s_{k}, then find an explicit formula for s_{n} in terms of n.
Solution
Let T(z) be the generating functions of t_{k}
 T(z) = (1 + z^{2} + z^{4} + ... + z^{2n} + ...)^{2}
It's not hard to see that
Example 2
Let t_{k} be the number of solutions to the following equation:
 a + 2b = n; a, b ≥ 0
Find the generating function for t_{k}, then find an explicit formula for t_{n} in terms of n.
Solution
Let T(z) be the generating functions of t_{k}
 T(z) = (1 + z + z^{2} + ... + z^{n} + ...)(1 + z^{2} + z^{4} + ... + z^{2n} + ...)
 A = 1/4, B = 3/4, C = 1/4
Exercises
1. Let
be the generating functions for t_{k} (k = 0, 1, 2 ...). Find an explicit formula for t_{k} in terms of k.
2. How many solutions are there the following equations if m is a given constant
where a, b and c ≥ 0
Problem Set
1. A new Company has borrowed $250,000 initial capital. The monthly interest is 3%. The company plans to repay $x before the end of each month. Interest is added to the debt on the last day of the month (compounded monthly).
Let D_{n} be the remaining debt after n months.
a) Define D_{n} recursively.
b) Find the minimum values of x.
c) Find out the general formula for D_{n}.
d) Hence, determine how many months are need to repay the debt if x = 12,000.
2. A partion of n is a sequence of positive integers (λ1,λ1,..,λr) such that λ1 ≥ λ2 ≥ .. ≥ λr and λ1 + λ2 + .. + λr = n. For example, let n = 5, then (5), (4,1), (3,2), (3,1,1), (2,2,1), (2,1,1,1), (1,1,1,1,1) are all the partions of 5. So we say the number of partions of 5 is 7. Derive a formula for the number of partions of a general n.
3. A binary tree is a tree where each node can have up to two child nodes. The figure below is an example of a binary tree.
a) Let c_{n} be the number of unique arrangements of a binary tree with totally n nodes. Let C(z) be a generating function of c_{n}.
 (i) Define C(z) using recursion.
 (ii) Hence find the closed form of C(z).
b) Let be a power series.
 (i) By considering the nth derivative of P(x), find a formula for p_{n}.
 (ii) Using results from a) and b)(i) , or otherwise, derive a formula for c_{n}.
Hint: Instead of doing recursion of finding the change in c_{n} when adding nodes at the buttom, try to think in the opposite way, and direction.(And no, not deleting nodes)
Project  Exponential generating function
This project assumes knowledge of differentiation.
(Optional)0.
 (a)

 (i) Differentiate log x by first principle.

 (ii)*** Show that the remaining limit in last part that can't be evaluated indeed converges. Hence finish the differentiation by assigning this number as a constant.
 (b) Hence differentiate .
1. Consider
 (a) Find out the nth derivative of E(x).
 (b) By considering the value of the nth derivative of E(x) at x = 0, express E(x) in power series/infinite polynomial form.
(Optional)2.
 (a) Find out the condition for the geometric progression(that is the ordinary generating function introduced at the beginning of this chapter) to converges. (Hint: Find out the partial sum)
 (b) Hence show that E(x) in the last question converges for all real values of x. (Hint: For any fixed x, the numerator of the general term is exponential, while the denominator of the general term is factorial. Then what?)
3. The function E(x) is the most fundamental and important exponential generating function, it is similar to the ordinary generating function, but with some difference, most obviously having a fractorial fraction attached to each term.
 (a) Similar to ordinary generating function, each term of the polynomial expansion of E(x) can have number attached to it as coefficient. Now consider
 Find and compare it with A(x). What do you discover?
 (b) Substitute nz, where n is a real number and z is a free variable, into E(x), i.e. E(nz). What have you found?
4. Apart from A(x) defined in question 2, let
 (a) What is A(x) multiplied by B(x)? Compare this with ordinary generating function, what is the difference?
 (b) What if we blindly multiply A(x) with x(or x^{n} in general)? Will it shift coefficient like what happened in ordinary generating function?
Notes: Question with *** are difficult questions, although you're not expected to be able to answer those, feel free to try your best.
Contents
Feedback
What do you think? Too easy or too hard? Too much information or not enough? How can we improve? Please let us know by leaving a comment in the discussion tab. Better still, edit it yourself and make it better.