1 00:00:03,340 --> 00:00:08,057 Today we're going to talk about an introduction to analytic commonotorics. 2 00:00:08,057 --> 00:00:13,080 it might seem a bit strange in a course entitled, Analytic Combinatorics to not 3 00:00:13,080 --> 00:00:16,082 get to this topic until the middle of the course. 4 00:00:16,082 --> 00:00:20,860 But as you see it builds upon all the things we've talked about until this 5 00:00:20,860 --> 00:00:26,374 point and gives us a, coherent starting point from where we can go forward in the 6 00:00:26,374 --> 00:00:30,478 analysis of algorithms and the analysis of combinatorial structures. 7 00:00:30,478 --> 00:00:35,257 And I hope by the end of this lecture you'll have a pretty good ideal of what 8 00:00:35,257 --> 00:00:39,525 analytic combinatorics actually is. Just start with a brief overview. 9 00:00:39,525 --> 00:00:44,359 Analytic Combinatorics is a Calculus for the quantitative study of large 10 00:00:44,359 --> 00:00:48,862 combinatorial structures. and most of the work behind Analytic 11 00:00:48,862 --> 00:00:54,160 Combinatorics is set forth in our book, Analytic Combinatorics, that'll be the 12 00:00:54,160 --> 00:00:59,193 basis for part two of this course. but it also plays an important role in 13 00:00:59,193 --> 00:01:03,983 the, in the analysis of algorithms and, and the, the tie between elementary 14 00:01:03,983 --> 00:01:09,351 combinatorics and the kind of analysis that we need to really study computer 15 00:01:09,351 --> 00:01:12,628 programs. So the features, the basic features of 16 00:01:12,628 --> 00:01:17,122 analytic combinatorics is that, we begin with formal combinatorial 17 00:01:17,122 --> 00:01:20,587 constructions. So that is, we have a mathematical way to 18 00:01:20,587 --> 00:01:23,520 specify what it is that, that we're studying. 19 00:01:23,520 --> 00:01:29,905 the generating function that we've talked about in the third lecture, is really the 20 00:01:29,905 --> 00:01:33,999 central object of study in the analytic combinatorics. 21 00:01:33,999 --> 00:01:39,135 Number one, because we have transfer theorems that can immediately give us 22 00:01:39,135 --> 00:01:43,854 generating function equations from the combinatorial constructions. 23 00:01:43,854 --> 00:01:49,615 And number two, because we can take transfer theorems to give us estimates of 24 00:01:49,615 --> 00:01:53,710 the values of things right from the generating function. 25 00:01:53,710 --> 00:01:59,507 As mentioned last time, our asymptotic results are going to extend in principle 26 00:01:59,507 --> 00:02:02,957 to any desired precision on the standard scale. 27 00:02:02,957 --> 00:02:07,947 and most important is that it's a calculus, that is, we can handle 28 00:02:07,947 --> 00:02:11,983 variations on fundamental constructions very easily. 29 00:02:11,983 --> 00:02:18,295 and those kinds of variations help us cover a very broad variety of problems 30 00:02:18,295 --> 00:02:21,891 for study. So this is just a graphic depiction. 31 00:02:21,891 --> 00:02:25,516 We start with combinatorials constructions. 32 00:02:25,516 --> 00:02:31,466 And we use a symbolic transfer theorem to get a generating function equation and 33 00:02:31,466 --> 00:02:35,140 that process is sometimes known as the symbolic method. 34 00:02:35,140 --> 00:02:40,161 Then from the generating function equation, we use analysis and we use 35 00:02:40,161 --> 00:02:45,899 analytic transfer thorem to get our coefficient asymptotics directly. [COUGH] 36 00:02:45,899 --> 00:02:51,637 Essentially, this process allows us to avoid a lot of the detail calculations 37 00:02:51,637 --> 00:02:55,869 that we've been doing, in the analysis of algorithms and combinatorial structures. 38 00:02:57,591 --> 00:03:03,186 for example, in analytic combinatorics, if you want to know the number or tree, 39 00:03:03,186 --> 00:03:08,566 binary trees within nodes, there's a commonotorial instruction and we'll go 40 00:03:08,566 --> 00:03:12,549 through the details of this. That immediately transfers to a 41 00:03:12,549 --> 00:03:17,593 generating function equation. That immediately transfers to coefficient 42 00:03:17,593 --> 00:03:22,140 asymptotics for the result without going into all of the detail. 43 00:03:22,140 --> 00:03:26,112 That's the overview. We'll end the lecture with this slide two 44 00:03:26,112 --> 00:03:30,790 and you'll understand everything that goes behind the transfers. 45 00:03:30,790 --> 00:03:36,411 So the beginning point is the symbolic method, so we'll start by talking about 46 00:03:36,411 --> 00:03:40,792 the symbolic method. Now, it's an approach for number one, for 47 00:03:40,792 --> 00:03:45,803 defining combinatorial constructions. But mainly, for translating them to 48 00:03:45,803 --> 00:03:50,675 generating function equations. And the way that we do that is, define a 49 00:03:50,675 --> 00:03:55,756 class of combinatorial objects. Define some notion of what the size of an 50 00:03:55,756 --> 00:03:59,235 object is. Then, define a generating function, whose 51 00:03:59,235 --> 00:04:02,298 coefficients count objects of the same size. 52 00:04:02,298 --> 00:04:07,726 that's what we've been doing in generating function counting in several 53 00:04:07,726 --> 00:04:20,515 examples already. and then from those operations we're 54 00:04:20,515 --> 00:04:26,267 going to have translations for each operation that defines a construction to 55 00:04:26,267 --> 00:04:31,795 an operation on a generating function. And this is just the kind of notation 56 00:04:31,795 --> 00:04:34,591 that we use. Upper, upper case letters for 57 00:04:34,591 --> 00:04:39,092 combinatorial objects. some no, notation like absolute value for 58 00:04:39,092 --> 00:04:42,707 size. and then generating function will have 59 00:04:42,707 --> 00:04:47,685 the same letter as the as the class. Except it will be a function of a 60 00:04:47,685 --> 00:04:51,981 variable, usually Z. and then the operations actually will 61 00:04:51,981 --> 00:04:57,521 involve familiar symbols So now we have to get started somewhere, so there's a 62 00:04:57,521 --> 00:05:02,748 very formal basis, that, and, after these definitions we'll do examples and you'll 63 00:05:02,748 --> 00:05:07,914 see, the need for, for these, but it's a good, thing to talk about'em right at the 64 00:05:07,914 --> 00:05:10,649 beginning. So what is a combinatorial class, it's 65 00:05:10,649 --> 00:05:15,633 just a set of objects and size function. now we have to have something to begin 66 00:05:15,633 --> 00:05:19,220 with, and we call those atoms, those are objects at size one. 67 00:05:19,220 --> 00:05:22,762 We also, for convenience, have an atom of size zero. 68 00:05:22,762 --> 00:05:27,028 Which is a neutral object, and that's useful for describing. 69 00:05:27,028 --> 00:05:30,715 You'll see, that's useful for recursive definitions. 70 00:05:30,715 --> 00:05:36,427 so a combinatorial construction uses the union product and sequence operations 71 00:05:36,427 --> 00:05:42,067 that I'll talk about in a minute to define a class in terms of atoms in other 72 00:05:42,067 --> 00:05:45,682 classes. And we start with the very basic building 73 00:05:45,682 --> 00:05:52,218 blocks over on the right where the notation capital Z is in a contains a 74 00:05:52,218 --> 00:05:58,074 single atom then there is notation capital E which is a, a neutral class 75 00:05:58,074 --> 00:06:02,654 that contains an atom of size zero and also this empty class. 76 00:06:02,654 --> 00:06:09,261 And again now worthwhile I spend time in these definitions right now but to refer 77 00:06:09,261 --> 00:06:16,078 back to one we use later on if necessary. So here's a very simple example of a 78 00:06:16,078 --> 00:06:22,573 combinatorial class the natural numbers. So the defi, definition of a natural 79 00:06:22,573 --> 00:06:27,490 number is a set of atoms. Or since you can't tell the difference 80 00:06:27,490 --> 00:06:33,387 between atoms that's what we mean by unlabeled and we'll get into that detail, 81 00:06:33,387 --> 00:06:38,376 in much more detail later. A set or a sequence, it's the same thing. 82 00:06:38,376 --> 00:06:44,804 So, there's only one object of each size. so, we most usually, or at the beginning, 83 00:06:44,804 --> 00:06:48,435 we're most interesting in the counting sequence. 84 00:06:48,435 --> 00:06:53,731 How many objects of each size there are? In this case, there's only one. 85 00:06:53,731 --> 00:06:59,858 And we use ordinary generating functions, so the ordinary generating function for 86 00:06:59,858 --> 00:07:05,792 natural numbers is just 1 / 1 - Z. So that's a simple example of a 87 00:07:05,792 --> 00:07:11,317 combinatorial class and actually, that, it seems trivial, and that basically the 88 00:07:11,317 --> 00:07:15,855 early ones do seem trivial. It's when you put'em together that you 89 00:07:15,855 --> 00:07:19,407 get interesting and useful mathematical results. 90 00:07:19,407 --> 00:07:24,603 So, for example this combinatorial class is a basis of study for things like 91 00:07:24,603 --> 00:07:29,338 partitions of natural numbers. how many ways can you break'em up into 92 00:07:29,338 --> 00:07:35,013 subunits and compositions, and so forth? And we don't get into that too much in 93 00:07:35,013 --> 00:07:40,774 part one but we will in part two. here's something that we, that we study 94 00:07:40,774 --> 00:07:44,349 all the time in computer science a bit string. 95 00:07:44,349 --> 00:07:49,849 A bit string is a sequence of zero or one bits, and that's very familiar just 96 00:07:49,849 --> 00:07:55,054 defining this in familiar class. I have to get used to are, are notation 97 00:07:55,054 --> 00:07:59,600 and conventions. so how many bit strings are there of 98 00:07:59,600 --> 00:08:05,918 length N, well there's two to the N, so what's the OGF, it's two to the N, Z to 99 00:08:05,918 --> 00:08:12,544 the N, which is 2Z to the N, or 1 / 1 - 2Z, so that's another example of a 100 00:08:12,544 --> 00:08:17,910 combinatorial class. here's one familiar one recast in terms 101 00:08:17,910 --> 00:08:24,043 of analytic combinatorics. so the binary tree is empty or it's a 102 00:08:24,043 --> 00:08:31,000 noded two binary trees that's, that are in sequence in order that matters. 103 00:08:31,000 --> 00:08:36,316 so those are now familiar binary trees that we studied before. 104 00:08:36,316 --> 00:08:40,929 we know the counting sequence is the Catalan numbers. 105 00:08:40,929 --> 00:08:46,402 [COUGH] that was the subject of quite a bit of lecture three. 106 00:08:46,402 --> 00:08:52,970 and its, its got this OGF and that derivation is all given in lecture three. 107 00:08:52,970 --> 00:08:57,736 so those are three examples of combinatorial classes. 108 00:08:57,736 --> 00:09:02,964 And now I want to show constructions and how we build those things. 109 00:09:02,964 --> 00:09:08,868 so for unlabeled classes, so that's a [COUGH] And again, I will talk about the 110 00:09:08,868 --> 00:09:13,739 distinction with labelled in a minute. We're just going to use three different 111 00:09:13,739 --> 00:09:17,246 constructions. If A and B are combinatorial classes of 112 00:09:17,246 --> 00:09:22,248 unlabelled objects, then we have the disjoint union, the Cartesian product and 113 00:09:22,248 --> 00:09:26,340 the sequence operations. And, here is the meaning of each one of 114 00:09:26,340 --> 00:09:29,652 those. A plus B is just copies of objects from A 115 00:09:29,652 --> 00:09:32,770 and B. Take one from A and one from B and that's 116 00:09:32,770 --> 00:09:37,382 the, that's the disjoint union. Cartesian product is ordered pairs of 117 00:09:37,382 --> 00:09:40,240 copies of objects, one from A and one from B. 118 00:09:40,240 --> 00:09:44,100 And sequences, sequences of objects from A. 119 00:09:44,100 --> 00:09:51,525 so those are the constructions and these are just examples of how a construction 120 00:09:51,525 --> 00:09:55,110 might work. So, for bit strength [COUGH]. 121 00:09:55,110 --> 00:09:59,158 I mean, you can use the usual distributive law. 122 00:09:59,158 --> 00:10:04,445 So 00 + 01 is got copies of 00 and 01. And same on the right. 123 00:10:04,445 --> 00:10:10,817 And if we do the Cartesian product of those, we have to take each possibility 124 00:10:10,817 --> 00:10:15,286 on the left and sequence with each possibility on the right. 125 00:10:15,286 --> 00:10:21,673 so there's six possibilities there. So that's an example of, a, use of the 126 00:10:21,673 --> 00:10:25,800 cartesian product and disjoint union, operations. 127 00:10:25,800 --> 00:10:33,811 So here's one just with uninary numbers, so, a an atom of cartesian product with a 128 00:10:33,811 --> 00:10:41,417 sequence of atoms is, gives that list and there's binary trees so in, external node 129 00:10:41,417 --> 00:10:47,728 kind of atom, crossed with an internal node kind of atom crossed with a little 130 00:10:47,728 --> 00:10:51,370 tree of size of one, gives a two tree node. 131 00:10:51,370 --> 00:10:56,024 that the, that's the kind of constructions that we're going to use. 132 00:10:56,024 --> 00:11:01,390 And those are interesting, and we'll see how to use those to precisely define 133 00:11:01,390 --> 00:11:05,723 Classes of interest But and unlabeled again. 134 00:11:05,723 --> 00:11:11,403 We'll talk about it later what we mean by that. but what's most important is the 135 00:11:11,403 --> 00:11:16,231 idea of a transfer theorem. and this is, the first basis of the 136 00:11:16,231 --> 00:11:20,277 symbolic method. The idea is while we're constructing the 137 00:11:20,277 --> 00:11:26,099 classes we're also developing equations for their generating functions because 138 00:11:26,099 --> 00:11:31,211 for every operation we have a corresponding operation on the generating 139 00:11:31,211 --> 00:11:34,978 function. and for simple unlabeled classes they're 140 00:11:34,978 --> 00:11:38,320 quite simple. So, for example, for disjoint union. 141 00:11:38,320 --> 00:11:43,685 If we take disjoint copies of objects from A and B, and we form the disjoint 142 00:11:43,685 --> 00:11:49,897 union, the OGF for that class is the sum of the OGF's of the two classes that were 143 00:11:49,897 --> 00:11:53,426 operans in. For cartesian product, it's the product, 144 00:11:53,426 --> 00:11:59,497 we'll do a proof of this in just a second and for sequence it's one over one minus. 145 00:11:59,497 --> 00:12:05,357 So whatever construction we make, we can translate that to an operation on the 146 00:12:05,357 --> 00:12:10,722 generating function, so anything that we can constrruct, we have a generating 147 00:12:10,722 --> 00:12:14,151 function for. so and, and these are the proofs. 148 00:12:14,151 --> 00:12:20,178 And these are very straightforward from the kind of GF generating function 149 00:12:20,178 --> 00:12:25,990 counting arguments that, that we did when we talked about generating functions. 150 00:12:25,990 --> 00:12:31,227 if gamma belongs to A plus B then it, they're disjoint copies. 151 00:12:31,227 --> 00:12:35,030 So some of them belong to A, some of them belong to B. 152 00:12:35,030 --> 00:12:40,340 you split the sum in those two ways, and you have A of Z plus B of Z. 153 00:12:40,340 --> 00:12:47,171 for cross product that's a convolution. Again, they break up into independently, 154 00:12:47,171 --> 00:12:52,620 into the ones from a and the ones from b. the size of [COUGH]. 155 00:12:52,620 --> 00:12:57,823 Since you've taken one from each the size of gamma is the size of the alpha-1 plus 156 00:12:57,823 --> 00:13:01,816 the size of the beta-1. and those are independent, so that's the 157 00:13:01,816 --> 00:13:05,659 product. in sequence fallouts from the idea that 158 00:13:05,659 --> 00:13:10,771 sequence is like a product of two product of three product of four. 159 00:13:10,771 --> 00:13:15,590 It's just the, geometric series gives the proof of the sequence. 160 00:13:15,590 --> 00:13:19,753 So that's the transfer theorems and that's the proofs. 161 00:13:19,753 --> 00:13:25,376 And from this point forward with a symbolic method we don't have to worry 162 00:13:25,376 --> 00:13:28,443 about sums involving convolutions anymore. 163 00:13:28,443 --> 00:13:32,818 [COUGH] whereas, [COUGH], we can get so we can or practice 164 00:13:32,818 --> 00:13:37,976 doing convolutions and so forth, but with this we can do multiple convolutions and 165 00:13:37,976 --> 00:13:41,688 we don't have to worry about carrying around those details. 166 00:13:41,688 --> 00:13:44,960 We know what the generating function is going to be. 167 00:13:44,960 --> 00:13:49,913 so let's just look at how it applies for binary trees. 168 00:13:49,913 --> 00:13:55,842 so, so every time that we're going to study a combinatorial class or we're 169 00:13:55,842 --> 00:13:58,994 going to do it according to this rubric here. 170 00:13:58,994 --> 00:14:04,547 So, we have to articulate what's the class its a class of all binary trees. 171 00:14:04,547 --> 00:14:10,251 What's the size function a comment of class is the set and that in the size 172 00:14:10,251 --> 00:14:15,280 function and that's we're going to use under internal nodes indeed. 173 00:14:15,280 --> 00:14:26,022 the ordinary generating function is the sum over all trees in the class Z to the 174 00:14:26,022 --> 00:14:29,544 size. and as we discussed when talking about 175 00:14:29,544 --> 00:14:35,106 counting with generating functions that for every size N there's going to be T 176 00:14:35,106 --> 00:14:37,855 sub N that gives us the counting sequence. 177 00:14:37,855 --> 00:14:42,893 the coefficient of Z to the N in the generating function is the number of 178 00:14:42,893 --> 00:14:46,100 trees, and that's what we're going to be looking for. 179 00:14:46,100 --> 00:14:50,841 we need atoms to get going. We have internal nodes and external 180 00:14:50,841 --> 00:14:54,577 nodes. so we'll denote external nodes by Z sub 181 00:14:54,577 --> 00:14:59,677 box, and internal nodes by Z sub dot. and we want to count according to 182 00:14:59,677 --> 00:15:05,425 internal nodes, the size of an internal node is one, the size of an external node 183 00:15:05,425 --> 00:15:08,517 is zero. so that's the set up, that's the building 184 00:15:08,517 --> 00:15:13,152 blocks on the generating functions of these little classes since the size for 185 00:15:13,152 --> 00:15:17,615 an external node is zero, it's one, the size for an internal node is one, it's Z. 186 00:15:17,615 --> 00:15:20,820 that's the generating function for that little class. 187 00:15:20,820 --> 00:15:22,836 Okay. So that's the setup. 188 00:15:22,836 --> 00:15:28,965 And then here's the construction. and this is just using the, union and 189 00:15:28,965 --> 00:15:33,804 Cartesian product rules. It, it, you can read it in English, or 190 00:15:33,804 --> 00:15:38,884 you can read it in math. It says, the binary tree is an external 191 00:15:38,884 --> 00:15:42,513 node. Or, it's a tree connected to an internal 192 00:15:42,513 --> 00:15:47,748 node connected to a tree. and that's what we mean by a binary tree. 193 00:15:47,748 --> 00:15:52,210 This just makes it rigorous So, that's the construction. 194 00:15:52,210 --> 00:15:55,643 So that's a, a description of the class of all binary trees. 195 00:15:55,643 --> 00:15:59,833 A recursive description, but it's a description of a class of all binary 196 00:15:59,833 --> 00:16:02,568 trees. And now what's significant is, we can use 197 00:16:02,568 --> 00:16:06,816 the transfer theorem to immediately translate to the generating function 198 00:16:06,816 --> 00:16:08,082 equation. Z sub box. 199 00:16:08,082 --> 00:16:13,280 The generating function is one. Generating function for Z sub dot is Z. 200 00:16:13,280 --> 00:16:16,250 Generating function for the two Ts is T(Z).z). 201 00:16:16,250 --> 00:16:22,116 And Cartesian product of those is the same as the, translates to the product of 202 00:16:22,116 --> 00:16:25,978 the generating functions. And no sums involved there. 203 00:16:25,978 --> 00:16:31,770 We don't have to do sums anymore to get generating function equations of this 204 00:16:31,770 --> 00:16:34,937 nature. Now the next step is to extract 205 00:16:34,937 --> 00:16:39,322 coefficients. We're going to talk about that a little 206 00:16:39,322 --> 00:16:43,128 later. I'll just remark that this is something 207 00:16:43,128 --> 00:16:49,747 that we've studied already, to finally get out to the answer that coefficient is 208 00:16:49,747 --> 00:16:53,435 E^Nn. And that function is asymptotic to 4^N 209 00:16:53,435 --> 00:16:57,732 over squared of pi N^3. but for, for now when talking about the 210 00:16:57,732 --> 00:17:03,419 symbolic method we're going to consider how do we get those generating function 211 00:17:03,419 --> 00:17:06,063 equations. That's the first part of analytic 212 00:17:06,063 --> 00:17:11,022 combinatorics the symbolic method. And well, let's look at lots of examples 213 00:17:11,022 --> 00:17:14,527 of that. And then later we'll talk about how do we 214 00:17:14,527 --> 00:17:19,624 get the coefficients out. So that's our binary tree analysis recast 215 00:17:19,624 --> 00:17:25,200 in terms of the symbolic method. All of the calculations that we did 216 00:17:25,200 --> 00:17:30,694 before are in there, but it's a much, much, much more general setting. 217 00:17:30,694 --> 00:17:35,450 And we'll see how important that is as the course goes on. 218 00:17:35,450 --> 00:17:40,034 so what about ki, just as a similiar example, what about if we want to count 219 00:17:40,034 --> 00:17:44,089 binary trees by external nodes. so that's a different combinatorial 220 00:17:44,089 --> 00:17:48,614 class, because it's got a different size function, and we denote that with box and 221 00:17:48,614 --> 00:17:53,198 T and the atoms are a little bit different, because we consider external 222 00:17:53,198 --> 00:17:57,723 nodes to be size one and internal nodes to be a size zero and the generating 223 00:17:57,723 --> 00:18:02,542 functions are different. So it's the same construction, but the atoms are different 224 00:18:02,542 --> 00:18:05,540 so we get a different generating function equation. 225 00:18:05,540 --> 00:18:11,145 It's a really similar generating function equation, actually T box to Z is ZT of Z. 226 00:18:11,145 --> 00:18:15,889 if you plug in ZT of Z of that equation, and divide by Z, you get the same 227 00:18:15,889 --> 00:18:20,186 equation as before. well, this is a proof that the number of 228 00:18:20,186 --> 00:18:25,895 binary trees within external nodes is the same as the number of binary trees within 229 00:18:25,895 --> 00:18:30,245 minus 1 internal nodes. there's easier proofs of that, but this 230 00:18:30,245 --> 00:18:35,546 is showing the consistency of the analysis and the ease of developing a 231 00:18:35,546 --> 00:18:40,100 commentorial construction to get a generating function in equation. 232 00:18:40,100 --> 00:18:43,854 Let's look at some other examples. What about binary strings? 233 00:18:43,854 --> 00:18:48,734 and just as a warm up, just to check on our understandings, and notation, and 234 00:18:48,734 --> 00:18:53,427 atoms and constructions, and transfers let's try to count binary strings. 235 00:18:53,427 --> 00:18:57,870 Now we know what the answer is. So our class is, the class of all binary 236 00:18:57,870 --> 00:19:00,811 strings. The size is, the number of bits in the 237 00:19:00,811 --> 00:19:04,837 binary strings. OGF, same as before, and same as always 238 00:19:04,837 --> 00:19:10,873 for every object in the class you add up Z to the size of that object and that 239 00:19:10,873 --> 00:19:16,978 brings the counting sequence as the coefficient of Z^N in that function. 240 00:19:16,978 --> 00:19:22,522 for binary strings, we have two atoms, either zero bits or one bits, that will 241 00:19:22,522 --> 00:19:28,558 call them Z0 and Z1 they are both of size one, and they both have generative 242 00:19:28,558 --> 00:19:32,573 function Z. So how many binary strings within bits? 243 00:19:32,573 --> 00:19:39,061 Well a binary string is a sequence of zero and one bits, that's what that says, 244 00:19:39,061 --> 00:19:46,298 that's the definition of binary strings. And now we go to the transfer theorem, Z0 245 00:19:46,298 --> 00:19:50,167 + Z1 is 2Z. Sequence of 2Z, 1 / 1 minus. 246 00:19:50,167 --> 00:19:54,098 Binary strings of sequences are in one bits. 247 00:19:54,098 --> 00:19:57,493 And the transfer immediately gives us B(Z)z)=1/(1-2*z). 248 00:19:57,493 --> 00:20:01,335 = 1 / 1 - 2Z. and that checks, that coefficient of Z^Nn 249 00:20:01,335 --> 00:20:06,258 and B(Z) is 2^Nn, as we expected. Very simple and elementary as we'll see 250 00:20:06,258 --> 00:20:12,024 in just a minute how this translates to more interested, interesting and much 251 00:20:12,024 --> 00:20:17,304 more difficult to solve problems. just as an aside there's lot of ways to 252 00:20:17,304 --> 00:20:22,861 construct any combinatorial class. Here is an alternative way to do binary 253 00:20:22,861 --> 00:20:27,030 strings, same starting point or we can use this construction. 254 00:20:27,030 --> 00:20:33,221 A binary string is either empty, or it's a zero or one bit followed by a binary 255 00:20:33,221 --> 00:20:36,910 string. That leads to the generating function 256 00:20:36,910 --> 00:20:43,771 equation direct from transfer theorem 1 + B of Z = 1 + 2Z B of Z and if you solve 257 00:20:43,771 --> 00:20:49,920 for B of Z you get the same result. And so it's another way to do it. 258 00:20:49,920 --> 00:20:55,456 So again very simple constructions immediate transfer to OGF equations then 259 00:20:55,456 --> 00:20:59,170 it's just going to be a matter of extracting coefficients. 260 00:20:59,170 --> 00:21:05,936 so here's now the first example of a problem that might be more difficult to 261 00:21:05,936 --> 00:21:11,838 solve and it's representative of a very general treatment that we'll do in 262 00:21:11,838 --> 00:21:15,698 chapter eight. How many embed binary strings have no two 263 00:21:15,698 --> 00:21:19,573 consecutive zeros? actually there's a lots of practical 264 00:21:19,573 --> 00:21:23,119 applications where such questions are quite important. 265 00:21:23,119 --> 00:21:27,716 if, if we're looking for lots of consecutive zeros some types of 266 00:21:27,716 --> 00:21:33,299 communications devices have problems in such situations, and need to have codes 267 00:21:33,299 --> 00:21:36,977 that don't do that. And, and so, these things are, are well 268 00:21:36,977 --> 00:21:40,589 studied. And this is a simple example but it gets 269 00:21:40,589 --> 00:21:46,105 to be much more complicated very soon. That's what we'll talk about in chapter 270 00:21:46,105 --> 00:21:49,650 eight. but, still, 271 00:21:49,650 --> 00:21:53,820 let's take a look at solving this with the symbolic method. 272 00:21:53,820 --> 00:22:00,354 okay so it's the same, it's binary string so it's the same setup our class is than 273 00:22:00,354 --> 00:22:04,016 the class of binary strings that don't have any 00. 274 00:22:04,016 --> 00:22:10,407 we have the same setup for a generating function and the atoms are all the same. 275 00:22:10,407 --> 00:22:15,903 So what does the construction look like? While a binary string with no 00 is 276 00:22:15,903 --> 00:22:21,732 either empty or it's zero or it's one or 01 followed by a binary string with no 277 00:22:21,732 --> 00:22:25,448 00. and you can check that that's a way to 278 00:22:25,448 --> 00:22:31,496 describe the class you have to think about a little bit but it's not too bad. 279 00:22:31,496 --> 00:22:37,179 and what's important though is that we don't have just an English language 280 00:22:37,179 --> 00:22:40,750 description, we have a combinatorial construction. 281 00:22:40,750 --> 00:22:46,315 Combinatorial construction immediately translates to a generating function 282 00:22:46,315 --> 00:22:49,432 equation. Z 0 across Z 1 is Z squared. 283 00:22:49,432 --> 00:22:54,776 Z 1 generating function is Z. [INAUDIBLE] plus Z zero generating 284 00:22:54,776 --> 00:22:58,338 function is one plus Z. So put all that together. 285 00:22:58,338 --> 00:23:03,978 Now we have a generating function equation for B zero, zero Z that we can 286 00:23:03,978 --> 00:23:08,727 solve and that's one plus Z over one minus Z minus Z squared. 287 00:23:08,727 --> 00:23:12,290 and again [COUGH] extracting coefficients. 288 00:23:12,290 --> 00:23:16,052 These are problems that we know how to solve. 289 00:23:16,052 --> 00:23:21,235 In this case, it turns out, and we'll look at the details later. 290 00:23:21,235 --> 00:23:25,416 In this case, it turns out to be Fibonacci numbers. 291 00:23:25,416 --> 00:23:27,506 11-e^-z^2) / 1 - Z - Z^2 is F sub N. Z is F1-e^-z^2) / 1 -1. 292 00:23:27,506 --> 00:23:29,763 Z - Z^2 is FN + 1. If you add FN + FN+11 you2. 293 00:23:29,763 --> 00:23:35,866 get FN+2 And that checks with the nth Fibonacci number, checks with the numbers 294 00:23:35,866 --> 00:23:42,304 that we found on the previous slide. Many of you probably noticed that it was 295 00:23:42,304 --> 00:23:49,160 Fibonacci numbers at that point. And, it's clear that this 296 00:23:49,160 --> 00:23:54,528 argument and this process is going to extend easily for binary strings with 297 00:23:54,528 --> 00:23:58,674 other kinds of restrictions. the trick is coming up with a 298 00:23:58,674 --> 00:24:02,004 construction that precisely describes your class. 299 00:24:02,004 --> 00:24:06,829 but often that's not difficult. And again we'll look at a general 300 00:24:06,829 --> 00:24:13,190 treatment of this later on in the course. So those are just some starting examples. 301 00:24:13,190 --> 00:24:17,277 we're going to have many, many, many examples, to follow. 302 00:24:17,277 --> 00:24:23,515 all with the same basis in one both part and part one and part two of the course. 303 00:24:23,515 --> 00:24:29,897 we're often asking how many of some type of objects are there, with some kind of 304 00:24:29,897 --> 00:24:33,626 restriction. we need to specify what the class is. 305 00:24:33,626 --> 00:24:37,856 We need to specify what the size function is and the atoms. 306 00:24:37,856 --> 00:24:43,450 and write down the generating function. And then we'll do a construction. 307 00:24:43,450 --> 00:24:48,073 that mirrors some English language description usually. 308 00:24:48,073 --> 00:24:51,433 That'll immediately translate to an OGF equation. 309 00:24:51,433 --> 00:24:57,946 and then the last step is to extract the coefficients and we'll talk about that at 310 00:24:57,946 --> 00:25:00,620 the end. So lot's of examples to follow. 311 00:25:00,620 --> 00:25:08,179 but before considering some more I want to talk about labeled objects, but that's 312 00:25:08,179 --> 00:25:11,220 an introduction to symbolic method.