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.