High School Mathematics Extensions/Counting and Generating Functions

High School Mathematics Extensions

---

Supplementary Chapters — Primes and Modular Arithmetic — Logic

Mathematical Proofs — Set Theory and Infinite Processes — Counting and Generating Functions — Discrete Probability

Matrices — Further Modular Arithmetic — Mathematical Programming — Markov Chains

Before we begin: This chapter assumes knowledge of

1. Ordered selection (permutation) and unordered selection (combination) covered in Basic counting,
2. Method of Partial Fractions and,
3. 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:

$\lim _{x\to \infty }{\frac {x^{2}+x}{x^{2}}}=1+\lim _{x\to \infty }{\frac {1}{x}}=1$

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:

$x_{1}+x_{2}+2x_{3}=m$

where

$x_{n}\geq 0$; n = 1, 2, 3

how many unique solutions are there if $m=55$?

Before we tackle that problem, let's consider the infinite polynomial:

$S=1+x+x^{2}+x^{3}+...+x^{n}+x^{n+1}...$

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:

$S=1+x+x^{2}+x^{3}+...$

We multiply both sides of the function by x to get: $xS=x+x^{2}+x^{3}+...$

Next we subtract S-xS 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 ${\frac {1}{1-x}}$ we get $S={\frac {1}{1-x}}$

So the closed form of

1 + x + x² + x³ + ...

is

${\frac {1}{1-x}}$

For convenience we can write, although this isn't true for any particular value of x.

$1+x+x^{2}+x^{3}+...={\frac {1}{1-x}}\ ;\ -1<x<1$

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:

$S=A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...$

where A and B are constants.

We can derive the closed-form as follows:

${\begin{matrix}S&=&A+&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\BxS&=&&ABx+AB^{2}x^{2}+AB^{3}x^{3}+...\\\\(1-Bx)S&=&A\\S&=&{\frac {A}{1-Bx}}\end{matrix}}$

The following identity as derived above is worth investing time and effort memorising.

$A+ABx+AB^{2}x^{2}+AB^{3}x^{3}+...={\frac {A}{1-Bx}}$

Exercises

1. Find the closed-form:

(a)$1-z+z^{2}-z^{3}+z^{4}-z^{5}+...$

(b)$1+2z+4z^{2}+8z^{3}+16z^{4}+32z^{5}+...$

(c)$z+z^{2}+z^{3}+z^{4}+z^{5}+...$

(d)$3-4z+4z^{2}-4z^{3}+4z^{4}-4z^{5}+...$

(e)$1-z^{2}+z^{4}-z^{6}+z^{8}-z^{10}+...$

2. Given the closed-form, find a function f(n) for the coefficients of xⁿ:

(a)${\frac {1}{1+z}}$ (Hint: note the plus sign in the denominator)

(b)${\frac {1}{1-2z}}$ (Hint: substitute A=1 and B=2 into ${\frac {A}{1-Bz}}$)

(c)${\frac {z}{1-z}}$ (Hint: multiply all the terms in ${\frac {1}{1-z}}$ by z)

Method of Substitution

We are given that:

1 + z + z² + ... = 1/(1 - z)

and we can obtain many other generating functions by substitution. For example: letting z = x² we have:

1 + x² + x⁴ + ... = 1/(1 - x²)

Similarly

A + ABx + A(Bx)² + ... = 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³)

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:

