Analytic Combinatorics teaches a calculus that enables precise quantitative predictions of large combinatorial structures. This course introduces the symbolic method to derive functional relations among ordinary, exponential, and multivariate generating functions, and methods in complex analysis for deriving accurate asymptotics from the GF equations.
Restricted Compositions
Loading...
From the course by Princeton University
Analytic Combinatorics
16 ratings
From the lesson
Applications of Rational and Meromorphic Asymptotics
We consider applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
Meet the Instructors
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
