0:04

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.

Â 2:47

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.

Â 4:37

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.

Â