${\begin{matrix}x_{n}&=&x_{n-1}&+&\ x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

where x_n is the (n+ 1)th number in the sequence. Note that the first number in the sequence is denoted x₀. 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

${\begin{matrix}x_{n}&=&2x_{n-1}&+&3x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\end{matrix}}$

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

$G(z)=1+z+5z^{2}+13z^{3}+41z^{4}+121z^{5}+...$

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

${\begin{matrix}&&G(z)&=&x_{0}+&x_{1}z+&x_{2}z^{2}&+&x_{3}z^{3}+x_{4}z^{4}+x_{5}z^{5}+...\\2z&\times &G(z)&=&&2x_{0}z+&2x_{1}z^{2}&+&...\\3z^{2}&\times &G(z)&=&&&3x_{0}z^{2}&+&...\\\end{matrix}}$

${\begin{matrix}G(z)-2zG(z)-3z^{2}G(z)&=&x_{0}+(x_{1}-2x_{0})z&+\\&&(x_{2}-2x_{1}-3x_{0})z^{2}&+\\&&(x_{3}-2x_{2}-3x_{1})z^{3}&+&...\end{matrix}}$

by definition x_n - 2x_{n - 1} - 3x_{n - 2} = 0

${\begin{matrix}(1-2z-3z^{2})&\times &G(z)&=&x_{0}+(x_{1}-2x_{0})z\\\\&&G(z)&=&{\frac {1-z}{1-2z-3z^{2}}}\\\\&&G(z)&=&{\frac {1-z}{(1-3z)(1+z)}}\end{matrix}}$

by the method of partial fractions we get:

$G(z)={\frac {1}{2}}\times {\frac {1}{1-3z}}+{\frac {1}{2}}\times {\frac {1}{1+z}}$

each part of the sum is in a recognisable closed-form. We can conclude that:

$x_{n}={\frac {1}{2}}\times 3^{n}+{\frac {1}{2}}\times (-1)^{n}$

the reader can easily check the accuracy of the formula.

Example 2

${\begin{matrix}x_{n}&=&x_{n-1}&+&x_{n-2}&-&x_{n-3};\ {\mbox{for n}}\geq 3\\x_{0}&=&1\\x_{1}&=&1\\x_{2}&=&1\end{matrix}}$

Find a non-recurrent formula for x_n.

Solution Let G(z) be the generating function of the sequence described above.

$G(z)=x_{0}+x_{1}z+x_{2}z^{2}+...$

${\begin{matrix}G(z)(1-z-z^{2}+z^{3})&=&x_{0}&+&(x_{1}-x_{0})z+(x_{2}-x_{1}-x_{0})z^{2}\\G(z)(1-z-z^{2}+z^{3})&=&1-z^{2}\\\\\end{matrix}}$

${\begin{matrix}G(z)&=&{\frac {1-z^{2}}{1-z-z^{2}+z^{3}}}\\\\G(z)&=&{\frac {1-z}{1-2z+z^{2}}}\\\\G(z)&=&{\frac {1}{1-z}}\end{matrix}}$

Therefore x_n = 1, for all n.

Example 3

A linear recurrence relation is defined by:

${\begin{matrix}x_{n}&=&x_{n-1}&+&6x_{n-2}+1;\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

Find the general formula for x_n.

Solution Let G(z) be the generating function of the recurrence relation.

$G(z)(1-z-6z^{2})=x_{0}+(x_{1}-x_{0})z+(x_{2}-x_{1}-6x_{0})z^{2}+...$

$G(z)(1-z-6z^{2})=1+z^{2}+z^{3}+z^{4}+...$

$G(z)(1-z-6z^{2})=1+z^{2}(1+z+z^{2}+...)$

$G(z)(1-z-6z^{2})=1+{\frac {z^{2}}{1-z}}$

$G(z)(1-z-6z^{2})={\frac {1-z+z^{2}}{1-z}}$

${\begin{matrix}G(z)&=&{\frac {1-z+z^{2}}{(1-z)(1+2z)(1-3z)}}\\G(z)&=&-{\frac {1}{6(1-z)}}+{\frac {7}{15(1+2z)}}+{\frac {7}{10(1-3z)}}\end{matrix}}$

Therefore

$x_{n}=-{\frac {1}{6}}+{\frac {7}{15}}(-2)^{n}+{\frac {7}{10}}3^{n}$

Exercises

1. Derive the formula for the (n+1)th numbers in the sequence defined by the linear recurrence relations:

${\begin{matrix}x_{n}&=&2x_{n-1}&-&1;\ {\mbox{for n}}\geq 1\\x_{0}&=&1\end{matrix}}$

2. Derive the formula for the (n+1)th numbers in the sequence defined by the linear recurrence relations:

${\begin{matrix}3x_{n}&=&-4x_{n-1}&+&x_{n-2};\ {\mbox{for n}}\geq 2\\x_{0}&=&1\\x_{1}&=&1\\\end{matrix}}$

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² + ... + zⁿ

Let H(z) = G(z)G(z), i.e.

H(z) = (1 + z + z² + ... + zⁿ)²

I claim that the coefficient of zⁿ 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² + z³ + ...

Let

B(z) = A²(z)

it follows

B(z) = (1 + z + z² + z³ + ...) + z(1 + z + z² + z³ + ...) + z²(1 + z + z² + z³ + ...) + z³(1 + z + z² + z³) + ...

B(z) = 1 + 2z + 3z² + ...

Now the coefficient of zⁿ (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² + ... + zⁿ + ...)(1 + z + z² + ... + zⁿ + ...)

$T(z)={\frac {1}{(1-z)^{2}}}$

i.e.

${\frac {1}{(1-z)^{2}}}=1+2z+3z^{2}+4z^{3}+...+(n+1)z^{n}+...$

Counting Solutions to a₁ + a₂ + ... + a_m = n

Consider the number of solutions to the following equation:

a₁ + a₂ + ... + 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

$T(z)={\frac {1}{(1-z)^{m}}}$

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 $n-1 \choose 2$ ways to do it! If you have 4 sisters, then there are $n-1 \choose 3$ ways to do it. If you have m sisters there are $n-1 \choose m-1$ 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₁ + a₂ + a₃ = 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 $n+2 \choose 2$. More generally, if you have m sisters and n lollies the number of ways to share the lollies is

${{n+m-1} \choose {m-1}}={{n+m-1} \choose {n}}$ .

Now to the important result, as discussed above the number of solutions to

a₁ + a₂ + ... + a_m = n

where a_i ≥ 0; i = 1, 2, 3 ... m is

${{n+m-1} \choose {n}}$

i.e.

${\frac {1}{(1-z)^{m}}}=\sum _{i=0}^{\infty }{m+i-1 \choose i}z^{i}$

Example 1

The closed form of a generating function T(z) is

$T(z)={\frac {z}{(1-z)^{2}}}$

and t_k in the coefficient of z^k is T(z). Find an explicit formula for t_k.

Solution

${\begin{matrix}{\frac {1}{(1-z)^{2}}}&=&\sum _{i=0}^{\infty }(i+1)z^{i}\\\\{\frac {z}{(1-z)^{2}}}&=&z\sum _{i=0}^{\infty }(i+1)z^{i}\\\\&=&\sum _{i=0}^{\infty }(i+1)z^{i+1}\\\end{matrix}}$

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

${\begin{matrix}{\frac {1}{(1-z)^{4}}}&=&\sum _{i=0}^{\infty }{{n+3} \choose {3}}z^{i}\\\\\end{matrix}}$

so

the number of solutions is ${{n+3} \choose {3}}$

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 $n\geq 0$, 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ⁿ of:

$(1+x^{2}+x^{4}+...)(1+x^{3}+x^{6}+...)(1+x+x^{2}+...)={\frac {1}{(1-x^{2})(1-x^{3})(1-x)}}$

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 closed-forms 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² + z⁴ + ... + z²ⁿ + ...)²

$T(z)={\frac {1}{(1-z^{2})^{2}}}$

It's not hard to see that

$s_{n}=0\ {\mbox{if n is odd}}$

$s_{n}={n/2+1 \choose n/2}={n/2+1 \choose 1}=n/2+1\ {\mbox{if n is even}}$

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² + ... + zⁿ + ...)(1 + z² + z⁴ + ... + z²ⁿ + ...)

