Some generating functions
Dear Sumant,
Its 23:16 and I am beginning to write my blog for today. I am sitting on my couch and there is this 1flouroscent bulb is glowing. I finished my yoga few moments ago. Today was day 11th lesson I finished but I am doing it for more than 13 days. I have skipped lesson few times but not the practice. Today I added three more asanas and variations to my practice one is head twist, modified chest expansion and modified cobra position. I have already added shoulder stand to my routine. I like that one and my goal is to also add the head stand too. Two of the most juicy positions. Tomorrow is day 12 lesson that means there will be a review of everything I have done today which is good. One thing I noticed that today for the first time I was able to do leg over, however the leg stand is by far the most difficult position for me. The objective is to keep my leg straight and point it towards the roof and I think I make an angle of like 60 degree at best. The moment I start to pull over it gives me a cramp like feeling. In the right leg I can actually feel my muscles snapping. Hopefully the continued practice will see me someday achieving the perfect poise and balance with this.
I spend all of the time today doing Combinatorics stuff. As you know there are two main models of generating function I am learning. The first is called Ordinary Generating Function and the second is called Exponential Generating Function. While the ordinary one counts unlabelled balls into labeled buckets. The exponential one counts labeled balls into labeled buckets. Miklos Bona’s book has some very neat examples on product and composition of generating functions. On products of generating function there are questions like you have [n] on which first k you do one sort of things and on the later n-i you do some other things then what is the total number of ways to do things over n. This I would call interval model. The other one is you make a subset and do operations on the subset. This I would call subset model.
Let me give you a brief overview of what interval model look like. Suppose there are n poles and there is a crew which finishes i poles in the day and paints a smiley face on one of the remaining n-i poles is an example of interval model. A composition model based on interval might look like There is a doctoral student writing her thesis and we don’t know the number of chapter however each chapter much contain at least one page of text and one page of picture also there is no page which contains both picture and text on one. If there are n pages on her dissertation how many ways can her doctoral thesis look like.
Let me also introduce you to some exponential generating models. One of the good thing is exponential generating functions give ordered stirling numbers. You know that stirling numbers are putting n different balls in unlabelled bucket so that no bucket is empty. When using exponential generating function it means that the buckets are labeled, so to get stirling number all we have to do is divide by n!, where n is the number of buckets. The composition of exponential function involves the classic model of making people sit around circular tables and for each table there is a choice of two different types of wines (red and white). The reason for exponential is we are choosing a subset of people to sit around table and we don’t know how many tables we have, all we know that we have n people. So there could be a case when one person is sitting by herself. The composition model helps us concentrate only on one particular subset thus in this case we know that if there are k people at a particular table we can make them sit in (k-1)! ways. If you put this in exponential generating function it will give ln(1/(1-x)). Also the number of ways one table can order a wine is 2 so there is 2^n ways for n subsets (or tables here). If we put this into its exponential generating function we get e^(2*x). To get the total number of ways seating arrangement and wine distribution takes place we compose it as e^(2*ln(1/(1-x))). Which gives 1/((1-x)^2 ) and the coefficient of x^n/n! is (n+1)!. Thus there are (n+1)! ways to serve 2 different types of wine.
Now compare the two composition cases in the first example it was about writing chapters so each chapter involves consecutive number of pages. A similar example in the book involves the session in congress where each session will have a preliminary and the rest of the days have two choices involve committee or subcommittee work. We only know that there are total of n days but no idea about the length of each session. This also gives rise to ordinary generating function model. Its easy to see that for each interval of size k can be deal with in k*2^(k-1). Which gives the generating function x/(1-2*x)^2. The composition will give 1/(1-x/(1-2*x)^2) and from there we can siphon off of the coefficient of x^n to be (4^n-1)/3 Thus the bottom line is if there is a session or chapter of a book where each block contains consecutive elements from the [n] to be a block then it’s a sequence if however you can randomly choose the elements of the block then it’s a block. Now think again how we choose the people to sit around a round table !!
That’s for now
Sumant Sumant
Its 23:16 and I am beginning to write my blog for today. I am sitting on my couch and there is this 1flouroscent bulb is glowing. I finished my yoga few moments ago. Today was day 11th lesson I finished but I am doing it for more than 13 days. I have skipped lesson few times but not the practice. Today I added three more asanas and variations to my practice one is head twist, modified chest expansion and modified cobra position. I have already added shoulder stand to my routine. I like that one and my goal is to also add the head stand too. Two of the most juicy positions. Tomorrow is day 12 lesson that means there will be a review of everything I have done today which is good. One thing I noticed that today for the first time I was able to do leg over, however the leg stand is by far the most difficult position for me. The objective is to keep my leg straight and point it towards the roof and I think I make an angle of like 60 degree at best. The moment I start to pull over it gives me a cramp like feeling. In the right leg I can actually feel my muscles snapping. Hopefully the continued practice will see me someday achieving the perfect poise and balance with this.
I spend all of the time today doing Combinatorics stuff. As you know there are two main models of generating function I am learning. The first is called Ordinary Generating Function and the second is called Exponential Generating Function. While the ordinary one counts unlabelled balls into labeled buckets. The exponential one counts labeled balls into labeled buckets. Miklos Bona’s book has some very neat examples on product and composition of generating functions. On products of generating function there are questions like you have [n] on which first k you do one sort of things and on the later n-i you do some other things then what is the total number of ways to do things over n. This I would call interval model. The other one is you make a subset and do operations on the subset. This I would call subset model.
Let me give you a brief overview of what interval model look like. Suppose there are n poles and there is a crew which finishes i poles in the day and paints a smiley face on one of the remaining n-i poles is an example of interval model. A composition model based on interval might look like There is a doctoral student writing her thesis and we don’t know the number of chapter however each chapter much contain at least one page of text and one page of picture also there is no page which contains both picture and text on one. If there are n pages on her dissertation how many ways can her doctoral thesis look like.
Let me also introduce you to some exponential generating models. One of the good thing is exponential generating functions give ordered stirling numbers. You know that stirling numbers are putting n different balls in unlabelled bucket so that no bucket is empty. When using exponential generating function it means that the buckets are labeled, so to get stirling number all we have to do is divide by n!, where n is the number of buckets. The composition of exponential function involves the classic model of making people sit around circular tables and for each table there is a choice of two different types of wines (red and white). The reason for exponential is we are choosing a subset of people to sit around table and we don’t know how many tables we have, all we know that we have n people. So there could be a case when one person is sitting by herself. The composition model helps us concentrate only on one particular subset thus in this case we know that if there are k people at a particular table we can make them sit in (k-1)! ways. If you put this in exponential generating function it will give ln(1/(1-x)). Also the number of ways one table can order a wine is 2 so there is 2^n ways for n subsets (or tables here). If we put this into its exponential generating function we get e^(2*x). To get the total number of ways seating arrangement and wine distribution takes place we compose it as e^(2*ln(1/(1-x))). Which gives 1/((1-x)^2 ) and the coefficient of x^n/n! is (n+1)!. Thus there are (n+1)! ways to serve 2 different types of wine.
Now compare the two composition cases in the first example it was about writing chapters so each chapter involves consecutive number of pages. A similar example in the book involves the session in congress where each session will have a preliminary and the rest of the days have two choices involve committee or subcommittee work. We only know that there are total of n days but no idea about the length of each session. This also gives rise to ordinary generating function model. Its easy to see that for each interval of size k can be deal with in k*2^(k-1). Which gives the generating function x/(1-2*x)^2. The composition will give 1/(1-x/(1-2*x)^2) and from there we can siphon off of the coefficient of x^n to be (4^n-1)/3 Thus the bottom line is if there is a session or chapter of a book where each block contains consecutive elements from the [n] to be a block then it’s a sequence if however you can randomly choose the elements of the block then it’s a block. Now think again how we choose the people to sit around a round table !!
That’s for now
Sumant Sumant
posted by Sumant at 10:59 PM
0 Comments:
Post a Comment
<< Home