1 00:00:03,740 --> 00:00:06,828 Today we're going to talk about generating functions. 2 00:00:06,828 --> 00:00:11,709 As you'll see, generating functions are the central object of study in Analytic 3 00:00:11,709 --> 00:00:15,107 combinatorics. But they also have rich history and many 4 00:00:15,107 --> 00:00:20,049 uses and we'll show first how they are used for solving recurrence relations, 5 00:00:20,049 --> 00:00:23,323 and then ease into their use in more general context. 6 00:00:23,323 --> 00:00:27,895 So, to start off, we're going to talk about just what is a generating function. 7 00:00:27,895 --> 00:00:32,528 In this, the fist thing we'll talk about is what is called ordinary generating 8 00:00:32,528 --> 00:00:35,308 functions. So, there's a definition of what is 9 00:00:35,308 --> 00:00:41,970 ordinary generating function? it's a function that's defined as an infinite 10 00:00:41,970 --> 00:00:48,331 sum, involving a free variable, Z in this case over a sequence. 11 00:00:48,331 --> 00:00:54,580 So given a sequence A0, A1, infinite sequence like the types we were working 12 00:00:54,580 --> 00:01:01,324 with recurrences the ordinary generating function of that sequence is obtained by 13 00:01:01,324 --> 00:01:06,640 multiplying the Kth term by Z to the K and then summing over old K. 14 00:01:06,640 --> 00:01:13,092 We also use the notation that inside brackets Z to the N of A of Z, is the 15 00:01:13,092 --> 00:01:18,529 coefficient of Z to the N in A of Z. and a lot of times we want to refer to 16 00:01:18,529 --> 00:01:23,036 what the coefficient is. and we'll see how it, it applies, but 17 00:01:23,036 --> 00:01:28,830 let's just talk formally about some examples of generating functions first. 18 00:01:28,830 --> 00:01:34,267 So for example, if the sequence is all ones, then the generating function for 19 00:01:34,267 --> 00:01:41,206 that sequence is the sum N greater to 0 Z to the N, which is geometric sum 1 / 1 - 20 00:01:41,206 --> 00:01:45,846 Z. or if you have one 1/2. 1/6. 1/24, the 21 00:01:45,846 --> 00:01:51,788 sequence is one over n factorial. The generating function of that sequence 22 00:01:51,788 --> 00:01:57,570 is sum n bigger than zero, z to the n over n factorial, that's e to the z. 23 00:01:57,570 --> 00:02:00,905 So that's examples of generating functions. 24 00:02:00,905 --> 00:02:06,850 And we'd say the coefficient of Z to the N and E to the Z is one over N factorial. 25 00:02:06,850 --> 00:02:13,163 so that's ordinary generating functions. now the significance of defining a 26 00:02:13,163 --> 00:02:19,101 generating function is that it allows us to represent an entire infinite sequence 27 00:02:19,101 --> 00:02:23,491 with a single function. rather than carrying around the infinite 28 00:02:23,491 --> 00:02:27,424 sequence, 1/n factorial, we just work with the single function, e of z. 29 00:02:27,424 --> 00:02:32,506 And that turns out to have all kinds of benefits when we're doing analysis of 30 00:02:32,506 --> 00:02:36,378 algorithms, and studying properties of combinatorial structures. 31 00:02:36,378 --> 00:02:41,036 But before getting into the applications, let's look again at some more basic 32 00:02:41,036 --> 00:02:46,299 operations on generating functions that we'll use in order to be able to, we need 33 00:02:46,299 --> 00:02:50,111 to be able to find the generating function of a given sequence. 34 00:02:50,111 --> 00:02:54,285 And we need to be able to see the sequence back, given the generating 35 00:02:54,285 --> 00:02:57,611 function. Then we use some relatively simple 36 00:02:57,611 --> 00:03:02,186 operations to get these jobs done. So for example, here's the scaling 37 00:03:02,186 --> 00:03:04,701 operation. If you have a of z, tis is just 38 00:03:05,840 --> 00:03:13,806 generating function for some sequence, if you multiply the argument by a constant 39 00:03:13,806 --> 00:03:17,884 c. So, just evaluate a of CZ then just do 40 00:03:17,884 --> 00:03:22,532 the math. That's the sum of c, c to the k, z to the 41 00:03:22,532 --> 00:03:26,325 k. That's the generating function of the 42 00:03:26,325 --> 00:03:30,308 sequence a0, ca1, c^2 a2, c^3 a3, and so forth. 43 00:03:30,308 --> 00:03:36,380 and that's just, from, from the math. CKZK is the 44 00:03:36,380 --> 00:03:39,596 Is the generated function of that sequence. 45 00:03:39,596 --> 00:03:44,839 So here for example, if you have the sequence that's all ones, where it's, 46 00:03:44,839 --> 00:03:49,664 ogf1 over one minus z. then one over one minus 2z is the sum of 47 00:03:49,664 --> 00:03:54,907 two to the n, z to the n, which is the generating function for the powers of 48 00:03:54,907 --> 00:03:56,515 twos. So that's scaling. 49 00:03:56,515 --> 00:04:02,388 So that's an easy way to get generating functions for different sequences out of 50 00:04:02,388 --> 00:04:06,513 a known sequence. and again, we'd say coefficient of z to 51 00:04:06,513 --> 00:04:09,660 the n and 1over one minus 2z is two to the n. 52 00:04:09,660 --> 00:04:15,091 So that's scaling. let's look at another example, addition. 53 00:04:15,091 --> 00:04:18,580 That's an easy operation in generating functions. 54 00:04:18,580 --> 00:04:24,206 If you have two generating functions on two different sequence, then the sum of 55 00:04:24,206 --> 00:04:30,188 the generating functions is the the OGF of the term by term sum of the sequences. 56 00:04:30,188 --> 00:04:36,384 So, for example, these two generating functions that we've developed here if we 57 00:04:36,384 --> 00:04:40,799 subtract the say we subtract the first one from the second, 58 00:04:40,799 --> 00:04:43,007 1u200bz-u200b1/u200b1-u200bz over, 1 - 2Z - 1 / 1 - Z that's the generating 59 00:04:43,007 --> 00:04:48,141 function for powers of 2-1. so with each one of these operations we 60 00:04:48,141 --> 00:04:53,069 enrich the set of sequences that we know generating functions for. 61 00:04:53,069 --> 00:04:59,492 differentiation that's another thing, if we have a generating function A of Z = A 62 00:04:59,492 --> 00:05:05,360 K Z to the K, if we differentiate that. That's Z a prime of Z. 63 00:05:05,360 --> 00:05:10,129 This KAKZ to the K. that's the generating function of this 64 00:05:10,129 --> 00:05:15,896 sequence A1, 2A2, 3A3, and so forth. so, then that's a useful operation, that 65 00:05:15,896 --> 00:05:20,782 we can use again to get, generate functions for more sequences. So for 66 00:05:20,782 --> 00:05:26,164 example with our simple geometric sum for the sequence that's all 1s and 67 00:05:26,164 --> 00:05:30,428 differentiate that. Differentiate the left side it's Z over 68 00:05:30,428 --> 00:05:34,637 one minus Z squared. and the right side tells us that's the 69 00:05:34,637 --> 00:05:37,623 generating function for the natural numbers. 70 00:05:37,623 --> 00:05:42,714 Sequence 0, 1, 2, 3, 4, 5. We can do that again, we can continue 71 00:05:42,714 --> 00:05:46,108 differentiating and get a richer set of functions. 72 00:05:46,108 --> 00:05:49,910 So differentiate again, it's Z squared over one minus ZQ. 73 00:05:49,910 --> 00:05:55,728 and that's the generating function for the binomial coefficients, N choos 2 74 00:05:55,728 --> 00:06:01,967 [COUGH], or N times N - 1 / 2. and actually we can get a generating function 75 00:06:01,967 --> 00:06:07,646 for binomial coefficients on the lower index, by differentiating, N times, in 76 00:06:07,646 --> 00:06:13,534 this way, and you can, check that out. The generating function for N choose M, 77 00:06:13,534 --> 00:06:16,970 is Z to the M, over one minus Z to the M plus one. 78 00:06:16,970 --> 00:06:23,305 and as we saw special number sequences like the binomial coefficients arise when 79 00:06:23,305 --> 00:06:27,452 we're studying algorithms and combinatorial structures. 80 00:06:27,452 --> 00:06:33,712 so with generating functions we can work with all these kinds of sequences with 81 00:06:33,712 --> 00:06:41,567 just one function. so [COUGH] oh, and this is just dividing 82 00:06:41,567 --> 00:06:46,619 by, dividing out z to the n, we get a slightly different look at that same 83 00:06:46,619 --> 00:06:50,940 generating function. and we'll have use for applying all of 84 00:06:50,940 --> 00:06:54,730 these equations which are in tables in the book later on. 85 00:06:54,730 --> 00:06:57,716 okay, we can go the other way and we can 86 00:06:57,716 --> 00:07:01,467 integrate. if you have a OGF if you integrate it 87 00:07:01,467 --> 00:07:05,566 from zero to Z. if you do it term by term the definition, 88 00:07:05,566 --> 00:07:11,123 you see that, that gives us the OGF of the sequence, A1 over two, A2 over three 89 00:07:11,123 --> 00:07:15,082 and so forth. so, taking our standard integrating it. 90 00:07:15,082 --> 00:07:18,764 On the left, it's natural log of one over one minus Z. 91 00:07:18,764 --> 00:07:24,460 On the right, it's the sum Z to the N over N or the generating function for the 92 00:07:24,460 --> 00:07:28,350 sequence, one, one half, one third, one fourth, and so forth. 93 00:07:28,350 --> 00:07:34,884 [COUGH] so that's integration. and we can, actually, integrate more and 94 00:07:34,884 --> 00:07:39,282 get more, answers, but, let's look at another thing, 95 00:07:39,282 --> 00:07:45,349 In that is, partial sum, if you have a genarating function and you multiply by 96 00:07:45,349 --> 00:07:51,113 one minus Z, then you get the generating function of the partial sums of the 97 00:07:51,113 --> 00:07:54,905 sequence. so the original sequence is A0, A1, and 98 00:07:54,905 --> 00:08:00,593 so for, partial sums there A0, plus A1, A0 plus A1, plus A2 and so forth. 99 00:08:00,593 --> 00:08:08,204 Let's look at a proof of that fact so that's just running down the definition 100 00:08:08,204 --> 00:08:15,027 of the two sequences 1 1 1 - z is some big until zk and AFC is by definition 101 00:08:15,027 --> 00:08:20,782 some ingredients of a and zn so we have the product of those two sums. 102 00:08:20,782 --> 00:08:28,181 so we distribute to bring in the powers of z together and give us that double 103 00:08:28,181 --> 00:08:31,836 sum. then the next thing is to, in the inner 104 00:08:31,836 --> 00:08:37,379 sum, change N to N minus K. and so then we have A, N minus K and Z to 105 00:08:37,379 --> 00:08:44,665 the N so, there's only, N in the exponent of Z, and then switch order of summation, 106 00:08:44,665 --> 00:08:50,843 so K be going in your little zero, N bigger than or equal to K, if we switch 107 00:08:50,843 --> 00:08:57,416 order of co, summation that's the same as N bigger than zero, the K restricted to 108 00:08:57,416 --> 00:09:02,810 between, be between zero and N. and then, in that inner sum, we can 109 00:09:02,810 --> 00:09:07,259 change, k to n - k. and then we see that we have the partial 110 00:09:07,259 --> 00:09:09,483 sums. So the generating function. 111 00:09:09,483 --> 00:09:14,766 so this product is the generating function of that sequence which is the 112 00:09:14,766 --> 00:09:19,215 partial sums. so, that's another, fine operation, to be 113 00:09:19,215 --> 00:09:25,193 able to perform to give us a richer set of functions, of sequences that we now 114 00:09:25,193 --> 00:09:30,704 generating functions for. So for example if given our two of the 115 00:09:30,704 --> 00:09:36,185 generating functions that we've already derive two of the sequences that we've 116 00:09:36,185 --> 00:09:40,090 already derived generating functions for. If we multiply those together. 117 00:09:40,090 --> 00:09:45,341 Or one over one minus Z times, log one minus Z, we get the generating function 118 00:09:45,341 --> 00:09:50,462 for the harmonic numbers, a harmonic numbers is sum from, of K goes from one 119 00:09:50,462 --> 00:09:55,910 to N of one over one mine, one over K. and we saw that the harmonic numbers, 120 00:09:55,910 --> 00:10:01,031 arose in the analysis of quick sort and naturally arise in many places in the 121 00:10:01,031 --> 00:10:06,020 analysis of algorithms and now we have, we can represent'em with that single 122 00:10:06,020 --> 00:10:10,550 function, one over one minus Z, natural log of, one over one minus Z. 123 00:10:10,550 --> 00:10:16,487 and that partial sum idea, generalizes to the idea of a convolution. 124 00:10:16,487 --> 00:10:22,099 if you have, any two generating functions, you can multiply them 125 00:10:22,099 --> 00:10:26,573 together. and you get the, generating function for 126 00:10:26,573 --> 00:10:31,779 this, convolved product. sum from where the nth term in the 127 00:10:31,779 --> 00:10:36,090 sequence is sum from zero goes from k to n of akbn-k. 128 00:10:36,090 --> 00:10:41,635 And here's the proof of that. It's just pretty much the same as the 129 00:10:41,635 --> 00:10:48,607 proof that we just did for partial sums where we distribute then we change in the 130 00:10:48,607 --> 00:10:53,043 inner sum. We change n to n - k [COUGH] and then we 131 00:10:53,043 --> 00:10:58,510 switch order of summation and that gives us the convolved product. 132 00:10:58,510 --> 00:11:03,273 So that's convolution. so for example, if, another way to derive 133 00:11:03,273 --> 00:11:08,597 the generating function for the natural numbers, is just to, square the 134 00:11:08,597 --> 00:11:14,552 generating function for ones, and then that, you know you can do the math to see 135 00:11:14,552 --> 00:11:18,755 that this convolved product is just N plus one in that case. 136 00:11:18,755 --> 00:11:24,149 And that's a different way to derive the generating function for the natural 137 00:11:24,149 --> 00:11:27,080 numbers. So that's convolution. 138 00:11:27,080 --> 00:11:35,886 So the summary is that we can, what's called, expanding a generating function 139 00:11:35,886 --> 00:11:39,435 by, the. expressing an unknown generating function 140 00:11:39,435 --> 00:11:42,185 as a power series. That's finding the coefficients. 141 00:11:42,185 --> 00:11:46,915 in, you can look at what we've been doing as both directions given a sequence 142 00:11:46,915 --> 00:11:51,425 what's the generating function or given a generating function what's the sequence. 143 00:11:51,425 --> 00:11:55,715 So let's look at the first one given a, second one given a generating function 144 00:11:55,715 --> 00:11:59,840 what's the sequence what we've really been using is Taylor's theorem. 145 00:11:59,840 --> 00:12:05,252 That if you can differentiate the function then you can expand it and know 146 00:12:05,252 --> 00:12:10,525 the coefficients of Z to the N, it's just the Nth derivative of the function 147 00:12:10,525 --> 00:12:15,035 divided by N factorial. That's really what's behind the series 148 00:12:15,035 --> 00:12:18,852 that I gave for E to the Z, Z to the N over N factorial. 149 00:12:18,852 --> 00:12:22,668 or for one over one minus Z, the geometric series. 150 00:12:22,668 --> 00:12:27,803 the derivatives give factorials and they cancel out and you get one. 151 00:12:27,803 --> 00:12:33,354 So you can get your basic starting point from the Taylor Theorem usually and 152 00:12:33,354 --> 00:12:36,346 that's. that's what I just mentioned. 153 00:12:36,346 --> 00:12:40,213 But also, you can reduce to known generating functions. 154 00:12:40,213 --> 00:12:44,152 as we did for example. if we have 1 / 1 - z. 155 00:12:44,152 --> 00:12:49,379 Natural log of 1 / 1 - z. We know how to find the coefficients of z 156 00:12:49,379 --> 00:12:53,390 to the n in that. by, the process of convolution. 157 00:12:53,390 --> 00:13:01,940 so that's a summary of what we do to find coefficients given a generating function. 158 00:13:01,940 --> 00:13:05,804 And so the other way, if we're given this sequence. 159 00:13:05,804 --> 00:13:11,570 how do we find the generating functions? The same is just the same thought, just 160 00:13:11,570 --> 00:13:15,910 worked the other way. we integrate 1 / 1 - z, to get the 161 00:13:15,910 --> 00:13:20,387 generating function for one over k, and then convolve it with 1- z. 162 00:13:20,387 --> 00:13:25,610 to get our generating function. So that's, working with generating 163 00:13:25,610 --> 00:13:30,290 functions, just using the basic operations, that we've talked about. 164 00:13:30,290 --> 00:13:37,798 So here's a exercise that now you should think about to cement your understanding 165 00:13:37,798 --> 00:13:44,729 of the idea of ordinarity generating functions and the sequences that [COUGH] 166 00:13:44,729 --> 00:13:52,054 the sequences that they represent. So let's prove that using generating 167 00:13:52,054 --> 00:14:00,380 functions, prove that the sum of the harmonic numbers from K goes from 1 to N 168 00:14:00,380 --> 00:14:04,405 has this value. remember when we talked about solving 169 00:14:04,405 --> 00:14:09,362 recurrences we said that we're going to find that we need, we're going to have 170 00:14:09,362 --> 00:14:14,573 sums that we need to evaluate and how are we going to evaluate a sum like that if 171 00:14:14,573 --> 00:14:19,785 it's going to turn up, and generating functions are a reasonable tool for doing 172 00:14:19,785 --> 00:14:23,916 something like this. So think about if you, if you can solve 173 00:14:23,916 --> 00:14:29,381 that problem to apply your understanding of the last couple of slides in the 174 00:14:29,381 --> 00:14:32,665 lecture. So what we do is for the left-hand side, 175 00:14:32,665 --> 00:14:36,345 so what's the generating function for the left-hand side? 176 00:14:36,345 --> 00:14:41,638 Well we know the generating function for the harmonic numbers, that's one over one 177 00:14:41,638 --> 00:14:46,544 minus Z, log of one over one minus Z. If we multiply that by one minus Z, then 178 00:14:46,544 --> 00:14:49,320 we get the generating function for the sum. 179 00:14:49,320 --> 00:14:54,097 So first thing, that gives us the generating function for the left-hand 180 00:14:54,097 --> 00:14:56,855 side. So now to what we want to do is we want 181 00:14:56,855 --> 00:15:02,200 to extract coefficients from that generating function in a different way. 182 00:15:02,200 --> 00:15:08,818 And what we'll do is we'll. convolve natural log of 1-z with 1 / 1 - 183 00:15:08,818 --> 00:15:14,827 z^2 to get the coefficients. So that tells us right away that the 184 00:15:14,827 --> 00:15:20,298 coefficient of z to the n in this its a convolution, its a summon k the 185 00:15:20,298 --> 00:15:26,539 coefficient of z to the n in that one will n - it and the coefficients z the n 186 00:15:26,539 --> 00:15:30,707 and that one over k. So, that's just a convolution of, simple 187 00:15:30,707 --> 00:15:33,806 convolution of those two generating functions. 188 00:15:33,806 --> 00:15:37,848 It's a sum, but it's, all the pieces of that sum we can do. 189 00:15:37,848 --> 00:15:43,439 we just have to do a little bit of math. It's N plus one, times H of N, that's the 190 00:15:43,439 --> 00:15:46,740 first term. And then, minus K over K, and there's N 191 00:15:46,740 --> 00:15:50,984 terms, it's just minus N. And then, just need to note that H of N 192 00:15:50,984 --> 00:15:54,016 is H of N plus one, minus one over N plus one. 193 00:15:54,016 --> 00:15:57,250 And then, a little algebra gives us the solution. 194 00:15:57,250 --> 00:16:02,303 So that's an introduction to ordinary generating functions and some 195 00:16:02,303 --> 00:16:08,173 calculations that gives us the useful ways to work with sequences and evaluate 196 00:16:08,173 --> 00:16:14,044 sums and do other operations just because of the idea that we can represent an 197 00:16:14,044 --> 00:16:18,280 entire sequence with the single mathematical function.