Next were going to look at another set of combinatorial classes, that we studied in the early lectures. It's compositions and partisans. and that's starts out with we want to count the number of ways to express an integer in. As a sum of positive integers in lots of ways to show that that number is going to wind up two to the n minus one and these are the small examples. Let's see how that works with analytic combinatorics. to do it we start out just by doing the class of integers and so a class of integers is a sequence of positive integers of at least one object. This is counting in uniary we did this us example. So the generating function for that is z over one minus z uh,[COUGH] so there's a z to account for the[COUGH], at least one and then one of only minus z for the sequence of the rest of them. immediate from the symbolic method. and so in this case there's a singularity, it's a pole at one. and this function grows so its a little hard to see that singularity but its there. so we can compute the residue, the numerator evaluate at one is one the derivative of the denominator evaluate at one is also one. we just get 1, in the end is we get 1. there's one positive integer of each size. so to get compositions we'd just generalize that. A composition is a sequence of integers. and sequence is 1 over 1 minus, so the generating function by the symbolic method is 1 over 1 minus z over 1 minus z, which simplifies to 1 over, 1 minus z over 1 minus 2 z. Rational meramorphic so we're interested in the pole. Pole at one half this time. equals one half and goes to 0. that's single poles and the real line closest to the origin. we can compute evaluate the numerator. One half is one half. differentiate the denominator evaluate at one half and we get 2, so that turns out to be one fourth. and so the asymptotic's, the coefficient is divide those two. and get a one half in the exponential growth is 2 to the N, 1 over that. So the end result is 2 to the N minus 1, as expected for composition. Again, there's certainly lots of ways to get that result but with analytic commonetorics we can generalize in all sorts of ways. For example, suppose we restrict the size of the parts. How many ways are there to express N as a sum of ones and twos? well that one, also we can prove other ways that's the Fibonacci numbers. but it's instructive to look at it through analytic combinatorics. so that is a sequence of ones and twos and immediately translates to the familiar generating function for the Fibonacci numbers. and that one we've done these kinds of calculations in the earlier lecture. it's got its singularity set at fee hat, at minus fee. and we can computer the coefficient[COUGH] and used tricky Fibonacci, Golden Ratio identities to go ahead and compute the full asymptotic growth. so it's a constant times another exponential growth factor to the nth power in this case 1.618. but whatever set of things we use to pick to restrict the parts. this same method is going to work, it's just going to be a polynomial, a ratio of two polynomials. here's an interesting one that's covered in the book. How many ways are there to express N as a sum of primes? You might have trouble trying to figure out the[UNKNOWN] of this using elementary methods but with analytic[UNKNOWN] it's just a sequence of the, the z to the 2 for 1 for 1 factor for every prime. Now, this turns out to be a little more complicated than it looks and I'm leaving out some details that are discovered in the book, but, it is this generating function that's not quite a polynomial but turns out to be analytic function. It's quite a strange looking analytic function, and this is not doing all primes this is only doing up to 11 actually, there's an infinit number of singularities that this But there all further away from the origin than the dominant one which is on the real line and you can calculate where that one is even though there's an infinite number of primes. There's enough space between the primes that it's possible to prove this. and that immediately gives the a coefficient and the exponential growth. so and again there's as, as with many of these problems, there's going to be some periodic oscillations in next terms, but still it's going to give a quite accurate estimate. So that's compositions composed of primes. so again, I, you can look at page 298 299 in the book. To see some of the interesting calculations that I admitted. This one. isn't necessarily quit so simple as the other ones that we've talked about. and then there's partitions from a fixed set, which are called uh,[UNKNOWN] . so that's a famous example of that, is how many ways are that'll make change for n cents. so this the order doesn't matter, so it's just the set of things that you can choose. So $0.14, you can either take 14 pennies, or 9 pennies and a nickel, or 4 pennies and 2 nickels, or 4 pennies and a dime 4 different ways to make change for n cents. For 14 cents, for 15 cents, there's 6 different ways enumerated here. So, but this is easy with analytic common notorialitics. the construction is, a multi-set of pennies, nickels, dimes and quarters. the symbolic method immediately gives a generating function equation. One over one minus Z, one minus Z to the 5th, 1 minus Z to the 10th, 1 minus Z to the 25th. that's a polynomial, a complicated polynomial but it's a polynomial. That's again a meromorphic function, ratio of two analytic functions what we're interested in is the zero's, in this case, we have a higher order pole at z equals 1, so, this is the plot of this function it kind of mixes up the roots of[UNKNOWN] but at 1 there's a pole of order 5. So, we have to do a more complicated residue calcuation. in this case it's easy to show, with the limit form of the coefficient calculation, that the, since 1 minus z over 1 minus z to the t is equal to the sum of these things, then the limit is just 1 over t so immediately get out the result that the the coefficient is 1 over the product 1 times 5 times 10 times 25. it's the pole of order 4 it's the pole of order 4, that's the type of and so the asetonic to the coefficient is n cubed over 7500. so again, quite easily, from the symbolic method we get combinatorial construction, generating function asymptotics and coefficient. In this case the estimate is not exponentially accurate, cause it's an n squared term and so forth. and also the other poles are not so far away so this one n has to be Larger for it to become accurate. but still, we can calculate more terms if we want, and so forth, depending on how much calculation. our marimortic, marimorphic transfer theorem actually gives an exact equation for it, and then we can do asymptotics on that. but still, and again, if you want to choose different coins, or whatever, you can go ahead and immediately get asymptotic results for comparison. so that's more examples with compositions and partitions, showing how the meromorphic transfer theorem gives us, via analytic combinatorics very high level derivations from combinatorial constructions right through to asymptotic results.
