Generating Functions and Their Applications

Abstract

Chapter Generating Functions and Their Applications PART II The Counting Problem EXAMPLES OF GENERATING FUNCTIONS Much of combinatorics is devoted to developing tools for counting\n We have seen that it is often important to count the number of arrangements or patterns but in practice it is impossible to list all of these arrangements\n Hence we need tools to help us in counting\n In the next four chapters we present a number of tools that are useful in counting\n One of the most powerful tools that we shall present is the notion of the generating function\n This chapter is devoted to generating functions Often in combinatorics we seek to count a quantity a k that depends on an input or a parameter say k\n This is true for instance if a k is the number of steps required to perform a computation if the input has size k\n We can formalize the dependence on k by speaking of a sequence of unknown values a a a a k We seek to determine the kth term in this sequence\n Generating functions provide a simple way to encode a sequence such as a a a a k which can readily be decoded to nd the terms of the sequence\n The trick will be to see how to compute the encoding or generating function for the sequence without having the sequence\n Then we can decode to nd a k The method will enable us to determine the unknown quantity a k in an indirect but highly eective manner The method of generating functions that we shall present is an old one\n Its roots are in the work of De Moivre around it was developed by Euler in in connection with partition problems and it was treated extensively in the late eighteenth and early nineteenth centuries by Laplace primarily in connection with probability theory\n In spite of its long history the method continues to have In an elementary treatment this chapter should be omitted Chapters and are the only chapters that make use of the calculus prerequisites except for assuming a certain level of math widespread application as we shall see\n For a more complete treatment of generat ing functions see Lando !" MacMahon !" Riordan !" Srivastava and Manocha !\t" or Wilf !"\n See also Riordan !\t" Power Series In this chapter we use a fundamental idea from calculus the notion of power series The results about power series we shall need are summarized in this subsection The reader who wants more details including proofs of these results can consult most any calculus book A power series is an innite series of the form P k a k x k Such an innite series always converges for x Either it does not converge for any other value of x or there is a positive number R possibly innite so that it converges for all x with jxj R\n In the latter case the largest such R is called the radius of convergence In the former case we say that is the radius of convergence\n A power series P k a k x k can be thought of as a function of x fx which is dened for those values of x for which the innite sum converges and is computed by calculating that innite sum\n In most of this chapter we shall not be concerned with matters of convergence\n We simply assume that x has been chosen so that P k a k x k converges Power series arise in calculus in the following way\n Suppose that fx is a function which has derivatives of all orders for all x in an interval containing Then fx X k f k k# x k f % f x% f # x % f # x % The power series on the righthand side of converges for some values of x at least for x The power series is called the Maclaurin series expansion for f or the Taylor series expansion for f about x Some of the most famous and useful Maclaurin expansions are the following x X k x k % x% x % x % for jxj e x X k k# x k % x% # x % # x % for jxj sinx X k k k % # x k x # x % # x for jxj ln % x X k k k x k x x % x x % for jxj This assumption can be made more precise by thinking of P k a k x k as simply a formal expression a formal power series rather than as a function and by performing appropriate To show for instance that is a special case of it suces to observe that if fx e x then f k x e x for all k and f k Readers should check for themselves that Equations and are also special cases of One of the reasons that power series are so useful is that they can easily be added multiplied divided composed dierentiated or integrated\n We remind the reader of these properties of power series by formulating several general principles Principle Suppose that fx P k a k x k and gx P k b k x k Then fx%gx fxgx and fxgx can be computed by respectively adding term by term multiplying out or using long division\n !This is true for division only if gx is not zero for the values of x in question\n" Specically fx % gx X k a k % b k x k a % b % a % b x% a % b x % fxgx a X k b k x k % a x X k b k x k % a x X k b k x k % a b % b x% b x % % a xb % b x% b x % % a x b % b x% b x % % fx gx a P k b k x k % a x P k b k x k % a x P k b k x k % a b % b x% b x % % a x b % b x% b x % % a x b % b x% b x % % If the power series for fx and gx both converge for jxj R so do fx % gx and fxgx\n If g then fxgx converges in some interval about For instance using and we have x % e x % x% x % x % % % x% # x % # x % % % % x% % # x % % # x % X k % k# x k Also x e x % x% x % x % % x% # x % # x % % x% # x % % x % x% # x % % x % x% x % % % x% x % Power series are also easy to compute under composition of functions Principle If fx gux and if we know that gu P k a k u k we have fx P k a k !ux" k Thus setting u x in Equation gives us ln % x X k k k x k Principle generalizes to the situation where we have a power series for ux Principle If a power series fx P k a k x k converges for all jxj R with R the derivative and antiderivative of fx can be computed by dierentiating and integrating term by term\n Namely df dx x d dx X k a k x k X k d dx a k x k X k ka k x k and Z x ft dt Z x X k a k t k dt X k Z x a k t k dt X k k % a k x k The power series in and also converge for jxj R For instance since x d dx x we see from and that x X k kx k % x% x % \tx % Generating Functions Suppose that we are interested in computing the kth term in a sequence a k of numbers\n We shall use the convention that a k refers to the sequence and a k written without parentheses to the kth term\n The ordinary generating function for the sequence a k is dened to be Gx X k a k x k a x % a x % a x % If the power series for gu converges for juj S and juxj S whenever jxj R then the The sum is nite if the sequence is nite and innite if the sequence is innite\n In the latter case we will think of x as having been chosen so that the sum in converges Example Suppose that a k n k for k n\n Then the ordinary generating function for the sequence a k is Gx n % n x% n x % % n n x n By the binomial expansion Theorem Gx % x n The advantage of what we have done is that we have expressed Gx in a simple closed form encoded form\n Knowing this simple form for Gx one can now possibly derive a k simply by remembering this closed form for Gx and decoding that is expanding out and searching for the coecient of x k Even more useful is the fact that as we have observed before often we are able to nd Gx without knowing a k and then to solve for a k by expanding out Example Suppose that a k for k Then Gx % x% x % By Equation Gx x provided that jxj Again the reader will note the closed form for Gx Example Often we will know the generating function but not the sequence We will try to recover the sequence from the generating function\n For example suppose that Gx X k a k x k and we know Gx x x What is a k Using Equation we have for jxj Gx x x x % x% x % Hence a k In this chapter and Chapter we study a variety of techniques for expanding out Gx to obtain the desired sequence a k Example Suppose that a k k# for k Then Gx # % # x% # x % # x % By Equation Gx e x for all values of x Example Suppose that Gx x sinx is the ordinary generating function for the sequence a k To nd a k use Equation substitute x for x and multiply by x to nd that Gx x x # x % # x x # x % # x Thus we see that a k is the kth term of the sequence # # Example Suppose that Gx cosx is the ordinary generating function for the sequence a k Since Gx has derivatives of all orders we can expand out in a Maclaurin series by calculating f k for all k and we see that Gx X k k k# x k # x % # x The verication of this is left as an exercise\n An alternative approach is to observe that Gx dsinxdx and so to use Equation Then we see that Gx d dx sinx d dx x # x % # x d dx !x" % d dx # x % d dx # x % # x % # x which agrees with Equation Example If a k the ordinary generating function is given by Gx % x% x % x % x % % x% x % x % x % x % x x x Example If a k # #\t# the ordinary generating function is given by Gx # % # x% # x % x # x % # x % # x % x e x x Example The Number of Labeled Graphs In Section we counted the number Ln e of labeled graphs with n vertices and e edges n e Cn If n is xed and we let a k Ln k k Cn let us consider the generating function G n x C\nn X k a k x k Note that in Section we computed Ln e CCn e\n Hence if r Cn G n x r X k Cr kx k By the binomial expansion Theorem we have G n x % x r % x C\nn which is a simple way to summarize our knowledge of the numbers Ln e\n In particular from we can derive a formula for the number Ln of labeled graphs of n vertices\n For Ln r X k Cr k which is G n Thus taking x in gives us Ln C\nn which is the result we derived in Section Smith Jones Brown Black White Cutting Shaping Gluing Polishing Packaging Figure A board corresponding to a job assignment problem Example Rook Polynomials Job Assignments and Storing Com puter Programs Suppose that B is any nm board such as those in Figures and with certain squares forbidden and others acceptable the acceptable ones being darkened\n Let r k B be the number of ways to choose k acceptable dark ened squares no two of which lie in the same row and no two of which lie in the same column\n We can think of B as part of a chess board\n A rook is a piece that can travel either horizontally or vertically on the board\n Thus one rook is said to be able to take another if the two are in the same row or the same column\n We wish to place k rooks on B in acceptable squares in such a way that no rook can take another\n Thus r k B counts the number of ways k nontaking rooks can be placed in acceptable squares of B The board in Figure arises from a job assignment problem\n The rows correspond to workers the columns to jobs and the i j position is darkened if worker i is suitable for job j\n We wish to determine the number of ways in which each worker can be assigned to one job no more than one worker per job so that a worker only gets a job to which he or she is suited\n It is easy to see that this is equivalent to the problem of computing r B The board in Figure arises from a problem of storing computer programs The i j position is darkened if storage location j has sucient storage capacity for program i\n We wish to assign each program to a storage location with sucient storage capacity at most one program per location\n The number of ways this can be done is again given by r B\n We shall compute r B in these two examples in the text and exercises of Section The expression RxB r B % r Bx % r Bx % is called the rook polynomial for the board B\n The rook polynomial is indeed a squares Locations Programs Figure A board corresponding to a computer storage problem The rook polynomial is just the ordinary generating function for the sequence r B r B r B As with generating functions in general we shall nd methods for computing the rook polynomial without explicitly computing the coecients r k B and then we shall be able to compute these coecients from the polynomial To give some examples consider the two boards B and B of Figure In board B there is one way to place no rooks this will be the case for any board two ways to place one rook use either darkened square one way to place two rooks use both darkened squares and no way to place more than two rooks\n Thus RxB % x% x In board B there is again one way to place no rooks four ways to place one rook use any darkened square two ways to place two rooks use the diagonal squares or the nondiagonal squares and no way to place more than two rooks\n Thus RxB % \tx% x EXERCISES FOR SECTION For each of the following functions nd its Maclaurin expansion by computing the derivatives f k a cosx b e x c sinx d x ! \nx!