0:04

Now we're going to look at the application of these techniques, to solve

some more difficult problems. so, for example, we talked about

compositions, which are a number of ways to write an integer as a sum of smaller

integers. so question that natural question is how

many compositions of n have k parts? So for 2 it's either 1 plus 1 or 2.

So there's 1 that has 1 part. There is 1 with 2 parts.

for 3 there's 1 plus 1 plus 1. that's one composition with three parts.

There's 1 plus 2 and 2 plus 1, that's two compositions with two parts and there's

three, that's one composition with one part.

There's always going to be one with ah,[COUGH] one part, and one with n

parts. and again now the binomial coefficients

are starting to show up again. and in fact, the number of pop

compositions with k parts is n minus 1 choose k minus 1.

we can ah,[COUGH] hypothesize that from this table.

and I also start including in these tables the cummulative cost and the

average which are easily computed computed from these numbers.

So, for example, for n equals 4, where the number of compositions with k parts,

for k equals 1, 2, 3, 4, is 1, 3, 3, 1. The total number of compositions is 8.

The cumulative cost is 20. That's 1 times C 41 plus 2 times C 42

plus 3 times C 43 plus 4 times C 44. So that's 1 plus 2 times 3 is 7 plus 3

times 3 is 9, plus 7 is 16,plus 1 times 4 is 20 and divide the 20 by the 8, you get

2.5, and do that same calculation for n equals 5, you get an average cost of 3.

So, the average goes 1.5, 2, 2.5, 3, you can probably see a pattern there as well.

but we'll do is use the symbolic method to compute this average.

okay, so here's the definitions, we're interested in the class of all

compositions. and recall that we can write compositions

as the number in[INAUDIBLE] and just put a bar.

to indicate the division into a sum so 12 could be 1 plus 3 plus 1 plus 5 plus 2

and that's an example but now our parameter is the number of parts so we

have a ordinary bivariate generating function z to the c times u to the number

of parts in c. So what does the construction look like?

We want u to mark the number of parts. want to use our same co, construction

that we used before. A composition is a a sequence of

integers, and an integer is a sequence of objects, but not including the empty one.

so for every integer we just want to mark that with u, so that's the construction,

just add the u to the inner sequence. that immediately translates to the

ordinary bivariate generating function. u sequence greater than 0 z is u times z

over 1 minus z. sequence of that is 1 over 1 minus that.

simplify by multiplying by 1 minus z and we get the expression 1 minus z over 1

minus z u plus 1. so to compute the horizontal ordinary

generating function, we take the coefficient of z to the n in that, and

that's very similar to our calculation for binomial coefficients.

It's just u plus 1 to the n, minus u plus 1 to the n minus 1.

So the number of compositions of n, is just evaluate that at 1, is 2 to the n

minus 1. The accumulated cost is going to be

differentiate and then evaluate at 1. and that's N times 2 to the N minus 1

minus N minus 1 times 2 to the N minus 2. Which simplifies to N plus 1 times 2 to

the N minus 2. A very, again very simple calculation.

And then divide those two and we get the average number of parts in a random

composition of N. Is N plus 1 over 2.

and that's what we observed in the table on the previous slide.

[COUGH] Okay, lets look at parameters on trees.

Again, these are questions that maybe are might be a little more difficult to

analyze, but they're straightforward, using this method.

So what's the expected root degree of a random tree with N nodes?

so this one has root degree 4, the root's got 4 children.

or how many leaves are there in a random tree with N nodes?

this one's gotten 14 leaves. parameters like this again we can analyze

by developing a generating function equation for the ordinary bivariate

generating function using the symbolic method.

Then extracting coefficient to get the horizontal generating function and then

evaluating it one to get the answer. And, this is a practical question in

plenty of applications this is a big random tree.

How many of the nodes are leaves? [SOUND] so this is all random trees,

these are ordered[INAUDIBLE] trees. And so again we're asking how many tress

are there that have n nodes and k leaves. so, there's 1 for phemone 1 for 1 and 2,

for 3, there's 1 tree that has 1 leaf and there's 1 tree that has 2 leaves for 4

there's one that has 1 leaf there's 2, there's 3 that have 2 leaves the ones in

the middle and there's one that has 3 leaves, the one at the top.

And for 4 now these are not binomial coefficients so this is the distribution.

and we can go ahead and compute the cumulative cost as before.

so for 4 the cumulative cost is 1 times 4 1, 2 times 4 2 plus 3 times 4 3 so that's

1 times 6 times plus 6 plus 3 is, that's 10.

and that's 5 of them so the average is 2, and the next one is 35 the average is

2.5. again, you might have a hypothesis for

the number of leaves just from this table but the question is to prove it.

which is straight forward, and turns out to be n over 2.

and we'll prove it on the next slide. so we're going to use the same

construction that we used before for trees but we're going to carry through

the transfer for ordinary bivariate generating functions not just a single

bivariate generating functions. so our parameter is the number of leaves

in the tree. what's a Tree?

a tree is either a root or it's a root with sequence a non-empty sequence of

trees. so that root is to, if a leaf that one's

got no trees below it so that's what we mark.

so that immediately, that construction immediately translates to generating

function equation. [COUGH] it's, it's, it's just using the

symbolic method. and it's very similar to the one that we

saw when we generated trees. In fact, if you evaluate at u equals one,

you get exactly the same equation that we had for, trees, which is a coefficients

