1 00:00:03,280 --> 00:00:06,168 Next we'll look at coefficient asymptotics. 2 00:00:06,168 --> 00:00:11,004 How do we get estimates of the coefficients of the generating functions 3 00:00:11,004 --> 00:00:14,766 that are so easily obtained through the symbolic method. 4 00:00:14,766 --> 00:00:20,368 fortunately it's the case that we often can immediately get the coefficient 5 00:00:20,368 --> 00:00:25,974 asymptotics through general transfer, analytic transfer thorems, and we've 6 00:00:25,974 --> 00:00:31,579 already seen some examples of transfer thorems that worked for a lot cases. 7 00:00:31,579 --> 00:00:37,627 For example, Taylors thorem is a transfer thorem. If you have a generating function 8 00:00:37,627 --> 00:00:44,781 f(z) and you know it's derivatives. then coefficient of z^N and f(z) is the nth 9 00:00:44,781 --> 00:00:50,533 derivative evaluated at zero over N factorial and, for lots of functions 10 00:00:50,533 --> 00:00:55,198 that's how we extract coefficients. That's how we get started with generating 11 00:00:55,198 --> 00:00:58,608 functions. we saw another example with rational 12 00:00:58,608 --> 00:01:04,926 functions and we talked about that in the generating functions lecture and also the 13 00:01:04,926 --> 00:01:08,669 asymptotics lecture. this is a special case just for 14 00:01:08,669 --> 00:01:14,109 simplicity on this slide. If f(z) and g(z) are polynomials, then 15 00:01:14,109 --> 00:01:22,814 the coefficient of z^N and the ratio of f(z) to g(z) depends on, [COUGH], the 16 00:01:22,814 --> 00:01:29,276 largest root of g, of the denominator. and if one over beta is that, 17 00:01:29,276 --> 00:01:36,072 then this expression, gives the it's should be asymptotic of 18 00:01:36,072 --> 00:01:39,781 the coefficient is z to the n in the ratio 19 00:01:39,781 --> 00:01:45,852 that's two beta times f of one over beta divided by g prime of beta, beta to the 20 00:01:45,852 --> 00:01:49,070 n. The growth is like a beta to the n and 21 00:01:49,070 --> 00:01:54,848 that's the constant if that root has multiplicity one and that we have a 22 00:01:54,848 --> 00:02:01,284 better form a more complicated formula that depends on the multiplicity if its 23 00:02:01,284 --> 00:02:05,711 got higher multiplicity. So those are two examples of transfer 24 00:02:05,711 --> 00:02:07,820 theorems. And, and we use those. 25 00:02:07,820 --> 00:02:14,006 the one I want to talk about today next is what's called a radius of convergence 26 00:02:14,006 --> 00:02:18,857 transfer theorem. and that covers the problems that we've 27 00:02:18,857 --> 00:02:24,843 talked about today and many others. but actually most of the transfer 28 00:02:24,843 --> 00:02:29,565 theorems that we use in real life are based on complex asymptotics. 29 00:02:29,565 --> 00:02:33,883 and we'll talk about those in a lot of detail in part two. 30 00:02:33,883 --> 00:02:40,089 but the radius and convergence one works for a lot of things and that helps give a 31 00:02:40,089 --> 00:02:44,340 coherent treatment of analytic combinatorics at this level. 32 00:02:44,340 --> 00:02:52,138 So here's the thorem. the ideal this thorem is that, the function 1 / 1 - z 33 00:02:52,138 --> 00:02:58,480 seems to arise a lot, and, the commonaltoric constructions, that we 34 00:02:58,480 --> 00:03:06,365 develop, so this is 1 - z to alpha power, where alpha's, not neccessarily, an 35 00:03:06,365 --> 00:03:13,050 integer, the only restriction is that it can't be a zero or a negative integer. 36 00:03:13,050 --> 00:03:19,582 And it, so gives us the, it in some sense, it, it generalizes the ratio on 37 00:03:19,582 --> 00:03:23,654 that I did before where g(z) was a polynomial. 38 00:03:23,654 --> 00:03:32,477 Now it's 1 - Z z, raised to alpha power. Coefficient of z to the N and f(z) / 1 - 39 00:03:32,477 --> 00:03:39,666 z alpha is asymptotic to f evaluated at one times N plus alpha - 1 choose N. 40 00:03:39,666 --> 00:03:46,899 And, that asymptotics to f evaluated at 1 N to the alpha - 1 over gamma of alpha. 41 00:03:46,899 --> 00:03:51,168 Gamma of alpha's a constant and I'll talk about it in a second. 42 00:03:51,168 --> 00:03:56,385 And I'm not going to go through the proof now, because most people are just going 43 00:03:56,385 --> 00:03:59,299 to want to apply this theorem. Not prove it. 44 00:03:59,299 --> 00:04:05,058 But it's not that difficult a proof really, it's a convolution that involves 45 00:04:05,058 --> 00:04:08,311 the generalized version of the binomial theorem. 46 00:04:08,311 --> 00:04:14,544 and also since the thing converges the sum of the first N coefficients converge 47 00:04:14,544 --> 00:04:18,909 exponentially to f(1). That's the, quick description of the 48 00:04:18,909 --> 00:04:23,093 proof of the first part. and then the, the second part is standard 49 00:04:23,093 --> 00:04:26,046 asymptotics. just using the definition of the 50 00:04:26,046 --> 00:04:30,538 generalized, binomial coefficient. And this function, the gamma function. 51 00:04:30,538 --> 00:04:35,706 if you don't know what the gamma function is here's just a real quick summary. 52 00:04:35,706 --> 00:04:38,660 It's a way to generalize the factorial function. 53 00:04:38,660 --> 00:04:44,316 it plays an important role in analytic combinatorics and the analysis of 54 00:04:44,316 --> 00:04:49,675 algorithms because it arises in transfer theorems just like this one. 55 00:04:49,675 --> 00:04:55,853 so for real z if you define this function, gamma z equals integral from 56 00:04:55,853 --> 00:05:00,170 zero to infinity t to the z minus one e to the minus t dt. 57 00:05:00,170 --> 00:05:05,438 Turns out, that function has the properties that we would want in 58 00:05:05,438 --> 00:05:10,221 generalizing the factorial. For example, gamma of alpha plus one 59 00:05:10,221 --> 00:05:16,138 equals alpha times gamma of alpha. Just like N factorial equals N times N 60 00:05:16,138 --> 00:05:20,895 minus one factorial. so and then, I, we work it out. 61 00:05:20,895 --> 00:05:27,882 gamma, gamma one equals one, so gamma of n plus one is exactly equal to n 62 00:05:27,882 --> 00:05:31,824 factorial. So for integers, it matches the 63 00:05:31,824 --> 00:05:36,687 factorial. but it always satisfies this property for 64 00:05:36,687 --> 00:05:44,004 any alpha and so gamma one equals one and one that comes up really a lot for us is 65 00:05:44,004 --> 00:05:49,470 gamma of one-half. If you want to compute gamma of one-half 66 00:05:49,470 --> 00:05:54,597 So that takes z equals one-half in there and then you get something like the 67 00:05:54,597 --> 00:05:58,303 normal and you compute it to be the square root of pi. 68 00:05:58,303 --> 00:06:04,110 [COUGH] and so again one-half equals square root of pi is a value that that we 69 00:06:04,110 --> 00:06:08,682 want to know because we applied this thing with alpha equals one-half, that's 70 00:06:08,682 --> 00:06:13,923 square root of one minus z. so that's a transfer theorem that works 71 00:06:13,923 --> 00:06:19,982 whenever we have a convolution of some function with one minus e to the alpha. 72 00:06:19,982 --> 00:06:26,526 And that turns out not to come up a lot. just a little more generally if the 73 00:06:26,526 --> 00:06:32,636 radius of convergence is bigger than a row and if a row is not equal to zero, so 74 00:06:32,636 --> 00:06:38,899 just applying this to zero of a row, plug in, in zero over row in this theorem then 75 00:06:38,899 --> 00:06:44,169 we get slightly more general. You could do one over one minus zero over 76 00:06:44,169 --> 00:06:51,480 row to the alpha and that pulls out a row to the end in the [COUGH] in the 77 00:06:51,480 --> 00:06:52,846 asymptotics. so, 78 00:06:52,846 --> 00:06:57,658 And that, that's just an elementary calculation to see, where that comes 79 00:06:57,658 --> 00:07:00,845 from. so that corollary is the one, that, now 80 00:07:00,845 --> 00:07:04,422 we'll really be interested in. so that's the theorem. 81 00:07:04,422 --> 00:07:09,170 if we have a generating function of that form, we know the asymptotics. 82 00:07:09,170 --> 00:07:15,950 and that applies to the two major problems that we've talked about so far 83 00:07:15,950 --> 00:07:23,663 in this lecture for catalan numbers so t of z equals one over 2z 1-square to 1-4z. 84 00:07:23,663 --> 00:07:31,292 So there is tiny complication because of first term has the cancel out but 85 00:07:31,292 --> 00:07:38,327 ignoring that what we're using is alpha equals one half in this alpha equals 86 00:07:38,327 --> 00:07:40,870 minus one half. So that's what. 87 00:07:40,870 --> 00:07:46,593 One minus zero over rho to the minus one half in the denominator that square root 88 00:07:46,593 --> 00:07:51,129 and rho equals a fourth, so that's square root of one minus 4Z, 89 00:07:51,129 --> 00:07:56,643 And then after this case is just a constant, just half up-front, and so we 90 00:07:56,643 --> 00:08:02,157 wind up needing gamma of minus one half and then that's two times gamma, of, of 91 00:08:02,157 --> 00:08:07,322 one halfs, just because gamma, alpha plus one equals alpha gamma of alpha, minus 92 00:08:07,322 --> 00:08:11,440 two square root of pi. So you plug it all in, and then, 93 00:08:11,440 --> 00:08:17,669 maybe it's easiest to think about it by just multiplying both sides by Z and then 94 00:08:17,669 --> 00:08:22,287 apply these exactly. it's not hard to finish the calculation 95 00:08:22,287 --> 00:08:26,705 to show that This transfer theorm immediately gives us 96 00:08:26,705 --> 00:08:33,101 the asymtonic's of the catalan numbers, So, one transfer theorem to get the 97 00:08:33,101 --> 00:08:37,438 generating function. Another transfer theorem, the analytic 98 00:08:37,438 --> 00:08:41,177 one to get the asymptotics of the coefficients. 99 00:08:41,177 --> 00:08:45,590 and this same theorem works for the arrangement problem. 100 00:08:45,590 --> 00:08:51,777 so different numbered, generalized arrangements, we had this complicated 101 00:08:51,777 --> 00:08:57,443 function. not so complicated with this transfer theorem, now we have alpha 102 00:08:57,443 --> 00:09:03,332 equals one, we have rho equals one, our function is just E to the minus E, so all 103 00:09:03,332 --> 00:09:08,998 we need to do is evaluate F at one, that's E to the minus one minus one half, 104 00:09:08,998 --> 00:09:14,888 up to one over N that's H Sebem, that immediately gives the asymptotics, E to 105 00:09:14,888 --> 00:09:19,700 the minus H sub M. so do problems that the first one a lotta 106 00:09:19,700 --> 00:09:24,761 calculations to get there. second one we don't even know how to get 107 00:09:24,761 --> 00:09:28,086 there. immediately through this analytic 108 00:09:28,086 --> 00:09:33,844 transfer theorem we can get the result. And this is just really, just the 109 00:09:33,844 --> 00:09:39,308 beginning. What Part two is going to be devoted to, is the idea of really 110 00:09:39,308 --> 00:09:44,697 universal laws that we can get from transfer theorems based on complex 111 00:09:44,697 --> 00:09:48,567 asymptotics. And I'll just talk through one, there's 112 00:09:48,567 --> 00:09:52,514 lot of technical details, just to give you some idea. 113 00:09:52,514 --> 00:09:58,206 If you have a system of combinatorial constructions or you have a bunch of 114 00:09:58,206 --> 00:10:04,656 classes and they are all interacting, and those operations indicated by OP zero, OP 115 00:10:04,656 --> 00:10:09,220 one, up to OP t Those can be sequencer, or sum or product operations. 116 00:10:09,220 --> 00:10:14,594 And you can create a whole linear system of combinatorial constructions. 117 00:10:14,594 --> 00:10:20,341 So very simple special cases, the binary tree one, where you got t on one side 118 00:10:20,341 --> 00:10:23,375 and. z times t times t on the other side. 119 00:10:23,375 --> 00:10:26,532 You could have a much more complicated thing. 120 00:10:26,532 --> 00:10:31,934 A cycle of binary trees of sets of well not those, but linear combinations of 121 00:10:31,934 --> 00:10:35,863 combinatorial classes. The whole system of combinatorial 122 00:10:35,863 --> 00:10:39,791 constructions. Those immediately transfer to a system of 123 00:10:39,791 --> 00:10:43,650 generating function equations with the symbolic method. 124 00:10:43,650 --> 00:10:48,938 Well that's good but those generating function equations might be quite 125 00:10:48,938 --> 00:10:54,498 complicated and difficult to solve. but in fact there's a, a method called 126 00:10:54,498 --> 00:10:59,719 Grobner basis elimination that reduces those all down to a single generating 127 00:10:59,719 --> 00:11:03,380 function equation. And not only that, there's a theorem 128 00:11:03,380 --> 00:11:08,737 called the Dimota-Lally-Woods theorem that shows there's an explicit solution 129 00:11:08,737 --> 00:11:12,557 to that equation. that equation's got the square root. 130 00:11:12,557 --> 00:11:18,098 and this is in the complex domain. and there's a process called singularity 131 00:11:18,098 --> 00:11:21,998 analysis that immediately gives a simple asymptotic form. 132 00:11:21,998 --> 00:11:27,128 So any combinatorial construction is asymptotic to a over two squared pi n 133 00:11:27,128 --> 00:11:31,233 cubed b to the n. Where a and b are constants that we can 134 00:11:31,233 --> 00:11:34,380 explicitly calculate from the construction. 135 00:11:34,380 --> 00:11:39,749 Its an amazing universal law. And you can find in older mathematical 136 00:11:39,749 --> 00:11:46,067 literature, hundreds of papers that come up with these these kinds of results. 137 00:11:46,067 --> 00:11:52,700 that this this one process covers. And that's just one example of universal 138 00:11:52,700 --> 00:11:58,070 laws that we see in analytic common towards there are many more. 139 00:11:58,070 --> 00:12:02,920 So that's an introduction to coefficient asymptotics.