1 00:00:00,012 --> 00:00:03,895 Today, we're going to talk about words and mappings. 2 00:00:03,895 --> 00:00:10,479 This is an appropriate area in which to finish our study because it ties together 3 00:00:10,479 --> 00:00:14,450 many of the things we've talked about before. 4 00:00:14,450 --> 00:00:18,935 Again, this is the, the last of, of the second half of the class. 5 00:00:18,936 --> 00:00:24,511 And what we're talking about today mostly labeled objects, so we'll be working 6 00:00:24,511 --> 00:00:29,947 exponential generating functions. And again, as I've been saying each week 7 00:00:29,947 --> 00:00:35,291 there's many more examples in the book than we're able to do in lecture. 8 00:00:35,291 --> 00:00:40,835 But we'll consider some techniques from analytic combinatorics in applications to 9 00:00:40,835 --> 00:00:45,486 the analysis of algorithms. So to start out, I'm going to talk about 10 00:00:45,486 --> 00:00:49,840 what we mean by what is a word in a combinatorial sense. 11 00:00:49,840 --> 00:00:55,210 And to do that, let's just review a few of the related combinatorial objects that 12 00:00:55,210 --> 00:00:58,714 we've looked at. So, for example, we've looked at again, 13 00:00:58,714 --> 00:01:03,739 how many binary strings are within bits, seems we talked about this almost every 14 00:01:03,739 --> 00:01:08,494 lecture. So a string is a sequence of 0 bits and 1 15 00:01:08,494 --> 00:01:13,319 bits. And with the symbolic method using 16 00:01:13,319 --> 00:01:19,235 ordinary generating functions we show that it's 2 to the N. 17 00:01:19,235 --> 00:01:26,531 Now that can extend to how many strings drawn from an M character alphabet. 18 00:01:26,532 --> 00:01:32,882 Then in that case it's a sequence of one of the M characters which is 1 over 1 19 00:01:32,882 --> 00:01:36,547 minus Mz. So again, that gives us N to the N. 20 00:01:36,547 --> 00:01:41,596 It's the number of strings drawn from the N character alphabet that has N 21 00:01:41,596 --> 00:01:45,217 characters. So, how's that related to words? 22 00:01:45,217 --> 00:01:50,572 Well, we'll get there. Let's look at labelled objects now. 23 00:01:50,572 --> 00:01:55,491 And let's say how many sets labelled sets are there of size N. 24 00:01:55,492 --> 00:02:01,913 So there's exactly one labelled set of size 2, the one that's got 2 objects in 25 00:02:01,913 --> 00:02:05,587 it. And actually of any size N there's only 26 00:02:05,587 --> 00:02:09,898 one labelled set. This is just a little bit of a review of 27 00:02:09,898 --> 00:02:15,778 what we mean by labeled objects as we don't consider the order significant so 28 00:02:15,778 --> 00:02:19,457 there's only one set and we label all the objects. 29 00:02:19,457 --> 00:02:25,714 Now, if you want to take ordered pairs of label sets of N objects, so then what do 30 00:02:25,714 --> 00:02:30,567 you get? Well for 2 objects you can have a 1 and 31 00:02:30,567 --> 00:02:36,545 then a 2, or a 2 and then a 1 or you can have an empty set in 2 objects or 2 32 00:02:36,545 --> 00:02:41,920 objects in an empty set. So the, in this case, the ordering of the 33 00:02:41,921 --> 00:02:49,128 sets is significant and then the labeled objects can fall in the sets in these 34 00:02:49,128 --> 00:02:54,274 different ways. And so, there's 8 different ordered pairs 35 00:02:54,274 --> 00:03:00,500 or labeled sets of, of N objects and so then, you can see the answers to the end. 36 00:03:00,500 --> 00:03:05,918 And that's the same as the number of bitstrings and we'll see how that 37 00:03:05,918 --> 00:03:09,779 relationships comes through in just a minute. 38 00:03:09,779 --> 00:03:16,600 So what about instead of pairs, what if we have a sequence of M sets, how many 39 00:03:16,600 --> 00:03:21,696 sequences of length M of labeled sets of N objects are there? 40 00:03:21,696 --> 00:03:27,162 And I, we use the word, urns, to talk about a set as a thing that can hold 41 00:03:27,162 --> 00:03:31,916 labeled objects. So thinking of it that way, a classic, or 42 00:03:31,916 --> 00:03:35,593 a classical way to think of it is of balls and urns. 43 00:03:35,593 --> 00:03:41,254 So, really what we are talking about is the number of different ways to throw in 44 00:03:41,254 --> 00:03:45,922 balls into two urns. So, if there's one ball, it can go, if 45 00:03:45,922 --> 00:03:50,046 there's two urns, one ball can go into either one of them. 46 00:03:50,046 --> 00:03:55,881 If there's two balls it can either, both can go in the first or both can go in the 47 00:03:55,881 --> 00:03:58,996 second. Or they can go in the two orders. 48 00:03:58,996 --> 00:04:04,672 The labels on the balls are significant but not the order of the labels within the 49 00:04:04,672 --> 00:04:08,045 urn. We put them in the order they went in but 50 00:04:08,045 --> 00:04:13,459 that order is not significant. And again, there's 8 ways to throw three 51 00:04:13,459 --> 00:04:18,838 balls into two urns. So that's a balls-and-urns way of looking 52 00:04:18,838 --> 00:04:22,707 at really the same combinatorial structure. 53 00:04:22,708 --> 00:04:28,225 So again, 2 to the N. So now, let's look at how we get at these 54 00:04:28,225 --> 00:04:34,712 counting results from the symbolic method. And this is just a review of what we 55 00:04:34,712 --> 00:04:39,673 talked about in, in Lecture 5. If we have combinatorial classes of 56 00:04:39,673 --> 00:04:45,282 labeled objects then we have these basic operations that we can perform on the 57 00:04:45,282 --> 00:04:51,049 classes that disjoint copies or taking ordered pairs relabeling in all ways and 58 00:04:51,049 --> 00:04:56,658 then the corresponding operations on the exponential generating function give us a 59 00:04:56,658 --> 00:05:02,191 symbolic transfer from the construction right to the generating function. 60 00:05:02,191 --> 00:05:07,762 And for labeled objects, we extend that to the sequences of length k or sequences of 61 00:05:07,762 --> 00:05:14,482 any length giving those transformations of the generating function or for sets where 62 00:05:14,482 --> 00:05:19,272 we divide by k factorial. So, a set of objects from a class, the 63 00:05:19,272 --> 00:05:25,932 generating function for that is e to the generating function of the class and also 64 00:05:25,932 --> 00:05:30,055 the cycles. So these are the basic operations that we 65 00:05:30,055 --> 00:05:35,706 use for labeled objects. And so, these are the ones that we're 66 00:05:35,706 --> 00:05:41,118 going to use now to look at balls and urns problems or words. 67 00:05:41,119 --> 00:05:47,917 So, combinatorially, we're going to define a word to be a sequence of M urns that 68 00:05:47,917 --> 00:05:53,396 have N objects and it's the number of ways to throw N balls into M urns. 69 00:05:53,396 --> 00:05:58,883 It's a number of it's, it's a configuration of throwing N balls into M 70 00:05:58,883 --> 00:06:02,271 urns. So, I want to know how many different 71 00:06:02,271 --> 00:06:06,687 words there are then we use generating functions. 72 00:06:06,687 --> 00:06:12,565 It's parameterized by M so that'd the number of urns in the sequence. 73 00:06:12,566 --> 00:06:19,924 So, the generating function is the sum of all possible objects that's configurations 74 00:06:19,924 --> 00:06:24,264 the way the balls fall. It's either the object size over W 75 00:06:24,264 --> 00:06:30,267 factorial and then as usual, that collects it together to get us the, a number of 76 00:06:30,267 --> 00:06:35,735 ways we can get balls into M urns. So, and again, we have all these different 77 00:06:35,735 --> 00:06:41,391 ways of looking at it. So, so this 9 balls into 5 urns and maybe 78 00:06:41,391 --> 00:06:48,055 this one way it could come out that corresponds to a sequence of 5 subsets of 79 00:06:48,055 --> 00:06:52,416 9 things or it could just write out the subset. 80 00:06:52,416 --> 00:06:57,478 Those are all different ways of representing the same combinatorial 81 00:06:57,478 --> 00:07:00,798 object. But in terms of the symbolic method, to 82 00:07:00,798 --> 00:07:06,804 find out this generating function or how many different ways there are to do this 83 00:07:06,804 --> 00:07:10,644 it's simple. It's a sequence of length M of a set of 84 00:07:10,645 --> 00:07:14,153 objects. So and it's, it's nothing more than that. 85 00:07:14,154 --> 00:07:20,510 So that means immediately, the generated function equation is e to the z to the Mth 86 00:07:20,510 --> 00:07:24,349 power, or e to the Mz. And so, our number of different 87 00:07:24,349 --> 00:07:30,091 configurations is N factorial times the coefficient of z to the N in that, which 88 00:07:30,091 --> 00:07:34,569 is just M to the N. Now, that M to the N, again, that's, 89 00:07:34,569 --> 00:07:41,512 that's the same as the number of strings from an alphabet of length N with M 90 00:07:41,512 --> 00:07:46,216 characters in it. And, and indeed, there's the 1 to 1 91 00:07:46,216 --> 00:07:52,989 correspondence between words and strings. So a string, as we talked about last time, 92 00:07:52,989 --> 00:07:57,802 is a sequence of N characters drawn from an M character alphabet. 93 00:07:57,802 --> 00:08:03,226 And since for each of the N characters in the string, there's M different 94 00:08:03,226 --> 00:08:07,144 possibilities, there's M to the N different strings. 95 00:08:07,144 --> 00:08:13,294 A word is a sequence of label sets with a total of N objects and there's M to the N 96 00:08:13,294 --> 00:08:16,314 words. So, what's the correspondence? 97 00:08:16,314 --> 00:08:19,983 Well, the correspondence is, is quite simple. 98 00:08:19,983 --> 00:08:27,119 What we do is we take a look at the second set, for example, corresponds to the 99 00:08:27,119 --> 00:08:32,105 positions in the string where the second character happens. 100 00:08:32,106 --> 00:08:37,671 It's as simple as that. There's no 3, so the third set is empty. 101 00:08:37,672 --> 00:08:42,388 The 1 is in position 7 so the first set has 7 in it. 102 00:08:42,389 --> 00:08:48,703 And the 5s are at positions 5, 6, and 9. And the 4s are position 2 and 4. 103 00:08:48,704 --> 00:08:54,712 So, it's just a 1 to 1 correspondence where the word tells us the position in 104 00:08:54,712 --> 00:09:01,930 the string where the character happens. That is for in the word, if you look at 105 00:09:01,930 --> 00:09:08,209 the case set for every i in the word, the ith character in the string is, is k or 106 00:09:08,209 --> 00:09:11,490 vice-versa. If you look at the string, if the ith 107 00:09:11,490 --> 00:09:15,841 character in the string is k, then you put i into the k set in the word. 108 00:09:15,841 --> 00:09:20,475 So, the word is just the indices where the letter appears in the string. 109 00:09:20,475 --> 00:09:25,788 That's the correspondent. So it's very familiar, we, we're, we 110 00:09:25,788 --> 00:09:33,180 worked with strings before and now we're going to be working with words and we have 111 00:09:33,180 --> 00:09:40,188 this one to one correspondence so this is just another way to look at it for binary 112 00:09:40,188 --> 00:09:44,090 strings. So looking at the 8 binary strings as 113 00:09:44,090 --> 00:09:49,646 words first one says that all three characters are zeros, and there's no ones. 114 00:09:49,646 --> 00:09:54,677 And the last one says there's no zeros, and all three characters are one and so 115 00:09:54,677 --> 00:09:57,255 forth. So what's the difference? 116 00:09:57,255 --> 00:10:00,994 That there's no difference, it's only the point of view. 117 00:10:00,995 --> 00:10:05,682 Last lecture, when we were looking at strings, we were concerned about the 118 00:10:05,682 --> 00:10:10,302 sequence of characters and about the relationships between one and the next in 119 00:10:10,302 --> 00:10:14,069 the sequence, looking for patterns in the string, and so forth. 120 00:10:14,069 --> 00:10:19,403 This time we're interested in applications where the sets of indices are important, 121 00:10:19,403 --> 00:10:24,184 where it matters how many zeros there are, how many ones there are, and so forth. 122 00:10:24,184 --> 00:10:29,740 But really it's the same object. In strings, we were using OGFs to 123 00:10:29,741 --> 00:10:37,611 enumerate words we're going to use EGFs so that's not a difference in point of view 124 00:10:37,611 --> 00:10:43,342 and a difference in technique that we use to analyze variations. 125 00:10:43,342 --> 00:10:49,635 So again, here's just a, a summary for strings, which we considered last time. 126 00:10:49,635 --> 00:10:54,337 We considered them as unlabeled objects, we used OGF to enumerate them. 127 00:10:54,338 --> 00:10:57,804 A typical string is just a sequence of characters. 128 00:10:57,804 --> 00:11:03,120 So, the OGF is 1 over 1 minus Mz if there's N characters, those M to the N of 129 00:11:03,120 --> 00:11:06,936 them. For words we consider them as labeled 130 00:11:06,936 --> 00:11:11,657 objects, and used an EGF. And we had all these different 131 00:11:11,658 --> 00:11:16,157 representations. And now, when we're doing sequence for 132 00:11:16,157 --> 00:11:21,827 doing star product or re, relabel and all, all possible ways and our number of 133 00:11:21,827 --> 00:11:26,283 different words is e to the Mz but we get the same result out. 134 00:11:26,283 --> 00:11:31,398 So, we're going to be focusing on a balls and urns kind of representation in this 135 00:11:31,398 --> 00:11:39,146 lecture. Now, that's a brief introduction to what 136 00:11:39,146 --> 00:11:44,113 is a word, combinatorially.