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. All the features of this course are available for free. It does not offer a certificate upon completion.
Compositions and Partitions
Loading...
审阅
4.7（25 个评分）
- 5 stars21 ratings
- 4 stars2 ratings
- 3 stars1 ratings
- 2 stars1 ratings
从本节课中
Combinatorial Structures and OGFs
Our first lecture is about the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.
教学方
Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Now we're going to look at compositions and partitions which are interesting
combinatorial objects that are well studied and well explained by the
symbolic method. So a composition is a simple idea, you
want to know the number of different ways to express n as the sum of positive
integers. So 2 could either be 1 plus 1 or 2, 3
could be 1 plus 1 plus 1, or 1 plus 2, or 2 plus 1, or just 3 and and so forth.
There's 8 ways to express 4 as a sum of positive integers, and 16 ways to express
5 as a sum of positive integers. and again it's easy to guess the pattern
there's 2 to the n minus 1 ways to express n as a sum of positive integers.
and that's easy to see with the symbolic method.
we start out by just considering integers as a combinatorial class.
So let i be the class of all positive integers.
so it's just like unary. so we take an atom and, and we give it
size one so that its generating function is z.
if we have seven of 'em then we have z to the 7th.
So the generating function for the class of integers is for every integer z to the
size of that integer or if we collect them by n i sub n z to the n.
And what is a positive integer? It's a sequence of at least one atom.
and so from the symbolic method, the generating function is z over 1 minus z.
so that means that there's one integer for all positive N.
and so that seems like a trivial derivation, but again [COUGH] making
these kinds of arguments for things that we understand so well lead us immediately
to be able to address more complicated problems with the same basic structure.
So now if we look at compositions what we can do is essentially think of a number
as being divided up into smaller pieces just by putting, if we have 12 dots, we
can put bars in with the 12 dots. And where, wherever the bars do, we
convert back to unary. So this is one composition, 1 plus 3 plus
1 plus 5 plus 2 equals 12. and if you look at it that way, and again
generating function you, in the standard way then a composition is just a sequence
of positive integers. so a sequence of positive intergers is a
composition. and but, in a grouping by N, we just need
to find a coefficient of z to the N. But sequence of positive integers, the
generating function is immediately 1 over 1 minus the generating function for
integers. And that one's z over 1 minus z, and if
you do the math, you get 1 minus z, over 1 minus 2z for the OGF for composition.
and then expanding that it's 2 to the n minus 2 to the n minus 1, or 2 to the n
minus 1 different compositions. so very straightforward to analyze this
combinatorial structure with the symbolic method.
you, and you can argue common authority if you want the zen minus 1 spaces
between N dots and every one of them could have a bar or not.
And so that's why there's 2 V N minus 1 possibilities in terms of number of
compositions. now what about partitions, what if we
don't care about the order same way as we did for trees?
so there's three, partitions of n-integers so we'll take the one that
goes in decreasing order. so all of these, 1 plus 1 plus 1 plus 2,
1 plus 2 plus 1 and so forth, they all represent the same partition, we'll keep
the one whose parts are not increasing. so anyway, just crossing out the ones
that appear more than once there's seven partitions of five elements expressed
again as a sum of unordered positive intergers.
It's not so obvious what the answer to this one is I think.
you know, look at the you're not going to find the 2 to the n minus 1 pattern here.
and people studied this, actually, quite a bit.
it's a thing known as Ferrer's diagram. Which is a 2D representation of the
partition where you just put the parts in order, just turn them on end and make
columns out of them. So if you have that partition, eight plus
eight and so forth, so that's parts are in decreasing order if you just turn the
dots on end, you get this Ferrers diagram for, of the 42 dots and it's
non-increasing, so it's a, a staircase down.
The question is, how many different diagrams are there?
this so the question is how many Ferrers diagrams are there with N dots?
And again this seems like a toy combinatorial question but actually it's
going to require the symbolic method and also saddle point asymptotics.
It's one of the most difficult asymptotic problems we'll run into.
and even, even so, not only that there's lots of applications where people want to
study these things. Not just analysis of algorithm but of
particle physics and its related to [UNKNOWN] and representation theories.
So you can find these objects studies in physics journals, not just math and
computer science journals. so we can do the symbolic method part
right here. so if we're going to study the class of
all partitions then the examples that we just showed it's simply the case that a
partition is multiset of positive integers.
so that means that sin, since there's only one integer of ea, ea, each kind
just directly from the transfer theorem that the symbolic method gives us we have
that expression for the generating function for the number of partitions.
and to find z to the n, and that again is quite a challenge, goes back to Hardy and
Ramanujan. and it's asymptotic to e to the pi
squared to 2n over 3 over 4n over the square root of 3.
and we'll later on touch on that. but for the present context we get right
to the problem with this symbolic method. And this is representative of the huge
number of problems where again with trees where a express different problems on
trees by having different kinds of restrictions on subtrees and for these
types of problems you can consider say compositions into m parts were restricted
compositions where you don't allow the integers just some subset of the integers
the same with partitions. You can do partitions into distinct parts
or restricted partitions where you've taken again any subset of the integers.
and all different kinds of problems ensue from considering these things.
Right down thee OGF for compositions into parts where the integers are all less
than or yule to r. And we'll look at a couple of other ones.
how many partitions are there into parts that are power of two?
well that's answer's an easy one, and we'll see why in just a second.
just from the symbolic method it's one plus z times one plus z squared, one plus
z to the fourth, and so forth. So we're looking for the coefficient of z
to the n in that. Well, if you just multiply the first two
terms that's 1 plus z plus z squared plus z cubed.
And then if you multiply that term by the z to the 4th, you can see the first four
terms come, and then z to the 4th times each one of them carries the series
through to seven. and then same for 8, so you can see
eventually, you just get sum of 1 plus z and so forth which is 1 over 1 minus z.
so it's just a number of ways to represent an integer as a sum of powers
of 2. there's only one, that's sometimes called
the computer scientist theorem. problems of this type are very well
studied. One of the most famous ones is due to
Polya. It's how many ways are there to change a
dollar. so let's say all you have is quarters,
how many ways are there to change the, a dollar.
well, so a dollar is, is 100 cents, and the number of ways to represent integer
with quarters is the sum of 25 is 1 over 1 minus z to the 25th.
So, coefficient is z to the 100th and that is just 1, that's only 1 z to the
100th term. So, the only way to change a dollar with
quarters is 1 with four quarters, so that's fine.
So what if you have dimes too. Well, turns out there's 3 ways to change
dollar with quarters and dimes. so, you can do that by trying to figure
out the possibilities or we can do it with generating functions too.
so, number of ways to change a dollar with quarters and dimes.
Is coefficient z to the 100 and 1 over 1 minus z to the 25th, 1 over 1 minus z to
the 10th. That's the number of ways to represent an
integer as the sum of 25s and 10s. so if you multiply out those power series
then and look for coefficients of z to the 100.
well, you're going to see there's going to be the 1 times a z to the 100th
out here. there'll be 2 z to the fiftieths
multiplied together. And then there'll be a z to the one
hundredth in this one times that one, so there's 3 different things.
in face what you can do is just throw out the irrelevant terms if you're just
looking for the coefficient of z to the one hundredth.
and then you get the 3 different ways. That's how many different ways to change
a dollar with quarters and dimes, either four quarters, two quarters and five
dimes or ten dimes. so now what if we so that's quarters,
quarters and dimes what about if we add nickels?
Well now if we add nickels you're going to say well, I, I want a computer
to do the symbolic analysis. Or what about pennies?
So how many different ways are there to change a dollar with quarters times
nickels and pennies. and so Polia had a key insight and wrote
a paper on this that shows that it's not difficult to calculate this for small
values by hand. Ant it's worth looking at 'cause it
illustrates a general phenomenon that very often, one thing that we can do with
generated functions is use them to get recurrences and then we can compute with
the recurrences to at least a known numerical value some of the things that
were studied. So what Polya pointed out was that if you
have generating function b of z is equal to another generating function a of z
times 1 over 1 minus z to the m. Then you multiply both sides by 1 minus z
to the m. and you get this following recurrent.
That b sub n equals b sub n minus m plus a sub n.
So that gives a way to go a head compute the small values.
So, for this example we're going to add the nickels and then the dimes and then
the quarters. Actually you can do this in other orders
too. So, add, and we're only doing, since
everything's a multiple of 5. we'll only look at the coefficients of Z
to the power that's a multiple of [INAUDIBLE] , so if we want to compute B
sub n so we're going to compute B sub 5 then we take A sub 5 and add B sub 0 to
it. if we want to compute B sub 10 then we
take A sub 10 and add B sub 5 to it, and so forth.
So for this line, its easier to figure out what happens.
We just, get[COUGH] N plus 1. so now it starts to get more interesting
for the next line. so now, if we want to know.
[COUGH] And if we start out with the first two are one, but now if we now want
to know b sub 15 then we go ten back so that's a sub 15.
that is the line below, plus b sub 5. So that gives 4, and then 2 plus 4 is 6,
4 plus 5 is 9 uh,, 6 plus 6 is 12, 9 plus 7 is 16 and so forth so add each 1 to the
1 2 back so to get this 1 we get 15 plus 49 is 64 and so forth.
Now, we can just fill in that whole line in that way and then finally the last
line that to get 25, we just go back to 0, and add a sub 25, and then well now we
can skip 5 at a time cause our goal is to get to 100.
so 49, 72, is 121, and then we have 242 different ways to change a dollar.
Well so it's an easy way to do a computation based on a generating
function even though computing this in general might be a bit of a challenge for
various different types of restrictions and if you want to do an, an exercise
start with this table and say the government switches to 20 cent pieces
instead of dimes for some reason. How many ways are there to change a
dollar and you can run through this computation in the same way in terms of
the
[UNKNOWN].
So, that's [UNKNOWN] change a dollar problem.
That's is an interesting problem in related to compostions and partitions.
I'll show you how we can use OGF to address some of these problems.