$T(z)={\frac {1}{(1-z)}}\times {\frac {1}{1-z^{2}}}$

$T(z)={\frac {1}{(1-z)^{2}}}\times {\frac {1}{1+z}}$

$T(z)={\frac {Az+B}{(1-z)^{2}}}+{\frac {C}{1+z}}$

A = -1/4, B = 3/4, C = 1/4

$T(z)=-{\frac {1}{4}}\sum _{i=0}^{\infty }(i+1)z^{i+1}+{\frac {3}{4}}\sum _{i=0}^{\infty }(i+1)z^{i}+{\frac {1}{4}}\sum _{i=0}^{\infty }(-1)^{i}z^{i}$

$t_{k}=-{\frac {1}{4}}k+{\frac {3}{4}}(k+1)+{\frac {1}{4}}(-1)^{k}$

Exercises

1. Let

$T(z)={\frac {1}{(1+z)^{2}}}$

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

$a+b+2c=m$

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 $P(x)={\sqrt {1+ax}}=p_{0}+p_{1}x+p_{2}x^{2}+p_{3}x^{3}...$ be a power series.

(i) By considering the n-th 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 bottom, 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 $a^{x}$.

1. Consider $E(x)=e^{x}$

(a) Find out the n-th derivative of E(x).

(b) By considering the value of the n-th 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 $A(x)=a_{1}+a_{2}{\frac {x}{1!}}+a_{3}{\frac {x^{2}}{2!}}+a_{4}{\frac {x^{3}}{3!}}+...$

Find $A'(x)$ 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 $B(x)=b_{1}+b_{2}{\frac {x}{1!}}+b_{3}{\frac {x^{2}}{2!}}+b_{4}{\frac {x^{3}}{3!}}+...$

(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ⁿ 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.

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.