Finding the the number of Lattice paths with three steps. We define a nice path of length as a path on a lattice from $(0,0)$ to $(n,n)$ such as every step in it is: $r=(0,1)$ , $u=(1,0)$ and $v=(1,2)$, and it does not go under the line $y=x$.
A. Write a formula for the generating function that counts the number of the nice paths.
B.Solve the above formula and find an expression for the number of these paths of length n.
C.Find the number of $(1,2)$ steps in all paths of length n.
I started with drawing the possible paths for $n=1,2,3,4$, getting that we have $1,3,9,27$ paths (respectively) if I did really succeed to count all the possible paths for each $n$.
So, then I concluded that each legal path (which is mentioned above) is:
Every path = $\epsilon$ or v(every path) u (every path) or r(every path) u (every path).
Whhere $\epsilon$ denote the empty path.
If $A(x)$ the generating function and x denote the number of steps then I get:
$A(x)=1+(xA(x))(xA(x))+(xA(x))(xA(x))$.
$A(x)=1+x^2A(x)^2+x^2A(x)^2$
In B. I can do this after extracting $A(x)$
With finding the coefficient of $x^n$ in $A(x)$.
C. I don't understand if this is related to statistics on the number of (1,2) steps..
I'm not sure if my way of thinking is correct or not, I discovered that my way is not accurate. I'll be glad if you can correct me, and explain it.
 A: Unfortunately, there are complications that make it not quite so straightforward as you've written. Most notably, what you have is the generating function for the number of paths with $n$ steps — but since you have one step that's longer than the others, that won't get you the number of paths to $(n,n)$. Instead, try writing a recurrence relation for $A_n$ in terms of smaller $A_i$ using the same approach that you sketched out loosely; you should find a very similar answer. (I suspect you're missing a factor of $x$ one way or the other in one of your terms, but writing the relation explicitly should make it clear.)
For (c), you'll need to expand your generating-function approach a bit. Let $A_{n,k}$ be the number of paths from $(0,0)$ to $(n,n)$ that contain $k$ (1,2)-steps. Then with a similar approach to what you've done for determining the number of steps you should be able to generate a recurrence relation for $A_{n,k}$, or equivalently an equation for the generating function $A(x,y)=\sum_n\sum_kA_{n,k}x^ny^k$. Once you've got this, the quantity that (c) asks for is $B_n=\sum_kkA_{n,k}$ (note that $A_n$ is just $\sum_kA_{n,k}$ without the multiplying factor). As a further hint if you aren't familiar with the particular manipulation that's relevant here, consider the effect of the $\frac{\partial}{\partial y}$ operator on $A(x,y)$.
