Generating Functions and Counting With Them - An Intro

okay in this video I want to talk about what are known as generating functions and you might run into these in a computer science class or a discrete math class and combinatoric Sande discrete math was always my favorite and I think these are kind of cool so put that aside let's let's just do some examples I want to just do some basic examples here about generating functions I'm just kind of an intro I'm going to set up a couple different examples and then in the next video we'll try to make things a little more formal we'll start talking about series and we'll get a little bit more in depth but just a little overview so you know if you consider the power the binomial 1 plus X raised to the n I assume you've seen this you end up picking up these binomial coefficients we've got you know n choose 0 and choose 1 etc and the thing that's interesting here is are the coefficients so what it says is it says if you have n objects and you want to pick R of those objects notice in front of the X to the R we get that binomial coefficient we get n choose R it's going to turn out that these coefficients in front of you know X to some power that's actually going to count the number of ways that certain things can be done and that's going to be the magic and with with these generating functions so I'm just going to run through a bunch of simple examples just to show you how to set them up and again how they work so let's start off with a real easy one so a girl can choose two items from a basket containing an apple and orange a pear a banana and my favorite a papaya we want to know how many ways can this be done well you might think we don't really need generating functions for that and I totally agree with you the simple answer the simple answer right is we're going to choose we've got five objects to choose from we've got an apple and orange of hair banana and a papaya we've got five objects to choose from we're going to choose two of those and remember to compute this this is five factorial over five minus 2 factorial which is three factorial multiplied by two factorial and if you compute that value you get exactly equal to ten so there's ten ways that she can do this but the way to think about approaching this problem with using what are known as generating functions and I'm not even going to make this generating function definition precise in this example what we'll see it in the next one so let's think about what she can really do okay so when she goes to pick things she can do one if for each item she can do one of two things so to start with she could choose zero apples so you could choose zero apples you can think about the and almost as being like or if you could choose zero apples or one Apple the way that we're going to rewrite this in terms of a polynomial for zero apples think about that as being X raised to the 0 so you can choose 0 apples or she can choose exactly one Apple now she can do this for each item she could also do it for an orange so I'm not going to write it down I'm going to maybe one more so she could pick 0 oranges or she could pick one orange and again the way that we're going to write that is we'll say well she can either pick 0 oranges or one orange and she could do this for each item so an or an apple and orange you can do the same things you can choose 0 pears or she can choose one pear she could choose 0 bananas or one banana she could choose 0 papayas or she could choose month of hyah and well X to the 0 that's just one so really we have 1 plus X raised to the power of well let's see we've got 1 2 3 4 5 of these we have 1 plus X raised to the fifth power and 1 plus X to the fifth power if you multiply that out we get 1 plus 5x plus ten times x squared plus 10 times X to the third plus five times X to the fourth plus X to the fifth so what we're looking at here you you're going to look at the exponent so again we're picking two items so that corresponds to the exponent we're going to pick two items the coefficient again tells us the number of ways that that can be done so it says oh there's ten ways that we can pick exactly two items from the total of five so again you're probably thinking hey this is overkill we don't need this and I would agree in this case but suppose we change it up a little bit you know and this is where the magic comes in so suppose in instead of a she's still going to pick two items but suppose instead of a containing just a single Apple a single orange a single payer a single banana and a single papaya suppose now that there are two apples and we consider these to be identical okay so this is where the distinction comes in if we didn't consider them to be identical we would just really be doing the same example as before but let's suppose we consider those apples to be identical how would that change things how many ways could she do this now well let's think about setting up our let's think about setting up our again our generating function so now for the number of apples the only thing that's going to change from our previous example so she could choose either zero apples or one Apple or two apples but for the remaining items again she could either choose you know what were they all the different ones she had oranges she could choose zero oranges or one orange she could choose zero payors or one pear she could choose zero papayas for one papaya so again think about each set of parentheses telling you the number of objects that she could select so this corresponds to the apples the oranges the pears and the papayas so again now our generating function for this example would be well we would have 1 plus X plus x squared then we've got 1 plus X to the third power and if you now multiply out this polynomial so I'll save you the gory details you get 1 plus 4x plus 7x squared plus 7x to the third plus 4 X to the fourth plus X to the fifth so again we're looking at the number of ways that she could pick exactly two items okay so I find that exponent of 2 it says oh there's seven ways that she could do this in this case there's now seven ways that she could do it and it makes sense intuitively right it should be a little bit different here than what we had previously so you notice we could actually you know just to convince you we could actually write it out so so number number of apples oranges pears papayas she could choose two apples no oranges no pears no papayas well she could choose exactly you know one apple and one orange she could choose one apple in one pair she could choose one apple and one papaya she could choose one orange and one pear she could choose one orange and one papaya or she could choose one pair and one papaya so zeros everywhere else in there and again if you count there's 1 2 3 4 5 6 7 ways that that can happen so again just to maybe convince you on a brute-force example now let's look here let's uh let's look at a couple more examples and then we'll in the next video like you said it will jump in to jump into making this a little more formal ok so suppose you go to the bakery just before it closes so they're running out of their stuff and they've only got three cheese pastries two cherry pastries and four raspberry pastries left we want to know how many ways could you choose exactly seven pastries well it's the same thing okay so the number let's think about the number of ways we can let's set up a polynomial for the number of ways we could pick the cheese pastries and I'm going to stop writing X to the zero I'm going to write that as one well what could you do you could pick X you could pick zero of the cheese pastries that again with correspond to X to the zero well we could pick one or we could pick two or we could pick three of those pastries for the cherry again we could choose zero or we could choose one or we could choose two and for the raspberry the same thing we could choose a we could choose none of those we could choose one we could choose two we could choose three or we could choose four so now this polynomial is going to be our generating function so again this corresponds to cherry and the last one corresponds to the what was the last one raspberry and if you multiply out this polynomial again if you multiply all of these terms together what you get is we have one plus three x plus six x squared plus nine x to the third plus 11 X to the fourth plus 11 X to the fifth plus nine x to the sixth plus six X to the seventh plus three X to the eighth plus X to the ninth so again we're interested in the number of ways that we could pick exactly seven pastries hey we just find that exponent of seven the coefficient on that is six it tells us that there are six ways that six different ways that we could choose exactly seven pace trees notice this function tells you a lot of other things too it says there's for example 11 ways that you could choose exactly 5 pastries there's also 11 ways you can choose exactly 4 pastries it's said so let's a I mean if you wanted to we can even write these down I think I have this again so so if we want exactly 7 we could have 3 2 & 2 that would be one way we could do it we could have 3 1 & 3 again accounting for the restrictions that we have we have 3 0 & 4 we could have 2 2 & 3 we could have 2 1 & 4 or we could have 1 2 & 4 so again notice that gives us 1 2 3 4 5 6 6 different ways which was the coefficient so again that's the magic the coefficient tells you the number of ways let's just make it one slight variation just to show you again how you can how you can easily modify these so suppose it's all the same but in this case suppose that the raspberry pastries only come in boxes of 2 so in that case you could either buy 0 raspberry - raspberry or 4 raspberry well how would that change the the generating function that you get well for the number of cheese it's still going to be the the polynomial that represents the cheese is still going to be the same that has changed there so you can choose 0 or 1 or 2 or 3 the same thing for the number of cherry that hasn't changed the way that we can pick those we can pick one excuse me we can pick 0 or 1 or 2 well now though the raspberry they come in pairs so we could choose 0 of them or we could choose 2 of them or we could choose 4 of them that's now going to be our generating function so again if you multiply out this this polynomial I probably should have already written these out but you get one plus two x plus four x squared plus five x to the third plus six x to the fourth plus six x to the fifth plus five X to the sixth plus four X to the seventh plus two X to the eighth plus X to the ninth so again we're looking for we're picking exactly seven so now it says there are exactly four ways to get exactly seven pastries under this new restriction and notice where did it go so notice if the raspberries have to be even let's see this column would work this column would work this column would work this column would also work which again tells us hey again there's one two three four ways of now we make that restriction that we have to choose an even number of raspberry pastries so okay so this is kind of the magic of these generating functions it's it's not that you know with combinations you have you know you're choosing R objects from n distinct objects but now we have sort of this amalgamation where you may have different objects but you may have you know different numbers you may have you know I bet within each of those distinguishable objects you have objects that are identical so this is kind of the power of these generating functions so we'll definitely look at in another video about making the stuff more formal the the the magic is going to be coming up with clever ways to compute coefficients and it's going to turn out that you can actually use series expansions to do this many cases where it'll actually be a bit easier so we'll talk about that and some next vid in the next video but hopefully this just gives you a little bit of an intuitive idea about how these generating functions work

Channel: patrickJMT

Views: 37,852

Keywords: generating, function, combination, permutation, discrete, math, computer science, free, tutorial, combinatorics, algorithm, complexity, count, counting, technique

Id: n9FFBXBccow

Length: 14min 59sec (899 seconds)

Published: Tue Dec 27 2016