of the cattelan numbers. so that's the number of trees and

cumulated cost differentiate with respect to U and evaluated 1.

And there's some calculation omitted, omitted here and so that's the the, the

result that we get. And coefficient of z to the N and 1 over

1 minus 4z is 2N choose N so now divide those 2 and you get N over 2.

That's the average number of leaves in a random tree.

and I, I admit I omitted a little bit of calculations here, you might want to

check that and see some wondrous property of the square root of 1 over 1 minus 4z.

So that's leaves and random trees and again that's what we observed and you can

also go ahead and compute these standard deviation and lets concentrate it.

So big tree have number of leaves, what about root degree how many trees are

there of n nodes and root degree k again these are the counts.

So for 4 There's 2 of them with root degree 1 the bottom 2.

2 of them with root degree 2 the middle 2, and 1 with root degree 3.

and for for 5 nodes then that's the distribution.

And again, we can go through and compute the cumulated costs and it goes 1.5, 1.82

not so clear what the result is going to be in this case.

But we'll use the same method to go head and compute the average root degree.

So it's the same class. it's the same construction.

We're just going to mark the trees in a different way.

So this time what we're going to do is they they, a random tree, is a root, and

then a sequence of random trees, but we're going to mark that first sequence

with with our variable U. [COUGH] so a coefficient of u to the n

the, so that the coefficient of z to the n, u to the k, in that is the number of

trees with so n nodes and root to degree k.

So that's immediately gives again the ordinary, bivariate generating function

equation and evaluated z of 1, z of 1 again, we get the what we got for regular

cattelan if we differentiate with respect to u and evaluate with 1 we get a 1 over

1 minus g squared term. and there is little magic calculation

here as well having to do with the fact that g of z.

Has this special generating function 1 minus, square root of 1 minus 4 Z over 2.

and, extracting coefficients, gives the result that the average number of leaves

is G N plus 1 over G N minus 1. which, the ratio of the cattelans there's

a little bit of calculation, it's 4 minus 6 over n plus 1, minus 1 is 3 minus 6

over n plus 1, and that's what we observed on the previous slide 1, 1.5,

1.8 and, and 2. The average number of leaves in a random

tree with n nodes is about 3 it converges to 3 and again that's interesting fact to

know for certain practical applications and it's available with some calculations

directly via symbolic method. here's another famous application this is

about rhyming schemes for poems. so this is a Limerick.

there was a small of Quebec, who was buried in snow to his neck when they

said, are you friz? He replied, yes I is.

But we don't call this cold in Quebec. So that's got the Rhyming scheme, as do

all limericks, AABBA. or if you want Robert Frost.

two roads diverged in a yellow wood and sorry I could not travel both.

And be one traveler, long I stood and looked down one as far as I could to

where it bent in the undergrowth. That one's got the rhyming scheme ABAAB.

so a natural question which actually lots of people have studied, from musicians to

poets is how many different ways are there to rhyme a poem?

so that's a parameter. and so we're going to ask the question.

if I have an N-line poem, how many ways are there to rhyme it with k rhymes?

So it's a two line poem there's only two possibilities.

Either the two lines don't rhyme or they do.

That's AB and AA. If it's three lines well you could have

ABC, nothing rhymes. Or you could have ABB the second two

rhyme. Or you could have AB and then A.

or you could have AA and then B, or you could have AAA.

But there's lots of strings of three letters that aren't here.

Well, the first ones always got to be A. the second ones got to be either A or B.

and then the third one can only be c if the first 2 are a and b and so forth.

So you can think a little bit about the constraint here.

so anyway here are the numbers. so for a 3 line poem,

There's one of them has just one rhyme that's AAA.

One of them's got three rhymes, it's ABC, and the rest of them have two rhymes ABB

ABA, or AAB. and then that's the answer for 4.

So these are that's the distributions, and we can also do the cumulative costs

as well but let's look at the generating function.

So, the class of all rhyming patterns, and our size is the number of lines.

Our parameter is the number of rhymes with k lines.

we use our ordinary bivariate generating function as before, and now the key is,

what's the combinitorial construction look like?

and this one actually is a vertical construction.

so, what it says is that you are going to have your first thing your first object

is going to be rhyming scheme A and you can have a sequence of any number of

those. and then after that, you're going to have

a B, and you can have a sequence of any numbers of A's and B's after that.

And then you can have a C and a sequence of any numbers of A's, B's and C's after

that. That's the construction for the class of

all rhyming patterns. and that immediately gives the vertical

OGF for the if we fix the number of rhymes to be k, this is the generating

function for the number of poems of size n, that have k rhymes.

That's the vertical OGF. and, actually this turns out to be

numbers that are well known in combinatorics and appear in many, many

other applications that we're not going to have time really to talk much

about although we'll see them again, and you can certainly read about them in the

book. These are called the sterling numbers of

the second kind and we'll see them again in another application in this lecture.

Turns out about k to the n over k factorial and line poems have k rhymes.

[COUGH] and just the, the sterling numbers of the second time, these are the

frequencies that we observed. and again they're very well studied.

The horizontal OGF is known as the bell polynomials

The vertical OGF is the one that we just determined.

Okay, these are the sterling numbers of the second kind and we don't have

explicit expressions for them, but we'll see them again.

so that's several examples of ordinary bivariate generating functions studied

with the symbolic method.