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.
