Exponential Generating Functions Explained | Combinatorics Tutorial

[00:00:01]hi in today's video we'll be going through another type of generating function known as the exponential generating function in the previous video we are going through ordinary generating functions to help us solve distribution problem from identical to identical but it can also help us solve other Tau problem for explanation you can reading function it is useful when we want to count all the arrangement now like permutations and so unlike the ordinary generating functions they Define for the sequence of X squared x cubed the coefficients now are of the form of the power series A1 X over one factorial plus A2 x squared over 2 factorial and the reason it for that is because if all of these coefficients are one you get the e x e to the power x and that's why it's called exponential generating function we'll see later how we can be used to count order Arrangements but we'll continue now with some common EGF as I said if all of them are once it's just e to the power x now if your sequence of numbers is a permutation of the r terms then is zero factorial one factorial two factor or factorial then you just get back 1 plus X Plus x squared all the way one nine always infinity and that equals to 1 over 1 minus X likewise if it's 1 1K k k squared K to power r then there will be e to the ball KX and you can just write them down and you can see for yourself why now if we want to alternating sum with one one minus one one then it's just e to the power minus X if we want the even power terms only means we want to kill off we just take this e to the power minus X and we add that with the original so this minus X will cancel out with this plus X this minus X cubed over 3 factorial one cancels out with the plus X cubed over 3 factorial and then because all the even terms are repeated twice we divide by half likewise for the odd you just take e well x minus e to the power minus X and then you divide by 2.

[00:02:44]so this allows us to play around with the exponential generating functions and now let us see how we can model this explanation generating function before that let me also say one note is that any operations that we have already went through in the ordinary generating function such as when you multiply 1 minus X all this it is applicable to the exponential generating function because is applicable in a certain sense if you are able to change the division because if you know times x here will be x squared over one and that doesn't fulfill the condition that is over R factorial so the operations might not be always relevant but I hope you can play around with it to see what is needed for the problem so let's move on to examples one example and one use of explanation training function is like I said it deals with order arrangement and so we let our coefficient be the number of our permutation of identical objects now well what does that mean it means that how many permutations of an identical object can you have well there is obviously one you can only permute them one one way because like if you have if you have a a and a little number of two permutation is just choosing this is which doesn't matter so it's one way and then you permute them and because a and a bar muted is still one way times one so that's one so all the coefficients I want and that's why the generating function is in this form you might think this is a trivial case but we'll see why this case is applied on to later problems so this is the general version of what we have just said if we have identical objects that means repeated and we want to permute them then for the first repeated one it's just one plus x to the power over one factorial plus all the way to x to the power N1 over N1 factorial and then you should you could have chosen something from the other I didn't I love repeater object and move on well this key this example is actually releasing in the first few videos when I teach you permutation repetition because for the case of let's say we have Apple and we want to permute three of the letters then we can write them as the monkey set accordingly every ACP repeated twice so you want to permute two of them we actually have to take in we actually use the way to break down the cases and actually that is the only other way and so this way of using the explanation joining function is that so-called technically like modeling this repeated cases and you just need to solve for the coefficient accordingly and like I said in the previous video from combinatories sometimes we want to get back into algebraic expressions that we can manipulate the coefficients easier so that we do not always need to think of the algebraic problem the combinatorics problem and as we've seen in like video 4 if all these ends are in infinity then the number of permutation is just the first slot has K choices and the last half slot has K choices so it's K to the power r and that coincides with our EGF version as well next application is removing the distinct to distinct boxes but when we use permutations each of these distinct boxes has to be either less than the objects or equal to the object so that you have no empty boxes but with EGF it allows for empty boxes or not and the ordering within the boxes does not matter in this case that's why it's a distribution you distribute something when you don't care about the ordering and this problem is actually equivalent to having the number of R digits any sequences what does that mean it means you your R digit means you have a length let's say three digit then it's just length of three and binary means is zero one ten the standard one is a 10 tenery which means our 10 digits that we always use but it could be any sequence out of the boxes represent the digits because they are this thing so let's take a simple example where our EGF for this case one plus X over one factorial plus x square over two factorial to the power n this just means that we have our digit can repeat our n types of Digit carry B oh n times like Okay so let's uh repeat this one I said so imagine you have all digits now then you can repeat your entire digits infinitely many times so each type of Digit is one plus X Plus x square over two factorial plus all the way and you repeat this n times because you have different doubt you have n types of digit and because they can repeat that infinitely many times is essentially is about an X and so the coefficients end about R which is exactly the same because in our combinator is proof how do we want to do this is if we have r d g our first digit can end options and options all the way to the off DG so it's n Bar r you can take a look if no box is empty is you just omit the one here and it's just e x minus one to power M and it's actually just equivalent number of subjective mappings you can read more about that online and we'll move on to an example to further illustrate the use of exponential generating functions an example will be like earlier where now we want to just our a R is the number of R digit quantities so four digits if four types of digits so there's zero one two three and we have a r length digit number and then because if we put in conditions such appears at least the digit second two and three appears at least once it makes it very hard to do a combinatorics proof because there are many cases to consider such as like or two appear and then because it's all digits it's quite arbitrary but with explanations simplify this to an algebraic expansion which is easier because now for the one and zero digit you can choose them you have two you can do them in one plus x x squared all the way infinitely number of times and then because it is zero and one there's two of them so it's two power two for the second and third because now it appears at least once you cannot have the option where you choose none of them so one is disregarded and so is X Plus x square over two factorial all the way then there's power x squared bracket e x minus 1 squared and when you expand out it's just e 4X minus two e three X Plus e to the power 2X and each of these can be written as a power series that we have seen and so when you simplify the power Series this will be the coefficient of AR or x to the power out over R factorial and this represents your AR and so you can easily get a closed formula for this problem now I'll do one example with you so let's see we want to distribute the number of all distinct objects into four distinct boxes as we have said earlier it is equivalent to creating the number of r d g energy sequence so it means we want to distribute all distinct objects means R digit quaternary because there's four so is zero one two or three Dot the digits representing the different boxes so box one must hold even number of objects so let's just say this is box one is for first digit one and like I say even power is this minus x divided by two so like is E X Plus e minus x divided by 2 and then Box 2 must also hold even number so that's Square but they say box 3 must go odd number so that the digit three whole odd number and lastly the zeroth digit can hold any number so let's eat about X and if you expand out this is just one quarter bracket e 2x plus 2 plus e minus 2X bracket e 2x minus E minus 2X times half so you can remove this 1 8 then this will be e4x Plus 2 e 2 X Plus 1 minus 1 minus 2 e minus 2X minus E minus 4X and so if you simplify this expression over here it will be one over eight bracket e to the power 4 x plus 2 e 2 x minus two e minus two x minus e to the power minus 4X and then we just use the power series formula this is this e to the power 4 x will become 4 to the power r Plus two times two to the power r minus two times two minus two to the power r minus minus fourth power off so this gives us a formula for us to solve for this expression includes form and so the number of ways will just be one over eight for the power r Plus 2 R plus 1 minus plus 2 2 Plus minus 2 r plus one minus minus 4 the power r and you can see how we have used explanation trending function to make our conditions easier to visualize and solve and soon you can use explanation training function to model other arrangements and I've hoped you have enjoyed this video because I've come to the end of it thank you for listening and feel free to Explore More by yourself please like share and subscribe and this series will be coming to an end for counting thank you