Name: Anonymous 2009-10-22 22:08
So I have a test on generating functions of the first and second type tomorrow and I get the gist of it but cannot finish my problems.
For example:
A bug makes some random moves along the x-axis:
case i) It starts at (0,0) and each of its moves is either a step right of length one, a step left of length one, or staying put. In how many ways can it land on (i,0) after n moves?
case ii) It starts at (0,0) and each of its moves is either a step right of length one, a step left of length one, or staying put. The bug has just finished his lunch, so he is more likely to stay put on each move. In particular, it is equally likely for him to go either right or left at each move, but it is twice as likely that he stays put than that he chooses to go right (or left) on each move. Compute the probabbility that the bug lands on (i,0) after n moves.
So I know the generating functions for each of these, and I understand that I have to find the coefficient of the x^i term for each. But I don't know how to finish this.
Generating functions:
case i) (x^-1 + x^0 + x^1) ^n
case ii) (x^-1 + 2x^0 + x^1) ^n
Also, dump all your knowledge of generating functions in layman words here, much appreciated.
For example:
A bug makes some random moves along the x-axis:
case i) It starts at (0,0) and each of its moves is either a step right of length one, a step left of length one, or staying put. In how many ways can it land on (i,0) after n moves?
case ii) It starts at (0,0) and each of its moves is either a step right of length one, a step left of length one, or staying put. The bug has just finished his lunch, so he is more likely to stay put on each move. In particular, it is equally likely for him to go either right or left at each move, but it is twice as likely that he stays put than that he chooses to go right (or left) on each move. Compute the probabbility that the bug lands on (i,0) after n moves.
So I know the generating functions for each of these, and I understand that I have to find the coefficient of the x^i term for each. But I don't know how to finish this.
Generating functions:
case i) (x^-1 + x^0 + x^1) ^n
case ii) (x^-1 + 2x^0 + x^1) ^n
Also, dump all your knowledge of generating functions in layman words here, much appreciated.