1 00:00:03,320 --> 00:00:09,066 Next, we're going to talk about another important class of combinatorial classes 2 00:00:09,066 --> 00:00:13,393 that has to do with labelled objects. And now let's, let's explain the 3 00:00:13,393 --> 00:00:19,010 distinction between the labelled and the unlabeled ones that we talked about and 4 00:00:19,010 --> 00:00:24,305 then look at some interesting problems. so labeled combinatorial classes the 5 00:00:24,305 --> 00:00:28,890 objects have an atoms, but we consider the atoms to be all different. 6 00:00:28,890 --> 00:00:34,525 and so just to make that clear, we label them, consider them to always be labeled 7 00:00:34,525 --> 00:00:40,514 with the integers 1 through n. so for just [COUGH] schematically, for 8 00:00:40,514 --> 00:00:46,431 unlabeled objects you can consider those two objects to be different. They, they 9 00:00:46,431 --> 00:00:51,081 have a different structure. but when they're labeled there, [COUGH] 10 00:00:51,081 --> 00:00:55,660 there's different ways to label them that make different objects. 11 00:00:55,660 --> 00:01:00,240 For example, that's two different ways to label that square 12 00:01:00,240 --> 00:01:03,504 that. [COUGH] So, in the one on the left 1's 13 00:01:03,504 --> 00:01:08,688 connected to the 2 and 4. The one on the right, 1's connected to 3 and 4. 14 00:01:08,688 --> 00:01:12,898 They're different. in this one, it's, it's not always clear 15 00:01:12,898 --> 00:01:16,539 how many different ways there are to label things. 16 00:01:16,539 --> 00:01:22,219 in the one on the right, then there's three different ways to label that. 17 00:01:22,219 --> 00:01:26,151 Either one, two or, three, there's actually four ways. 18 00:01:26,151 --> 00:01:32,414 1, 2, 3, or 4 are going to be the ones that's connected to everybody else. 19 00:01:32,414 --> 00:01:38,042 so there's a big difference in studying the number of different objects, 20 00:01:38,042 --> 00:01:41,264 because labels provide so many more possibilities. 21 00:01:41,264 --> 00:01:46,484 in fact, when we're working with labeled objects, we use exponential generating 22 00:01:46,484 --> 00:01:51,060 functions for that reason and that'll become clear as we move along. 23 00:01:51,060 --> 00:01:54,518 All right. So lets look at some basic simple 24 00:01:54,518 --> 00:01:59,843 examples again of labelled objects. so that's what we call an urn and so an 25 00:01:59,843 --> 00:02:04,892 urn is a set of labelled atoms. So it's set, the orders don't make any 26 00:02:04,892 --> 00:02:08,419 difference, so again, there is only one of each kind. 27 00:02:08,419 --> 00:02:15,059 We could use this definition of unary numbers and later on, you'll see why we 28 00:02:15,059 --> 00:02:18,310 use this characterization of it, it'll be very clear. 29 00:02:18,310 --> 00:02:23,793 so there's only one of each kind, but now we're going to use exponential generating 30 00:02:23,793 --> 00:02:27,030 functions. So the exponential generating function 31 00:02:27,030 --> 00:02:31,726 for urns is e^z. That's one of each kind, Z to the N over 32 00:02:31,726 --> 00:02:37,160 N factorial summed is e to the z. So that's a first basic example. 33 00:02:37,160 --> 00:02:40,463 next one is a familiar one. It's permutations. 34 00:02:40,463 --> 00:02:43,626 A permutation is a sequence of labeled atoms. 35 00:02:43,626 --> 00:02:49,179 Sequence means the order is significant, atoms are labeled, so every possible 36 00:02:49,179 --> 00:02:53,045 ordering of the atoms is going to give a different object. 37 00:02:53,045 --> 00:02:59,020 So there's two different objects of size 2, either 1, 2 or 2, 1. Six different 38 00:02:59,020 --> 00:03:03,870 objects of size 3, 24 different objects of size 4, and so forth. 39 00:03:03,870 --> 00:03:08,983 so what's the exponential generating function for permutations? 40 00:03:08,983 --> 00:03:12,935 Well, there's N factorial permutations of size N. 41 00:03:12,935 --> 00:03:18,901 and so, the exponential generating function is that divided by n factorial 42 00:03:18,901 --> 00:03:23,085 times z to the n, which just leaves us with sum of z to the 43 00:03:23,085 --> 00:03:27,866 n or 1 / 1-z. That's another basic common combinatorial 44 00:03:27,866 --> 00:03:31,561 class. [COUGH] the N factorial serves to stop 45 00:03:31,561 --> 00:03:37,566 the generating function from blowing up too much because of all the different 46 00:03:37,566 --> 00:03:42,691 possibilities induced by the orderings. here's another one, 47 00:03:42,691 --> 00:03:46,317 a cycle. A cycle is a cyclic sequence of labeled 48 00:03:46,317 --> 00:03:50,094 atoms. so that's everything is connected in a 49 00:03:50,094 --> 00:03:57,270 circle but now there's fewer of each type that's and in fact, actually if you study 50 00:03:57,270 --> 00:04:03,993 it for a minute if you just fix on the largest to smallest element, then you can 51 00:04:03,993 --> 00:04:10,414 see that the others are permutation, so actually the counting sequence is N - 1 52 00:04:10,414 --> 00:04:14,341 factorial. so what's the exponential generating 53 00:04:14,341 --> 00:04:20,128 function for cycles? well, it's the sum of N - 1 factorial C 54 00:04:20,128 --> 00:04:25,995 to the N factorial, which everything cancels but an N, so it's natural log of 55 00:04:25,995 --> 00:04:31,094 1 / 1 - z since another basic combinatorial class. 56 00:04:31,094 --> 00:04:36,767 Now, it's a varied characteristic of analytic combinatorics to start with 57 00:04:36,767 --> 00:04:40,724 extremely simple derivations in classes like this. 58 00:04:40,724 --> 00:04:47,592 but then combine them in the interesting ways to provide answers to analytic 59 00:04:47,592 --> 00:04:52,520 problems of interest. so what about the analog to the Cartesian 60 00:04:52,520 --> 00:04:57,184 product operation? Well, it's it's much more complicated for 61 00:04:57,184 --> 00:05:01,952 labelled classes. when we take the product of two classes, 62 00:05:01,952 --> 00:05:06,804 so say, this first example. One we, we call it the star product. 63 00:05:06,804 --> 00:05:13,328 One star product of 1, 2, 3. what we're going to get is object of size 64 00:05:13,328 --> 00:05:18,430 4, but they have to be numbered from 1 to 4. 65 00:05:18,430 --> 00:05:21,673 And what the combinatorics requires is that 66 00:05:21,673 --> 00:05:26,643 we do that numbering 1 to 4 but we do it in all consistent ways. 67 00:05:26,643 --> 00:05:31,957 So, in this case, the second argument is a sequence that's in increasing order. 68 00:05:31,957 --> 00:05:37,410 So when we renumber, we have to put that in increasing order on each one of the 69 00:05:37,410 --> 00:05:41,620 possibilities. So we can assign 1 2, 3, and 4 to the 70 00:05:41,620 --> 00:05:48,039 first one and then the remaining labels, we assigned to the remaining three atoms 71 00:05:48,039 --> 00:05:53,415 but they have to be in increasing order. and here's a more com, complicated 72 00:05:53,415 --> 00:05:58,645 example where we take the star product of a 2-cycle and a 3-cycle. 73 00:05:58,645 --> 00:06:03,958 Again, when we do that we get five. we have objects consist of five atoms 74 00:06:03,958 --> 00:06:08,934 that have the structure set of 2-cycle and a 3-cycle. 75 00:06:08,934 --> 00:06:16,267 The atoms have to all be numbered with 1 through 5 and we have to do it in all 76 00:06:16,267 --> 00:06:20,981 possible ways. So in this case there is you can choose 77 00:06:20,981 --> 00:06:25,782 any label, there is only one way to label the 2-cycle. 78 00:06:25,782 --> 00:06:32,504 and you can choose five choose two or ten different ways to label the two cycle. 79 00:06:32,504 --> 00:06:39,926 so first row, first column is with the top one being 1, you can have 2, 3, 4, 5, 80 00:06:39,926 --> 00:06:44,557 to the bottom one. second column, the top one being 2, 3, 81 00:06:44,557 --> 00:06:48,424 and 4. Then, after you've labeled the two cycle, 82 00:06:48,424 --> 00:06:54,490 then you take the remaining labels and assign them to the 3-cycle, but you have 83 00:06:54,490 --> 00:07:00,486 to be consistent and maintain the order. So for example with 3, 4, in this case 84 00:07:00,486 --> 00:07:06,905 with 3, 4 is labeled 2-cycle the remaining labels are 1, 2, and 5 and they 85 00:07:06,905 --> 00:07:11,611 have to go in that order. So that's the star product operation 86 00:07:11,611 --> 00:07:17,812 relabeled in all consistent ways. and when we get to applications we'll see 87 00:07:17,812 --> 00:07:24,309 why that's not just intuitive that's fundamental to working with labeled 88 00:07:24,309 --> 00:07:27,515 objects. so we'with labelled objects, since you 89 00:07:27,515 --> 00:07:33,297 can tell the difference in the ordering we have more basic constructions and it's 90 00:07:33,297 --> 00:07:38,047 a much richer set of operations that we are going to work with. 91 00:07:38,047 --> 00:07:43,760 And actually the ones that I'm giving both for labelled and unlabelled are only 92 00:07:43,760 --> 00:07:47,408 the beginning. research is ongoing and people have 93 00:07:47,408 --> 00:07:52,640 developed many, many more constructions that I'm going to present here. 94 00:07:52,640 --> 00:07:56,544 so [COUGH] we talked about, so, plus is the same. 95 00:07:56,544 --> 00:08:04,452 You take copies of objects from A and B, but you relabel in all consistent ways. 96 00:08:04,452 --> 00:08:09,257 star product is where you take ordered pairs of copies. 97 00:08:09,257 --> 00:08:14,667 sequence is similar to what we did for unlabeled. 98 00:08:14,667 --> 00:08:21,756 it's A + A star A + A star star A, and so forth. but you could have sets of objects 99 00:08:21,756 --> 00:08:27,749 like we did for urns and you can have objects arrange in a cyclic sequence for 100 00:08:27,749 --> 00:08:31,403 example. so those are the constructions that we 101 00:08:31,403 --> 00:08:37,468 can use richer set of constructions and leads to much richer set of objects to 102 00:08:37,468 --> 00:08:41,269 talk about. and again, what's important is that we 103 00:08:41,269 --> 00:08:45,698 have a transfer theorem. If we have combinatorial classes and we 104 00:08:45,698 --> 00:08:49,820 know they're EGFs, then the whatever operations we pick from 105 00:08:49,820 --> 00:08:54,423 that list, we're going to know the EGF or the result of that operation. 106 00:08:54,423 --> 00:08:57,858 As before, if we do disjoint union, we have the sum. 107 00:08:57,858 --> 00:09:03,904 if we do the labeled star product we have the product to the generating functions. 108 00:09:03,904 --> 00:09:08,163 if we do a sequence of k objects, it's like A(z)^k. 109 00:09:08,163 --> 00:09:13,660 a sequence of any number of objects is summing those is 1 over 1-. 110 00:09:13,660 --> 00:09:21,650 If we have a set, it's A(z)^k over k factorial and so that's a set of size k. 111 00:09:21,650 --> 00:09:25,208 And a set of any size, is sum of those is e^A(z). 112 00:09:26,340 --> 00:09:31,798 cycle is A(z)^k over k and cycles of any length. 113 00:09:31,798 --> 00:09:37,881 Cycles of size k is, that cycles of any length is log of 1 over 1 - A(z). 114 00:09:37,881 --> 00:09:44,431 So, so if we know the generating function for combinatorial class, when we perform 115 00:09:44,431 --> 00:09:50,280 one of these operations, we know the generating function for the result and 116 00:09:50,280 --> 00:09:55,582 that's extremely powerful transfer theorem that's a basis for the 117 00:09:55,582 --> 00:09:59,079 symbolic method. So let's just look at the basic 118 00:09:59,079 --> 00:10:03,681 constructions of the basic objects using these operations. 119 00:10:03,681 --> 00:10:12,058 So urns urn is a set of atoms and that immediately translates to e^z from the 120 00:10:12,058 --> 00:10:17,466 transfer theorem, for sets. and as we saw that, that gives a comic 121 00:10:17,466 --> 00:10:22,793 sequence Un = 1. cycles a cycle is this, a cycle of atoms 122 00:10:22,793 --> 00:10:28,765 and again, immediately from the transfer theorem, that tells us that the 123 00:10:28,765 --> 00:10:36,190 generative function is log 1 / 1 - z and therefore, the comic sequence is n 124 00:10:36,190 --> 00:10:41,760 factorial times coefficieny to the n in that, which is n - 1 factorial. 125 00:10:41,760 --> 00:10:47,443 permutations as with bit strength is two different ways to define permutations. 126 00:10:47,443 --> 00:10:53,127 You can say, a permutation is a sequence of atoms and then read immediately from 127 00:10:53,127 --> 00:10:58,742 the transfer theorem, that the generative functions for permutations has to be one 128 00:10:58,742 --> 00:11:04,563 of 1 - z or you can say, a permutation is either empty or the store product of an 129 00:11:04,563 --> 00:11:09,161 atom in a permutation. and that will generate all possible 130 00:11:09,161 --> 00:11:14,094 permutations. That immediately translates to P(z) = 1 + 131 00:11:14,094 --> 00:11:19,026 z * P(z). and then solving for P(z) gives the same 132 00:11:19,026 --> 00:11:22,486 result. and the, and then the kind of sequence is 133 00:11:22,486 --> 00:11:28,450 N factorial times the coefficient Z to the N in that, which is just N factorial. 134 00:11:28,450 --> 00:11:34,683 So those are just the starting point for some basic constructions. 135 00:11:34,683 --> 00:11:40,356 the proofs of the transfer theorems, again, they come just immediately from 136 00:11:40,356 --> 00:11:46,073 the definitions and from generating function, counting, the way that we 137 00:11:46,073 --> 00:11:51,067 talked about earlier. so A+ again, they separate into the 138 00:11:51,067 --> 00:11:55,048 disjoint sets and that immediately gives the result. 139 00:11:55,048 --> 00:12:01,417 for star, it's a convolution of, of the type that we've seen before but let's 140 00:12:01,417 --> 00:12:05,899 take a look. so to do all different relabellings, so 141 00:12:05,899 --> 00:12:12,992 we take one alpha from A and beta from B, and to do all different relabellings it's 142 00:12:12,992 --> 00:12:18,861 alpha plus beta choose alpha just like with the example I did with the cycles. 143 00:12:18,861 --> 00:12:23,689 and then [COUGH] so that's a number of ways you can relabel. 144 00:12:23,689 --> 00:12:29,320 and then the size of [COUGH] the, an object composed of an alpha and a beta is 145 00:12:29,320 --> 00:12:34,452 Z to the alpha plus beta. And again, the factorials for alpha plus 146 00:12:34,452 --> 00:12:39,371 beta factorial. and then if you take that complicated sum 147 00:12:39,371 --> 00:12:45,358 the alpha plus beta factorials cancel. and you can seperate out Z to the alpha 148 00:12:45,358 --> 00:12:50,990 or alpha vectorial Z to beta over beta factorial to get that it's a product. 149 00:12:50,990 --> 00:12:54,843 Again, that's a complicated convolution, but this is the only time we have to do 150 00:12:54,843 --> 00:12:58,608 it. and for the other operations I have a 151 00:12:58,608 --> 00:13:02,997 slide that's gotten lots of dense math on it, 152 00:13:02,997 --> 00:13:10,311 but its pretty simple. so as we saw before A(z)^k is the number 153 00:13:10,311 --> 00:13:16,702 of k-sequences as a generating function for exponential generating function for 154 00:13:16,702 --> 00:13:23,401 the number of k-sequences of size N so and then, that's just as we saw several 155 00:13:23,401 --> 00:13:26,706 times before. and if you add those all up for a 156 00:13:26,706 --> 00:13:32,967 sequence of any length you get 1 / 1 - z. But if you have all the k-sequences of 157 00:13:32,967 --> 00:13:40,388 size N, then you're going to have each k-cycle of size N appear k times there in 158 00:13:40,388 --> 00:13:46,110 each cyclic orientation. So that means that A(z) over, to the k 159 00:13:46,110 --> 00:13:53,621 over k is the EGF for k-cycles for cycles with k objects. And then summing all 160 00:13:53,621 --> 00:13:58,450 those up gives the result for cycles of any length. 161 00:13:58,450 --> 00:14:04,883 Similarly, if you have all k-sequences of size N, you're going to have all sets up 162 00:14:04,883 --> 00:14:10,364 here, k factorial times. So that means that A(z) to the k over k 163 00:14:10,364 --> 00:14:16,877 factorial is the exponential generating function for the number of k sets of size 164 00:14:16,877 --> 00:14:23,152 N and then summing all those up give the result that for any set, it's E to the A 165 00:14:23,152 --> 00:14:26,488 of Z. so these are worthy of study, but they're 166 00:14:26,488 --> 00:14:31,727 very straightforward and immediate from the definitions and the basic ideas of 167 00:14:31,727 --> 00:14:36,956 generating function counting. so let's look at much more interesting 168 00:14:36,956 --> 00:14:40,188 example. So the idea is that we have these 169 00:14:40,188 --> 00:14:44,426 operations, we can combine them in various interesting ways. 170 00:14:44,426 --> 00:14:50,245 And actually, as we'll see in part 2 there's every way of combining these 171 00:14:50,245 --> 00:14:56,422 basic operations leads to a combinatorial class that people have studied in detail. 172 00:14:56,422 --> 00:15:01,020 and, but there's many more operations we can throw in as well. 173 00:15:01,020 --> 00:15:04,188 So let's look at, this is a famous one. 174 00:15:04,188 --> 00:15:09,275 How many different sets of cycles are there of labeled atoms? 175 00:15:09,275 --> 00:15:15,562 For example, for [COUGH] three atoms, you could have a cycle of size 3 and 176 00:15:15,562 --> 00:15:22,814 there's two different ways to label that, or you could have one cycle of size 1 and 177 00:15:22,814 --> 00:15:29,349 another cycle of size 2 and there's three possibilities for labeling that, 178 00:15:29,349 --> 00:15:36,021 or you could have three cycles of size 1. So it's a total of six sets of cycles of 179 00:15:36,021 --> 00:15:39,718 labeled atoms. and if you work it out for four, 180 00:15:39,718 --> 00:15:44,914 on the right is all the possibilities of sets of cycles of four atoms. 181 00:15:44,914 --> 00:15:50,853 You can have them be four singles and cycles or you could have 1-cycle of size 182 00:15:50,853 --> 00:15:57,163 4 and there's six different ways to label that one or you could have something in 183 00:15:57,163 --> 00:16:01,098 between all the possibilities are laid out here. 184 00:16:01,098 --> 00:16:07,705 you might recognize the numbers and yes, there's N factorial sets of cycles of N 185 00:16:07,705 --> 00:16:11,864 labelled atoms. And what we'll look at next is how we 186 00:16:11,864 --> 00:16:16,891 learn that from analytic combinatorics. And it's not just instructive, it forms 187 00:16:16,891 --> 00:16:21,731 the basis for us to solve problems that we couldn't otherwise solve as you'll 188 00:16:21,731 --> 00:16:25,943 see. So let's use are, regular methodology, we 189 00:16:25,943 --> 00:16:32,415 have to articulate what our class is. So it's P star, is the class of all sets of 190 00:16:32,415 --> 00:16:38,725 cycles of atoms the number of atoms is the size, the EGF, as usual brings 191 00:16:38,725 --> 00:16:45,682 together this coefficient is even over N factorial, is the number of sets of 192 00:16:45,682 --> 00:16:52,235 cycles of i and atoms the atoms are just labeled atoms for label classes, it's 193 00:16:52,235 --> 00:16:56,560 always the same. [COUGH] What's our construction? 194 00:16:56,560 --> 00:17:02,104 A, nothing more than saying a set of cycles of atoms is a set of cycles of 195 00:17:02,104 --> 00:17:08,097 atoms. that's what, that's what the math says, and it immediately translates from 196 00:17:08,097 --> 00:17:14,466 the transfer theorems to cycle of z translates to natural log 1 over 1 - z. 197 00:17:14,466 --> 00:17:20,160 Set of something is E to that power and that's just 1 over 1 - z. 198 00:17:20,160 --> 00:17:26,798 so therefore the counting sequence is N factorial is N factorial, that's the same 199 00:17:26,798 --> 00:17:31,667 as for permutations. and again, that's a very quick result, it 200 00:17:31,667 --> 00:17:37,568 just comes from the combinatorial description a set of cycles that we can 201 00:17:37,568 --> 00:17:43,469 get the generating function for sets of cycles immediately from the transfer 202 00:17:43,469 --> 00:17:47,448 theorem. Now, this is a well-known combinatorial 203 00:17:47,448 --> 00:17:50,912 bijection. a permutation is a set of cycles. 204 00:17:50,912 --> 00:17:56,786 And to see that, you'd start anywhere. Say we'll start at four so here, we have 205 00:17:56,786 --> 00:18:01,681 the permutation and then we have the index of the sequence. 206 00:18:01,681 --> 00:18:07,178 Where is it in the sequence? So if we start at the fourth thing in the 207 00:18:07,178 --> 00:18:13,580 sequence or the fourth enter in the permutation, it says 10 so we go to 10. 208 00:18:13,580 --> 00:18:19,142 and ten says [COUGH] that tenth entry in the sequence is 6 so we go to 6. 209 00:18:19,142 --> 00:18:24,156 and the sixth entry in the sequence is 15, so we go to 15. 210 00:18:24,156 --> 00:18:29,444 and the point is as you see from this example, eventually, you're going to get 211 00:18:29,444 --> 00:18:36,169 back to where you started that's a cycle. we can depict that thing just like this. 212 00:18:36,169 --> 00:18:41,650 just when you go from 4 to 10 to 6 to 15 back to 4. 213 00:18:41,650 --> 00:18:47,953 and if you do that if you've already done it, if you've already done an item and 214 00:18:47,953 --> 00:18:53,863 ignore it otherwise, do this process. You can convert any permutation into a 215 00:18:53,863 --> 00:19:00,010 set of cycles and it's a worthwhile exercise to figure out how to reconstruct 216 00:19:00,010 --> 00:19:05,920 a permutation from a set of cycles, but that's a well-known bijection. 217 00:19:05,920 --> 00:19:10,976 So that brings us to our first actual problem that you might not know the 218 00:19:10,976 --> 00:19:15,844 answer to or you might, because it's a classical problem but we'll get to one 219 00:19:15,844 --> 00:19:20,395 you don't know the answer to. and that's the derangements problem and 220 00:19:20,395 --> 00:19:25,769 this is a famous problem from the the eighteenth century and usually well, 221 00:19:25,769 --> 00:19:30,900 at that time, it was cast in this way. So, you have in people, who go to the 222 00:19:30,900 --> 00:19:36,100 opera, and they leave their hat on a shelf in the cloak room, but they all 223 00:19:36,100 --> 00:19:40,106 look the same. and so when they leave, they each grab a 224 00:19:40,106 --> 00:19:43,352 hat at random. And the question is, what's the 225 00:19:43,352 --> 00:19:46,710 probability that nobody gets their own hat? 226 00:19:46,710 --> 00:19:53,026 so [COUGH] in, in, in terms of combinatorics 227 00:19:53,026 --> 00:19:58,260 we refer to this as a derangement. Nobody gets their own hat, that means 228 00:19:58,260 --> 00:20:03,641 there's no singleton cycle. so that means that, that getting, getting 229 00:20:03,641 --> 00:20:08,580 your own hat means if you're in position four it's the, fourth item. 230 00:20:08,580 --> 00:20:15,288 [COUGH] so, and that's a singleton cycle. so the question is what's the probability 231 00:20:15,288 --> 00:20:20,670 that, that a permutation is a derangement or how many derangements are there? 232 00:20:20,670 --> 00:20:29,158 now just as an amusing aside this problem has been posed in the centuries since in 233 00:20:29,158 --> 00:20:32,830 many different ways. that's the classical opera way. 234 00:20:32,830 --> 00:20:37,998 so some people say, well, a professor returns exams to students and by passing 235 00:20:37,998 --> 00:20:42,010 them out at random. What's the probability that nobody gets 236 00:20:42,010 --> 00:20:46,628 their own exam? so lot's of people use that way of posing 237 00:20:46,628 --> 00:20:52,556 a problem in combinatorics classes or a more fun way to do it is the drunken 238 00:20:52,556 --> 00:20:58,624 sailor. so you have a group of sailors that are a bit inebriated and whenever, 239 00:20:58,624 --> 00:21:03,352 when they get back home, they wind up sleeping in a random cabin. 240 00:21:03,352 --> 00:21:08,947 So what's the probability that nobody winds up in their own cabin or maybe more 241 00:21:08,947 --> 00:21:14,906 relevant to college students is got an n students that live in a single room and 242 00:21:14,906 --> 00:21:20,129 they get in a state of inebriation. what's the probability that nobody ends 243 00:21:20,129 --> 00:21:23,812 up in their own room? that's all the same problem. 244 00:21:23,812 --> 00:21:28,700 and to solve that problem, what we want to do is to count derangements. 245 00:21:28,700 --> 00:21:35,679 So derangements or permutations with no singleton cycles. So this is our table of 246 00:21:35,679 --> 00:21:41,728 sets of cycles, which are equivalent to permutations with the ones that have 247 00:21:41,728 --> 00:21:47,311 singleton cycles graded out. So there's nine permutation of side four 248 00:21:47,311 --> 00:21:53,282 that have no singleton cycles. probability that nobody [COUGH] winds up 249 00:21:53,282 --> 00:21:57,160 with their own hat is only four, it's nine over 24. 250 00:21:57,160 --> 00:22:01,076 and so this maybe is not a familiar sequence, 251 00:22:01,076 --> 00:22:06,299 so let's see how to analyze that with the symbolic method. 252 00:22:06,299 --> 00:22:11,745 now we just go through our [COUGH] our, our regular regiment. 253 00:22:11,745 --> 00:22:17,534 We're going to define D to be the class of all derangements size is number of 254 00:22:17,534 --> 00:22:23,545 atoms standard labelled atoms. generating function is always the same 255 00:22:23,545 --> 00:22:28,295 exponential generating function. And so, what's the combinatorial 256 00:22:28,295 --> 00:22:32,889 construction? so one way to phrase it is this way. 257 00:22:32,889 --> 00:22:39,322 A derangement is a set of cycles where the length of the cycles is greater than 258 00:22:39,322 --> 00:22:45,096 one and we just indicate that with cycle greater than one of atoms. 259 00:22:45,096 --> 00:22:51,612 A permutations is a set of cycles of atoms this one excludes the ones of 260 00:22:51,612 --> 00:22:56,012 length one. [COUGH] that one immediately transfers, 261 00:22:56,012 --> 00:23:02,214 so derangements or permutations in those singleton cycles is what it says. and so 262 00:23:02,214 --> 00:23:07,703 set is z to the whatever it is, and what's the generating function for the 263 00:23:07,703 --> 00:23:13,691 cycles of length greater than one. Well, generating function for all cycles is z + 264 00:23:13,691 --> 00:23:20,820 z^2 / 2 + z [INAUDIBLE] like that, and we're just leaving out the first term. 265 00:23:20,820 --> 00:23:29,970 so that immediate translation and that's the same as log of one over one minus z 266 00:23:29,970 --> 00:23:36,205 minus z. that [COUGH] is that infinite series is 267 00:23:36,205 --> 00:23:37,545 exactly log(1/r-z)-z). one over one minus z minus z. 268 00:23:37,545 --> 00:23:40,784 And if we simply that, we get e^-z(-z/(1-z)). 269 00:23:40,784 --> 00:23:45,251 / 1 - z. We need translation to the generating 270 00:23:45,251 --> 00:23:50,724 function. another way to derive it which maybe is 271 00:23:50,724 --> 00:23:57,974 even easier to understand is we can say that a what is a permutation? 272 00:23:57,974 --> 00:24:03,990 A permutation is a set of singleton cycles crossed with a derangement. 273 00:24:03,990 --> 00:24:07,527 and so, that's, that's another way to phrase it. 274 00:24:07,527 --> 00:24:11,499 And then that one immediately translates to e to the z, 275 00:24:11,499 --> 00:24:15,903 d of z equals one over one minus z and solve for d of z, you get the same 276 00:24:15,903 --> 00:24:18,936 result. so symbolic method gives us the 277 00:24:18,936 --> 00:24:23,124 generating function. Now, extracting coefficients from this 278 00:24:23,124 --> 00:24:29,116 one is a little more complicated. we actually did it already in our lecture 279 00:24:29,116 --> 00:24:32,849 on asymptotics. so that's the result is that it's 280 00:24:32,849 --> 00:24:36,955 asymptotics to one over e. and let's just look at each of the 281 00:24:36,955 --> 00:24:39,340 elements of that. So first of all 282 00:24:39,340 --> 00:24:44,898 we're looking since we want a probability, it's convenient that we're 283 00:24:44,898 --> 00:24:50,998 using exponential generating functions and our probability denominator is n 284 00:24:50,998 --> 00:24:55,090 factorial. so we're taking advantage of that 285 00:24:55,090 --> 00:24:59,283 [COUGH] coincidence. It's not really a coincidence, but in this case it it works 286 00:24:59,283 --> 00:25:01,482 out. So to get the probability, we just look 287 00:25:01,482 --> 00:25:05,982 at the coefficient of z to the n in the generating function not in factorial time 288 00:25:05,982 --> 00:25:08,590 z to the n, because it's going to divide it right out. 289 00:25:08,590 --> 00:25:11,924 so [COUGH] that's d to the n over n factorial. 290 00:25:11,924 --> 00:25:17,800 So, and what's that coefficient? Well, it's a convolution e to the minus z times 291 00:25:17,800 --> 00:25:21,611 one one, one minus z. you, you just do the convolution of the 292 00:25:21,611 --> 00:25:27,725 coefficient of the z to the n in that is the sum of k from zero to n and minus one 293 00:25:27,725 --> 00:25:32,820 to the k over k factorial. and that's a straight convolution and 294 00:25:32,820 --> 00:25:38,951 then that's a sum that we looked at as one of our examples for bounding the tail 295 00:25:38,951 --> 00:25:44,800 in the asymptotics lecture to show that's asintotic to one over e, that's very 296 00:25:44,800 --> 00:25:49,463 close to one over e. we're going to look at an easier way to 297 00:25:49,463 --> 00:25:56,784 get this at the end of this lecture. but the symbolic method gets us there and 298 00:25:56,784 --> 00:26:02,315 then provides a practical solution to this kind of problem. 299 00:26:02,315 --> 00:26:07,196 the actual chance that if you go to a party and 300 00:26:07,196 --> 00:26:13,215 get yourself in a state of inebriation and wind up in a random room. 301 00:26:13,215 --> 00:26:19,315 you've got a pretty good probability that nobody ends up in their own room, 302 00:26:19,315 --> 00:26:22,314 36%. or maybe a way to tell your parents about 303 00:26:22,314 --> 00:26:27,271 this problem is when students graduate and throw their hats in the air and 304 00:26:27,271 --> 00:26:31,800 everybody catches a random hat, 36% probability nobody gets their hats back. 305 00:26:31,800 --> 00:26:37,356 actually your parents probably want you to get your, or the rental company 306 00:26:37,356 --> 00:26:40,413 probably wants you to get your own hat back. 307 00:26:40,413 --> 00:26:46,178 and so there's the idea of generalized derangements so if, if you've got a 308 00:26:46,178 --> 00:26:51,110 random hat, you can always get your own hat back by following the cycle. 309 00:26:51,110 --> 00:26:56,181 So student four wound up with ten's hat, she can go to ten, and ten's got six's 310 00:26:56,181 --> 00:27:02,502 hat, then she can go to six. Six has 15's hat, then she go to 15 and 15 there's her 311 00:27:02,502 --> 00:27:06,089 hat. so, following the cycle we'll get your 312 00:27:06,089 --> 00:27:11,722 hat back. so then, now we have the more general problem, what's the probability 313 00:27:11,722 --> 00:27:17,285 that all cycles are a blank bigger than N, that everybody is going to have to 314 00:27:17,285 --> 00:27:23,129 would have to follow at least N talk to at least N friends or N people, N random 315 00:27:23,129 --> 00:27:28,763 people to get their hat back, so that's a generalized derangements problem. 316 00:27:28,763 --> 00:27:33,340 What's the probability that all cycles are a blank bigger than N? 317 00:27:33,340 --> 00:27:39,600 now that problem it's much more difficult to analyze, but with the symbolic method 318 00:27:39,600 --> 00:27:44,864 we can get right to the generating function. So, it's just generalizing the 319 00:27:44,864 --> 00:27:51,195 arguement that I just gave D sub N is the class of all generalized deragements. no 320 00:27:51,195 --> 00:27:55,677 cycles of [INAUDIBLE] are equal to M and everything else is the same. 321 00:27:55,677 --> 00:28:01,741 so the construction is it's a set of cycles that are bigger than N of atoms. 322 00:28:01,741 --> 00:28:07,769 that translates directly to generating functions you just started Z to the M 323 00:28:07,769 --> 00:28:13,943 plus one, so it's the same series now starting at Z to the M plus one or that's 324 00:28:13,943 --> 00:28:19,535 log of one over one minus Z minus Z squared over Z, Z squared over two all 325 00:28:19,535 --> 00:28:24,295 the way up to Z to the M over M. And simplifying that, we have e to the 326 00:28:24,295 --> 00:28:29,360 minus z minus e squared over two minus z cubed over three and so forth up to z to 327 00:28:29,360 --> 00:28:33,911 the m over m over one minus z. So that's the generating function that we 328 00:28:33,911 --> 00:28:38,987 get immediately from the symbolic method. and very, and, and quite simpyl. 329 00:28:38,987 --> 00:28:45,177 without the symbolic method you might have some trouble getting to this 330 00:28:45,177 --> 00:28:51,007 generating function on your own. This, certainly other, certainly recent a 331 00:28:51,007 --> 00:28:56,910 lot of these things is possible to do, because what's behind the symbolic method 332 00:28:56,910 --> 00:29:01,372 is so simple. but the symbolic method really makes it 333 00:29:01,372 --> 00:29:04,900 so that a child can do it. so that's the 334 00:29:04,900 --> 00:29:09,978 a generating function equation. Now, to find the answer to this problem, 335 00:29:09,978 --> 00:29:16,610 we need to extract coefficients from this equation. Now, that one not so clear that 336 00:29:16,610 --> 00:29:22,289 would be an M way convolution, and you know, go ahead and try to extract 337 00:29:22,289 --> 00:29:27,379 coefficients from that one. So that's going to motivate, how could we 338 00:29:27,379 --> 00:29:33,427 find the coefficient, how can we estimate the coefficient of Z to the N in that 339 00:29:33,427 --> 00:29:39,107 complicated function that's going to motivate the second part of analytic 340 00:29:39,107 --> 00:29:44,344 commonotorics. The analytic transfer thorems, but that's the basic 341 00:29:44,344 --> 00:29:48,180 introduction to symbolic method for labeled objects.