Generating Functions in Combinatorics: Discrete Math Lecture 30

[00:00:00][Music] [Music] oh oh sh sh sh [Music] me in the last two lectures we saw about permutations and combinations PNR denotes the number of permutations of R objects out of n objects and CNR denotes the number of combinations of R objects out of n objects and we have seen some results about this where repetitions are allowed and where different types of arrangements are considered and so on we also saw that how to distribute distinct and non-distinct objects into distinct cells and what is the connection between them and permutations and combinations and today we shall look at the same thing combinations and permutations but from a different point of view making use of a tool called generating functions here also we'll see about combinations and permutation but we are going to get the answers or the formula using some other method the concept of a generating function so what is a generating we shall generating function we shall see two types of uh generating functions the ordinary enumerator and also the exponential enumerator now from three distinct objects a b and c there are three ways to choose one object namely to choose either a or b or c let us represent these possible choices symbolically as a + B+ C so if you have three objects a b c and you want to select one of them you can choose a or you can choose b or you can choose C that you can represent as a b A+ B+ a r b r c similarly from these three objects there are three ways to choose two objects namely you can choose either a and b or B and C or C and A and this can be represented symbolically as a B A and B B and C C and a a and b r b and c r c and a and if you want to choose all the three objects then there's only way of doing it and that can be symbolically represented as a c now if you look at this polinomial 1 into 1 + a x X into 1 + BX into 1 + c x this formula form formula if you expand this this is equal to 1 + A + B + c x a b + B C + C A X2 a b c x cub and so now the coefficient of x power 1 x is x^ 1 represents the number of or the the possible ways of choosing one object the coefficient of x² is A + B C + C A and that represents the N the possible ways of choosing two objects out of the three objects that is a b b c or C A the coefficient of x Cube represents the possible way of choosing all the three objects a c that is ABC now we discover that all these possible ways of selection are exhibited as the coefficients of the powers of X now how do you interpret this the factor 1 + a x it means that for the object a the there are two ways of selection one is not to select a that is one way of doing it and another one is to select a so that is represented as one means not selecting a the other is selecting a a x so it is represented like this now if you look at the left hand side of that equation previous equation this portion this is the product like this this means that for the object a b and c the ways of selection are to select or not to select a that is represented by this factor and you can select or not select B and that is represented by this Factor you can repres select or not select C and that is represented like this right so together this gives you the number of ways of selecting one object or two objects or three objects out of the three objects a b c and that the coefficient of x power r on the right hand side gives you the possible ways of selecting R objects out of these three objects in general you can see that if you have a sequence a not A1 A2 a r be the symbolic representation of a sequence of events or let it be simply a sequence of numbers then the function FX is equal to a mux A1 mu1 X A2 mu2 X Etc a r mux is called the odd orary generating function of the sequence a A1 A2 a r where mu x mu1 x mu 2x mu RX is a sequence of functions of X that are used as indicators this is the sequence a not A1 A2 a r this is the sequence and you are using the indicator functions this mux mu1 x mu2 x are called indic indicator functions using these sequence of functions as indicator functions if you represent FX like this that is called the ordinary generating function of the sequence a mu X A1 mu1 X and so on if you look back you see here the sequence is 1 A + B + C AB b c c a Ab plus b c plus c a and a b c and if if you use 1 x x² X Cub Etc as ordinary as indicator functions this is the ordinary generating function if you for example using if you use as indicator functions 1 cos x cos 2x Etc as the indicator functions then the ordinary generating function of the sequence 1 Omega Omega s Omega Cub Etc is given by this expression f of x is equal to 1 plus of course here the function is 1 then Omega second here you have cos x cos x then you have omega squ third here is cos 2x so you have cos 2x here and so on so for Omega R you we will have cos R of X so the expression is 1 + Omega cos x Omega 2 cos 2x Etc Omega power R cos RX this is the ordinary generating function for the sequence 1 Omega Omega s Etc using the sequence 1 cos x cos 2x cos RX as indicator functions now the indic functions you can choose in any way but you have to choose them in a proper manner that a particular sequence can be represented in a unique manner or one uh expression one expression uniquely represents one particular sequence two sequences should not give rise to the same expression or the function let us see using one one + x 1 - x 1 + x 2 1 - x 2 Etc as indicator functions supp 1 + x^ r 1 - x^ r as the indicator functions and suppose you take this sequence 3 2 6 0 0 as a sequence what will be the ordinary generating function 3 into 1 2 into 1 + x 6 into 1 - x 0 into 1 + x^ 2 0 into 1 - x 2 that is 3 into 3 + 2 into 1 + x + 6 into 1 - x if you simplify this will reduce to 3 + 2 + 6 11 2x - 6X will give you - 4x so the ordinary generating function becomes equal to 11 - 4x for this particular sequence using these as indicator functions now this expression it should not represent another sequence for the same set of indicator functions in that case it's not advisable to use them as indicator functions look at this sequence 1 370 0 and 1 12611 with the same set of indicator functions what will you get what will you get as the generating function 1 into 1 then 3 into 1 + x 7 into 1 - x 0 into 1 + x^ 2 0 into 1 - x² and so on let us see what you will get here 1 + 3 into 1 + x + 7 into 1 - x this will reduce to 1 + 3 + 7 11 3x - 7 x will give you - 4x the same 11 - 4x you are getting and it is representing this particular sequence as well as this sequence it also represents another sequence see suppose you take the sequence as 1 2 6 1 1 let us see what is the ordinary generating function for the same set of indicator functions you have 1 into 1 2 into 1 + x 6 into 1 - x 1 into 1 + X2 1 into 1 - X2 if you simplify this you realize that you get 1 + 2 + 6 + 1 + 1 will give you 11 this x² will cancel with this x² and as far as the coefficient of x is concerned you have 2x - 6X which will give you - 4x so again you see that you are getting the same ordinary generating function and it is representing three sequences which is not correct so these functions you cannot use as indicat functions the indicator functions should be such that for each sequence the expression you get is unique or each expression uniquely represents a sequence now the easy way out is you choose 1 x x² X cubed x power 4 x^ R Etc that is this sequence is taken as the set of indicator functions in that case the coefficient of x^ R gives you the value a r the r uh element in the sequence which you want to represent and there's only one way of doing it so there is no problem so usually One X x² X Cub Etc they are taken as indicator functions so we shall restrict our consideration to only those sequences now let us see how the generating function can represent a combination we have earlier seen 1 + a x into 1+ b x into 1 plus a x how it represents the the way of choosing a not choosing a choosing B not choosing B choosing c not choosing C Etc now put a equal to B is equal 1 in that expression then you will get 1 + x into 1 + x into 1 + x that is 1 + x Cub = to 1 + 3x + 3x2 + XB what is this three this the coefficient represent the number of ways of not choosing any objects out of three objects this gives you the number of ways of choosing one object out of three objects this gives you the number of ways of choosing two objects out of three objects and the coefficient of this gives you the way of choosing all the three objects so the coefficient of x^ R gives you the number of ways of choosing R objects out of n objects in general if you generalize this to find the number of combinations of a distinct object we have the ordinary enumerator ordinary generating functions this is a binomial function binomial expression 1 + x^ n is 1 + n x + n into N - 1 by 2 factorial x² Etc or you can represent this as c n not C N1 X plus C N2 x^2 and so on the coefficient of x^ 0 or the constant term here is the number of ways of choosing no objects out of n object the coefficient of x^ 1 or X is given by this this is the number of ways of choosing one object out of an object the coefficient of x² gives you the number of ways of choosing two objects out of n objects and the coefficient of x^ R gives you the number of ways of choosing R objects out of n objects of course the last term the way number of ways of choosing all the N objects out of an object is one CNN is one that we know in the expansion of one plus x^ n the coefficient of the term x^ R is the number of way of the term term x^ R can be formed by taking rx's and N minus r1's among the N factors 1 + x so that is you're selecting R object and leaving out n minor R objects out of n objects so using this generating function concept you can you can prove certain identities for example you have this this is the expression we have earlier seen instead of writing CNR we are writing it as n this also represents the number of ways of choosing R objects out of n objects so CNR can also be written in this form that is what we are making use of here for simp for uh Simplicity now from n this is the binomial expansion cn0 cn1 X Plus cn2 x² Etc is equal to 1 + x^ n now in this equation you put X is equal to 1 if you put X is equal to 1 here this becomes 2^ n and here if you put X in every place you get this the left hand side becomes this what is this this is the number of ways of choosing zero objects or one objects or two objects or three objects or n objects out of n objects this is the number of a of choosing zero objects this is the number of a of choosing one objects number of a of choosing two objects and so on you can very easily see that from a combinatorial point of view you have n objects for each object you have two possibilities either you can select or not select so if you uh for n objects there will be 2 power n possibilities each object you have two possibilities for n objects the possibilities will be 2 power n that is what you get on the right hand side so the number of ways of choosing zero objects one object two objects or n objects out of n objects that is the left hand side is seen to be equal to 2^ n so from combinatorial point of view are also we are able to see this and we can get this from the binomial expression also using the idea of generating function so this is what we have seen by setting X is equal to 1 we got that setting X is equal to minus1 in the previous one this will become zero and Alternate terms will become negative this will be negative this this will be positive this will be negative and so on so you will get n0 - N1 + N2 - 1^ r n r - 1^ n NN is equal to 0 right hand side will become zero so if you take all the negative terms to the right hand side this will be n0 N2 N4 and N1 N3 N5 C n0 CN 2 cn4 Etc what does the left hand side represent the left hand side represents the number of B of selecting zero objects out of n objects or two objects out of n objects or four objects out of n objects and so on what does the right hand side represent it represents the number of ways of selecting one object out of an object three objects out of n objects five objects out of n objects so the left hand side represents the number of ways of selecting an even number of objects from n objects the right hand side represents the number of ways of selecting an odd number of objects from from n objects we see that the number of ways of selecting an even number of objects is equal to the number of way of selecting an odd number of objects when in distinct object left hand side is equal to the right hand side so the number of ways of selecting an even number of objects from n object is equal to the number number of ways of selecting an odd number of objects from n objects this also you are able to uh get from the generating function idea now look at this this is an identity how can you prove this identity cn0 squ N1 s N2 squ Etc cn2 s CN not 2 Etc is equal to C 2nn this can be proved in two ways let us see how we can prove this look at the ordinary enumerator 1 + x^ n that is n0 + N1 x + N2 x² plus NN X power n look at 1 + 1 by x^ n that is equal to n0 + N1 into 1 by X Plus Etc + NN to X power n I'm sorry this is 1 by x 1 by X power now if you multiply is two you consider 1 + x^ n into 1 + 1 by x^ n that will be you have to multiply this whole thing by this now what is the coefficient of x^ 0 or the constant term here right hand side will be some expression okay what is the coefficient of x^ 0 or the constant term Co efficient of constant term this and this will give you a constant term that is n 0 the whole s and this when you multiply with this will give you a constant term that is n 1 the whole s this and the coefficient of 1 by x² will give you the account constant term so that is n 2 squ and so on and lastly when you multiply this by this you get a constant term and that is n n thus you get the left hand side of the expression which we want to prove so we want to prove this that is this is equal to this so by considering this and this and multiplying out you get the coefficient of x^ 0 or the constant term as this which is the left hand side now how do you get the right right hand side you have 1 + x power n this is what you're are considering right 1 + x to the^ of n now this one you can write as 1 + x^ n this x if you take it is X + 1^ n by x^ n or x^ - n this is 1 + x^ 2 N in this expression if you take the coeffient of x^ n when you multiply it by x^ minus n you get a constant ter so what is the coeffient of X power n in 1 + x^ 2 N that is 2 n n right the coecient of X power in this is 2 n^ N when you multiply this by X power minus n you get the constant term so if you look at it in a different way the constant term the co constant term here is 2N or I instead of saying coefficient of the constant term I could have said constant term itself the constant term is this and the con constant term constant term so it becomes equal to 2 N N so you find that you look at it in two different ways the expression 1 + x to the^ of n into 1 + 1 by x^ of n then in one way you get the left hand side in another way you get the right hand side are equal this is one way of looking at it you can also prove it by combinatorial argument now the left hand side is n0 whole squ but you know that NCR NC R is equal to NC n minus r this you know the number of face of choosing R objects out of n n objects is the number of a of leaving out n minus r objects out of n object so this identity we know so making use of that the left hand side left hand side will be equal to n0 and NN plus N1 n n minus1 and so on plus NN n z by a combinatorial argument what does this represent you have two n objects and you separate them into two sets of n objects now I want to choose n objects out of two n objects I can choose Zero from here and N from here which is given by this expression or I can choose one from this set and N minus one from this set and that is given by this I can choose two from this set and n minus 2 from this that will be this the next term and the last I can choose all the N from this and zero from the second set so that is given by this so in essence it amounts to the number of ways of choosing n objects out of 2 N objects and we know that that is given by 2 n n so by a combinatorial argument also you can prove this in equal equality now let us consider a small problem what is the coeffient of the term x^ 23 in 1 + x^ 5 + x^ 9 to the^ of 100 you have 1 + x^ 5 + x^ 9 the^ of 100 you want want to find the coefficient of x^ 23 how can you find this out now how can you get 23 by having fives 9es and ones there's only when one way of doing it you can have 5 + 9 + 9 this will give you 23 otherwise if you have four files then you'll have three which is not possible if you have two fives then also you'll be left with 19 which you cannot account for three fives then you will be left with 8 which is not accountable so there is only when one way of splitting 23 into FES and 9es and that can be done only in one B so if you have 100 factors like this out of the 100 factors you have to select two factors are x^ 9 from two factors and x^ 5 from one factor then only you'll get x^ 23 so you have to select x^ 9 from two factors out of 100 and you have to select x^ 5 from x^ 5 from one factor that is out of 100 out of the remaining 98 so it will be C 1002 from two factors you are selecting X power 9 after doing that you'll be left out with 98 factors out of from which you have to to Select 1 x^ 5 that can be done in C 98 comma 1 from the rest of the factors you have to select only one so this will give you the answer 100 into 99 by 2 into 98 you can simplify multiply and get the answer for the expression this is the number of ways of this is the Coe Co coefficient of x^ 23 in this expression when you allow repetitions what happens you are having three objects a b c but you allow repetition now for a you can choose it two times either once or twice you can choose and B and C you can choose only once in in that case how does the expression become or how does the generating function look like when repetitions are allowed in the selections are equivalently when there is more than one object of the same kind or you can look at it like this you are having two red balls two one blue ball one green ball and then from which you have to select uh 1 2 3 balls or so on the extension is immediate you can look at it like this 1 + a x + a 2 X2 that is the object a can be need not be selected or it can be selected once or it can be selected twice the object B can be not selected or selected ones the object C can be not selected or selected ones now you if you expand this you get this which means if you want to select one object out of the three objects where a can be selected twice see when you select only once it doesn't matter whether you a you can select twice or the coefficient becomes only a plus b the coefficient of x tells you the number of way of selecting one object out of three objects a b c where you allow a to be selected twice but when you look at the co of X squ then possibilities are like this either you can choose a and b or you can choose B and C or you can choose a and C or you can select a twice so a a squ also is in this term similarly when you want to select three objects ofed twice is you can select a b c or you can choose a squ twice and B once or a square twice and C once and if you want to select four of them a has to be to be selected twice B and C also have to be selected so this is the ordinary generating function for the combinations of the object a b c where a can be selected twice or you are allowing a to be selected twice you must note the difference between this and the polinomial 1 + a x into 1 + a see we have considered like this 1 + a x + a 2 X2 for the selection of a it is not the same as 1 + a x into 1 + a² CX because in this case the expression will become like this this is different here you are allowing a to be selected once twice Thrice and so on so that is not the same uh thing so if you look at this expression 1 + a x into to 1 + a 2 x to 1 + b x and 1 + c x Etc if you expand it will be like this what does this represent it represents the following thing you can imagine that there are four boxes one containing a one containing two A's one containing B and one containing C the generating function gives the out outcomes of the selection of these boxes so you are having four boxes this box contains one a this box contains 2 A's this box contains B this box contains if you select one of them what will be the outcome it could be a or it could be B it could be C or it could be a squ if you select two boxes then if you choose the Box containing A and B you'll get a B you choose the Box containing B and C you'll get this you choose the Box containing a and see you'll get this but if you choose the Box containing a squ one another box you can choose so a squ and a will give you a cub A squ and B will give you a squ b a squ and c will give you this similarly for the coefficient of x cub and x^ 4 so this represents that there are four boxes one containing a one containing two A's one containing B and one containing C and this generating functions gives the outcomes of of the selection of the boxes when you select one box what happens when you select two boxes what are the things inside that and so on this is different from what we considered earlier this one where you have three objects a b c where one object is allowed to be selected more than once that is a is allowed to be selected twice now instead of putting a BC if you put the them as one so the ordinary enumerator for the combination of the objects a b c where a can be selected twice is given by this instead of a and all we have just considering the number of a only so it is 1 + x + x 2 into 1 + x into 1 + x for B it is 1 + x for C it is 1 + x for a it is 1 + x + x² if you expand this you'll get this so the number of ways of choosing one object out of three objects a b c where a you can select twice is three so if you have three objects a b c the number of ways of selecting one of them is you can choose a you can choose B them is you can choose a b that is one you can choose BC that is one you can choose C A that is one a can be selected twice if it is selected twice that gives you one so totally it is four and that four repr represents that the coefficient of x² represent like like this like this you get the coefficient of x cubed and x^ 4 also the significance of the factor 1 + x + x² is that the object a there is one way not to select it one way to select it once and there is one way to select it twice that is what is meant by this expression 1 + x + x² given two each of P kinds of objects and one each of Q additional kinds of object in how many ways can our objects be selected this is the problem let us see how we tackle that so you have P objects they can be selected twice given two each of P kinds of objects so if you take one of them you can select it once or you can select it to twice okay this is the enumerator for the P kinds of objects and you are having Q additional kinds of objects each you have only one of them so either you can choose them or not choose them so this is the enumerator for the expression and generally see first object you are having two of them second object you are having two of them like that p p of them then Q of them you having only one okay so the first object you can select once you you need not select or you can select only one of them or you can select two of them like that for all the P objects so the enumerator for that is this ordinary enumerator then the remaining Q objects you're having only one of them so either you can select it or not select it select it or not select it and totally you are expected to select R objects out of the p+ Q out of the actually 2 p+ uh Q objects in that case what is the uh number this is you have to find the the answer is the coefficient of x^ R in this in this expression now what is the coefficient of x^ R in this now you can select X squ it X squ it then that will give you a power of 2 I then there will be how many factors remain here there will be P minus I factors remaining here and already there are Q factors out of these factors and these factors you have to select the remaining coefficient x^ R this the remaining coefficient you have to choose so the idea is if you say uh it is sigma I is = 1 to R by 2 from this V factors you have to select so p i and from the remaining P minus I + Q factors that is p + Q - I factors you have to select and this R if it is even this is okay otherwise you have to select the integral part of that this will give you the answer what does that mean it means that suppose R is 13 13 means you cannot select uh x² 13 by 2 is 6.5 you cannot select 6 and a half times this so you have to select 6 * x² maximum you can select this uh six times and one you have to choose from here so from I is equal to I * your I factors you are selecting here and that will account for 2^ I the rest of them you have to select from the p + Q minus I factors so this will give you the answer for this problem now the ordinary enumerator for the selection of R objects out of n objects where R is greater than or equal to n with unlimited repetitions but with each object included in each selection is this now before that uh each object is not need not be incl included so you are selecting R objects out of n objects what is the expression for this this we know is c n + r -1 by so we are selecting R objects out of n repetition and the expression for that is c n + r minus 1 r r c n + r both are equal how do you get this see you get 1 + x + x² Etc for one object it can be selected one not it need not be selected at all or once or for one object the enumerator is this for n objects the enumerator is this and this is nothing but 1 by 1 - x^ n r = 1 - x^ of - n the binomial expansion this will expand as 1 + NX + n into n + 1 by 2 factorial X2 and so on the coefficient of x^ R be n into n + 1 Etc n + r -1 by R factorial x^ r + Etc if you expand using binomial theorem this will be the expression now the coefficient of x^ R will give you the number of ways of selecting R objects out of n objects with unlimited expression and this is this expression and this is nothing but this okay this we have earlier seen by different arguments now if you have to select each one of the N object at least once then what is the expression we'll consider that the ordinary enumerator for the selection of R objects out of n objects now R has to be greater than r equal to n because each one of them you're selecting at least once with unlimited repetitions but with each object is included in each selection that is given by this expression x + x² + x^ 4 Etc to the power of n for each object the possibility is it can be selected once twice Etc please note that the possibility the constant term plus one which was there in the earlier case is not here because you have to select each object at least once so the ordinary enumerator is given by this expression and if you take out the x^ n this is equal to x^ n into 1 by 1 - x^ n to the^ of - n and this expression if you simplify this if you expand this portion and simplify x^ n is like this this the expression for 1 - x power minus n using binomial expression is Sigma i = 0 to Infinity n + i - 1 I that is c n + i - 1 I x^ I this is the way you expand this 1 - x to the^ of - n so this will be Sigma I is equal to 0 to Infinity n + i - 1 1 C that is is a combination c n + i - 1 I x^ n + I now put in X+ I with unlimited repetition where each object is selected at least once so if you put n + I is equal to R this the previous equation becomes here it becomes R but I will be now from so instead of saying I is equal to 0 to Infinity you can say R is equal to 0 to R is equal to n to Infinity so this is X power R then instead of saying I is equal to 0 to Infinity now it will be R is equal to n to Infinity so the expression for that is R -1 r n r - n n + I is R so it will be r - 1 i r is equal to n + I so I will be R minus n so this is rewriting that previous expression it will be equal to c r -1 r - n x^ R where the summation ranges from R is equal to Infinity now the coefficient of x^ R which is R -1 r- n you can also rewrite this in this way because c n r is equal to c n n minus r you can rewrite this expression like this the coefficient gives you the number of ways of selecting R objects out of n objects where each object is selected at least once we have seen this expression also in the case of Distributing R objects into IND distinct cells very each cell should contain at least one object and so on let as an application let us see a simple problem what is the number of ways in which four persons each rolling a single D once can have a total of 17 you are having four people each person is rolling a die and the outcome of each D will be between one and six and what what are the number of ways we can have a total of 17 from that so for for one person it could be 1 or 2 or three or four or five or six so the outcome can be like this so you are having four persons so ordinary enumerator for that will be x + x² + x + x^ 4 + x^ 6 the^ of 4 and you have to find the coefficient of x^ 17 in this so we have to find the coefficient of x^ 17 in x + x² + x^ 6^ 4 so this we can write as x^ 4 into 1 + x + x² + x power 5 + power of 4 and this is a geometric Series so this you can write as x 1 the^ of 4 so in essence you have to find you have to find the coefficient of x^ 13 CU four you are accounting for here in 1 - 6^ of 4 to 1 - x^ of - 4 let us see what is that coefficient 1 - x^ 6^ of 4 is 1 - 4 x^ 6 + 6 x^ 12 - x and 1 - x power - 4 is 1 + 4x + 4 into 5 by 2 factorial x^ 2 + 4 into 5 into 6 by 3 factorial X Cub X so in the product we have to find the coefficient of x^ 13 how can you get x^ 13 you can multiply this by x^ 13 here the term consisting of x 13 here and you can multiply this by the term having x^ 7 here and you can multiply this term by this term so in three ways we can get x^ 13 so let us add those coefficients so if you multiply this 1 by the coefficient of x^ 13 here what will be the coefficient of x^ 13 in this expansion that will be 4 into 5 into 6 up to 16 by 13 factorial CU you are considering the coefficient of x^ 13 then minus the product of this term with the coefficient of x^ 7 here x^ 6 and x^ 7 will give you x^ 13 so that is 4 * 4 into 5 into 6 up to 10 by 7 factorial then if you multiply x^ 12 by X you get x^ 13 so these two will give rise to another x^ 13 that is 4 into 6 so if you simplify this you can multiply by and divide by 1 into 2 into 3 4 into up to 16 by 13 factorial minus 4 * 1 into 2 into 3 by 1 into 2 into 3 up to 10 by 7 factorial + 24 and this will be 14 into 15 into 16 by 6 13 factorial will cancel off here again up to 7 you can cancel off so this will give rise to 4 into 8 into 9 into 10 by 6 + 2 4 and this is 7 3 5 35 into 16 35 into 16 minus this is 4 48 into 10 + 24 and this will be write it here 16 into 5 80 48 560 - 480 + 24 is 80 + 24 104 so there are 104 ways in which you can get 17 by Rolling four dice so we have considered some examples here and we have seen how the concept of a generating function an ordinary enumerator can be used to solve some problems in combinations the number of ways of selecting but when we consider the number of ways of permutations or Arrangement there is a slight problem the very big advantage in using an ordinary enumerator is that the binomial coefficients CNR they give you the number of ways of selecting R objects out of objects so you have a very simple closed form expression whereas the same will not be true in the case of permutations so in the case of permutations what sort of an enumerator we should have so that we get a decent closed form expression so in the next lecture we will consider generating functions for expressing the permutations number of ways you can permute R objects out of n objects [Music] t the e