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.

Â