Let PQR and S be the logical statements P f B rightarrow C i

Let P,Q,R, and S be the logical statements P= \"f: B rightarrow C is a 1-1 function\" Q= \"g: A rightarrow B is an onto function\" R= \"f composition g: A rightarrow C is an onto function\" S= \"f composition g: A rightarrow C is a 1 .1 function\" Give a truth table for the logical proposition ((P logicalAND Q) logicalOR R) rightwardsdoublearrow (R logical AND S). Under what circumstances in the truth table you have written in (a), if any, can you logically conclude that f composition g is a bijection? What is the generating function for the sequence (5,6,7,8, ...)? What is the generating function for the sequence (8,7,6,5,4,3,2,1,0,0,0,0, ...)? What is the generating function for the sum of the sequences in (a) and (b)? State and prove the \"Rule of 11\" for divisibility of decimal integers by 11. Give the remainder of 11^179 divided by 20.

Solution

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 n a . By varying n, we get different values of n a . In this way we get a sequence of real numbers 0 a , 1 a , 2 a , … from which we can define a power series (which in some sense can be regarded as an ‘infinitedegree polynomial’) 2 01 2 G x a ax ax ( ) = ++ +\". The above G x( ) is the generating function for the sequence 0 a , 1 a , 2 a , …. 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 17 x in the expansion of 5 7 20 (1 ) + + x x . Solution. The only way to form an 17 x term is to gather two 5 x and one 7 x . Since there are 20 2 C =190 ways to choose two 5 x from the 20 multiplicands and 18 ways to choose one 7 x 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 20 2 C =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 17 a = 3420 . Mathematical Database Page 2 of 17 2. Techniques of Computation Let us once again give the definition of a generating function before we proceed. Definition. Given a sequence 0 a , 1 a , 2 a , …, we define the generating function of the sequence { }n a to be the power series 2 01 2 G x a ax ax ( ) = ++ +\". 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) 2005 C0 , 2005 C1 , 2005 C2 , …, 2005 C2005 , 0, 0, 0, 0, … Solution. (a) The generating function is 2345 6 7 2345 () 1 1 1 1 1 1 0 0 1 Gx x x x x x x x xx x x x =+ + + + + + + + =+ + + + + \" We can apply the formula for the sum of a geometric series to rewrite G x( ) as 6 1 ( ) 1 x G x x = . (b) The generating function is 234 Gx x x x x () 1 = ++ + + +\". When | | 1 x < , we can apply the formula for the sum to infinity of a geometric series to rewrite G x( ) as 1 ( ) 1 G x x = . In working with generating functions, we shall ignore the question of convergence and simply say 1 ( ) 1 G x x = . (c) The generating function is 2 Gx x x () 1 3 3 1 =+ + + , and of course, the binomial theorem enables us to simplify the answer as 3 Gx x ( ) (1 ) = + . Mathematical Database Page 3 of 17 (d) The generating function is 2005 2005 2005 2 2005 2004 2005 2005 0 1 2 2004 2005 Gx C C x C x C x C x ( ) = + + ++ + \" , and the binomial theorem once again enables us to simplify the answer as 2005 Gx x ( ) (1 ) = + . 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), 234 Gx x x x x () 1 =+ + + + +\" is not in closed form while 1 ( ) 1 G x x = is. The reason for trying to put a generating function in 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 234 Gx x x x x () 2 3 4 = ++++\" or 0 1 ( ) 2 1 n n n Gx x n = = + , 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.