genfun2sln.html

Generating functions

An important idea in mathematics is to establish connections between two fields in order to apply knowledge in one field to the other field, or at least take a problem in one field and transform it to a problem in the other field. This idea motivates the idea of a generating function, which establishes a connection between functions of a real variable and sequences of numbers.

Definition: Given a numeric sequence the series is called the generating function of the sequence.

To find the generating function for a sequence means to find a closed form formula for f(x), one that has no ellipses.

Example: The generating function for the constant sequence , has closed form

This is because the sum of the geometric series is (for all x less than 1 in absolute value).

> f(x) =sum(x^'i','i'=0..infinity);

>

Problem: Find the generating function for

Problem: Suppose f(x) is the generating function for a and g(x) is the generating function for b. Show that f(x) + g(x) is the generating function for a + b, but that f(x) * g(x) is not the generating function for a*b.

Definition: The convolution of two sequences a and b is the sequence c defined by

Problem : Suppose f(x) is the generating function for a and g(x) is the generating function for b. Show that is the generating function for the convolution of a and b.

Every function which has derivatives of all orders at 0 is the generating function of its Taylor expansion at 0.

> 1/(1-x)=series(1/(1-x),x,20);

Uses of generating functions

One use for generating functions is get closed formulas for sequences which are defined recursively in terms of previous terms. The defining equations for such sequences are called recurence relations

Problem: Find a formula for the nth term of the sequence defined by , and .

Investigation. This rule is directly programmable in Maple, using a recursive program (g refers to itself in its definition).

> g := proc(n) options remember; if n = 0 then 1 else 5*g(n-1) - 3 fi end;

> g(100);

> seq(a[n]=g(n),n=0..10);

>

A Solution using generating functions.

= =

Doing a partial fraction decomposition of the right hand side

> convert((1-4*x)/((1-5*x)*(1-x)),parfrac,x);

f(x) =

So by inspection, we see the formula for

Checking this,

>

> p :=unapply(5^n-3*(sum(5^'i','i'=0..n-1)),n);

> k := n-> (5^n+3)/4;

> seq(k(n),n=0..10);

> seq(g(n),n=0..10);

> seq(p(n),n=0..10);

> f(x) := collect(sum(a[i]*x^'i','i'=0..5),x);

> expand( 5*f(x)*x);

Actually, DeMoivre introduced the notion of generating function in 1730 to solve recurrence relations. Here is a famous one first defined by Fibonacci in 1200.

Problem: Given that , find a closed formula for

Another use for generating functions is to solve counting problems . Most counting problems lie in a sequence of counting problems. If we can identify the generating function of that sequence we have a crack at finding the formula to solve the counting problems in the sequence.

Example. For fixed n, let C(n,r) be the number of combinations of n things taken r at a time, r = 0 to n. The generating function for this sequence is .

The way to see this is to think of how the coefficient of in the expansion of is made up. The expansion of has terms before collecting is done. Each term is a product n things some of which are x's and the rest 1's. The coefficient of is the number of those terms which has exactly r x's. We can program this directly in Maple.

> binom := proc(n,r)
local x,cof;
if r = 0 or r=n then 1 else
coeff( expand( (1+x)^n),x,r) ;
fi end:

> seq(binom(4,i),i=0..4);

So, for example, the number of ways to choose 10 books from a library of 40 books is

> binom(40,10);

Checking that with the Maple word binomial --

> binomial(40,10);

Same result.

Problem. How many Lotto tickets have only even numbers? prime numbers?

Problem . Show that for all positive integers n and r with r < n, .

Problem. Show that

This is only the tip of the iceberg. The answers to many many counting problems are coefficients of certain polynomial generating functions.

Problem. A library has 5 black books, 4 red books, and 3 yellow books, all with different titles. How many ways can a student take home 6 books, 2 of each color?

Solution. Let . When A(x,y,z) is expanded out, it will have terms each of which the product of 5 x's or 1's with 4 y's or 1's and 3 z's or 1's. Each term can be thought of as a checkout set of books. 1x111 yy11 1z1 means the 2nd black, 1st and 2nd red and 2nd yellow books were checked out. With that interpretation, the coefficient of is answer we seek, and this can be obtained by expanding out and collecting like terms.

> A := (1+x)^5*(1+y)^4*(1+z)^3;

> cf :=coeff(collect(expand(A) ,x),x^2);

> cf :=coeff(collect(cf ,y),y^2);

> cf :=coeff(collect(cf ,z),z^2);

Second Solution: Choose 2 of the 5 blacks, then choose 2 of the 4 reds, and last choose 2 of the 3 yellows. This gives

> binom(5,2)*binom(4,2)*binom(3,2);

Problem. A library has 5 indistinguishable black books, 4 indistinguishable red books, and 3 indistinguishable yellow books. How many distinguishable ways can a student take home 6 books, 2 of each color?

Solution 1 . The student chooses 2 black books (only one way to do that since the black books are indistinguishable) then 2 reds then 2 yellows. The set of things we are counting is the cartesian product of three sets each with 1 element, so the answer is 1.

Solution 2. Think of choosing the black books first: since they are indistinguishable amonst each other, the only distinguishing characteristic of the choice is the number of black books chosen. We could represent this by choosing a term of the polynomial ; thus choosing the term 1 means no black books are chosen, etc. Similarly choosing the red books would be to choose a term of and choosing the yellow books would be to choose a term of . The polynomial when expanded has 6*5*4 = 120 terms (none alike), each of which represents a distinguisable way of taking home a set of books from the library, including the term 1*1*1 which is taking home the empty set of books. The coefficient of is 1 which is the number of ways to take home 6 books, two of each color.

Solution 1. Direct count. Make a list. of the triples [x,y,z] of integers satisfying x+y+z = 6, 1<= x <=5, 1 <= y <= 4, and 1 <= z <= 4. [4,1,1], [3,2,1],[3,1,2], [2,3,1],[2,2,2],[2,1,3], [1,2,3],[1,3,2],[1,4,1]. There are 9.

>

Solution 2. As above, we can form a polynomial p = , where the term 1 has been left out of each factor since at least one book of each color is to be chosen. When expanded this polynomial has 5*4*3 = 60 terms, each representing a way for the student to take home a set of books at least 1 of each color. What we want is the number of terms of degree 6. Those represent the ways a student could take home 6 books, at least one of each color. If we set x = y = z in p and collect like terms then the coefficient of is the desired answer.

> p := (x+x^2+x^3+x^4+x^5)*(y+y^2+y^3+y^4)*(z+z^2+z^3);

> q :=subs({y=x,z=x},p);

> coeff(q,x^6);

>

Problem. A library has 5 indistinguishable black books, 4 indistinguishable red books, and 3 indistinguishable yellow books. How many distinguishable ways can a student take home 6 books?

Solution 1. Direct count. Make a list. of the triples [x,y,z] of integers satisfying x+y+z = 6, 0<= x <=5, 0 <= y <= 4, and 0 <= z <= 4.

Solution 2. Polynomial solution.

> p := (1+x+x^2+x^3+x^4+x^5)*(1+y+y^2+y^3+y^4)*(1+z+z^2+z^3);

> q :=subs({y=x,z=x},p);

>

> coeff(q,x^6);

>