Finding the the number of Lattice paths with three steps.

Question

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.

Answer 1

We derive a generating function $A(t)$ where $[t^n]A(t)$, the coefficient of $t^n$ in $A(t)$ gives the number of nice paths from $(0,0)$ to $(n,n)$. We conveniently encode a step in $x$-direction as $x$ corresponding to $u=(1,0)$, a step in $y$-direction as $y$ corresponding to $r=(0,1)$ and encode written in parenthesis $(xy^2)$ a step corresponding to $v=(1,2)$.

We consider the following symbolic equation \begin{align*} \mathcal{A}=\varepsilon + t\times\mathcal{A}\times\mathcal{A}+t^2\times\mathcal{A}\times\mathcal{A}\tag{1} \end{align*}

and interpret (1) as the set $\mathcal{A}$ of nice paths which is built from

• the empty path or

• a diagonal step of length $1$, which is realised as $yAxA$ where $A$ represents a nice path or

• a diagonal step of length $2$, which is realised as $(xy^2)AxA$ where $A$ represents a nice path.

The idea here is to consider the diagonal step $yx$ with length $1$ and the diagonal step $(xy^2)x$ with length $2$ as basic building blocks.

From (1) we derive the functional equation \begin{align*} A(t)&=1+tA(t)^2+t^2A(t)^2\\ \end{align*} and obtain the generating function \begin{align*} \color{blue}{A(t)}&\color{blue}{=\frac{1-\sqrt{1-4t-4t^2}}{2t(1+t)}}\\ &=1+t+3t^2+9t^3+\color{blue}{31}t^4+113t^5+431t^6+\cdots \end{align*} where the last line was calculated with some help of Wolfram Alpha.

The blue marked $31$ nice paths from $(0,0)$ to $(4,4)$ are \begin{align*} \begin{array}{llll} yyyyxxxx&yyxxyxyx&(xy^2)yxxyx&yx(xy^2)xyx\\ yyyxyxxx&yxyyyxxx&(xy^2)xyyxx&yyx(xy^2)xx\\ yyyxxyxx&yxyyxyxx&(xy^2)xyxyx&yxy(xy^2)xx\\ yyyxxxyx&yxyyxxyx&y(xy^2)yxxx&yyxx(xy^2)x\\ yyxyyxxx&yxyxyyxx&y(xy^2)xyxx&yxyx(xy^2)x\\ yyxyxyxx&yxyxyxyx&y(xy^2)xxyx&(xy^2)(xy^2)xx\\ yyxyxxyx&(xy^2)yyxxx&yy(xy^2)xxx&(xy^2)x(xy^2)x\\ yyxxyyxx&(xy^2)yxyxx&yx(xy^2)yxx\\ \end{array} \end{align*}

Note: The sequence $1,1,3,9,31,113,431,\dots$ is archived in OEIS as A052709.

We can also conveniently use the generating function $A(t)$ to obtain the number of $(1,2)$-steps which occur in the nice paths from $(0,0)$ to $(n,n)$. We mark the occurrence of an $(1,2)$-step, i.e. $(xy^2)$ in the symbolic equation (1) with $q$ and consider \begin{align*} \mathcal{A}_q=\varepsilon + t\times\mathcal{A}_q\times\mathcal{A}_q+q\cdot t^2\times\mathcal{A}_q\times\mathcal{A}_q\tag{2} \end{align*} We obtain from (2) the generating function \begin{align*} A(t;q)&=\frac{1-\sqrt{1-4t-4qt^2}}{2t(1+qt)}\\ &=1+t+(q+2)t^2+(4q+5)t^3+(\color{blue}{2q^2+15q+14})t^4\tag{3}\\ &\qquad+(15q^2+56q+42)t^5+\cdots \end{align*} and look at the polynomial $[t^4]A(t;q)=2q^2+15q+14$ which provides a refinement of the $31$ nice paths from $(0,0)$ to $(4,4)$. We have in accordance with the listed paths above:

• $14$ paths which have no occurrence of $(xy^2)$,

• $15$ paths which contain $(xy^2)$ precisely once and

• $2$ paths which contain $(xy^2)$ precisely twice.

Number $P_n$ of nice paths with $(1,2)$-steps:

We derive the number $P_n$ of nice paths which contain $(1,2)$-steps from the generating function $A(t;q)$. Looking again at $[t^4]A(t;q)=2q^2+15q+14$ we see we have to sum up the terms with a factor $q$ evaluated at $q=1$. We can isolate the constant term by evaluating $[t^4]A(t;q)$ at $q=0$. In order to derive the terms with factor $q$ we calculate the number of nice paths from $(0,0)$ to $(n,n)$ which contain $(1,2)$-steps as \begin{align*} P_n=[t^n]\left(A(t;1)-A(t;0)\right)\qquad\qquad n\geq 0\tag{4} \end{align*}

Number $V_n$ of $(1,2)$-steps in nice paths:

We can also count the number $V_n$ of $(1,2)$-steps in nice paths. In order to get e.g. the $\color{blue}{19}$ $(1,2)$-steps in the paths from $(0,0)$ to $(4,4)$ we differentiate $[t^4]A(t;q)$ w.r.t. $q$ and evaluate at $q=1$: \begin{align*} V_4=[t^4]\left(\left.\frac{\partial}{\partial q}A(t;q)\right|_{q=1}\right)=(4q+15)|_{q=1}\color{blue}{=19} \end{align*}

In general we have \begin{align*} V_n&=[t^n]\left(\left.\frac{\partial}{\partial q}A(t;q)\right|_{q=1}\right)\\ &=[t^n]\left.\left(\frac{t}{(1+qt)\sqrt{1-4t(1+qt))}}-\frac{1-\sqrt{1-4t(1+qt)}}{2(1+qt)^2}\right)\right|_{q=1}\tag{5}\\ &=[t^n]\left(t^2+4t^3+(\color {blue}{(4q+15)}t^4+(30q+56)t^5\right.\\ &\qquad\left.\big.+(15q^2+168q+70)t^6+\cdots\big)\right|_{q=1} \end{align*}

Calculation of $P_n$ and $V_n$:

We manually calculate the polynomial $p_n(q)=[t^n]A(t;q)$ from which we can easily deduce $P_n$ and $V_n$.

We obtain \begin{align*} \color{blue}{p_n(q)}&=\color{blue}{[t^n]}\color{blue}{A(t;q)}\\ &=[t^n]\frac{1-\sqrt{1-4t(1+qt)}}{2t(1+qt)}\\ &=[t^n]\left(1-\sum_{j=0}^\infty\binom{\frac{1}{2}}{j}\left(-4t\right)^j\left(1+qt\right)^j\right)\frac{1}{2t(1+qt)}\tag{6}\\ &=2[t^n]\sum_{j=1}^\infty\binom{\frac{1}{2}}{j}\left(-4t\right)^{j-1}\left(1+qt\right)^{j-1}\\ &=2[t^n]\sum_{j=0}^\infty\binom{\frac{1}{2}}{j+1}\left(-4t\right)^{j}\left(1+qt\right)^{j}\\ &=[t^n]\sum_{j=0}^\infty\binom{2j}{j}\frac{1}{j+1}t^j(1+qt)^j\tag{7}\\ &=\sum_{j=0}^n\binom{2j}{j}\frac{1}{j+1}[t^{n-j}](1+qt)^j\tag{8}\\ &\,\,\color{blue}{=\sum_{j=0}^n\binom{2j}{j}\frac{1}{j+1}\binom{j}{n-j}q^{n-j}}\tag{9} \end{align*}

Comment:

• In (6) we use the binomial series expansion.

• In (7) we use the binomial identity $\binom{\frac{1}{2}}{j}=\frac{1}{2^{2j-1}}\binom{2j-2}{j-1}\frac{(-1)^{j-1}}{j}$.

• In (8) we apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$.

• In (9) we select the coefficient of $t^{n-j}$.

We finally conclude from (4), (5) and (9) \begin{align*} \color{blue}{P_n}&=p_n(1)-p_n(0) \color{blue}{=\sum_{j=\left\lceil \frac{n}{2}\right\rceil}^{n-1}\binom{2j}{j}\binom{j}{n-j}\frac{1}{j+1}}\\ \color{blue}{V_n}&=\left.\left(\frac{d}{dq}p_n(q)\right)\right|_{q=1} \color{blue}{=\sum_{j=\left\lceil \frac{n}{2}\right\rceil}^{n-1}\binom{2j}{j}\binom{j}{n-j}\frac{n-j}{j+1}} \end{align*} and get as plausibility check \begin{align*} \color{blue}{P_4}&=\sum_{j=2}^3\binom{2j}{j}\binom{j}{4-j}\frac{1}{j+1}=\binom{4}{2}\binom{2}{2}\frac{1}{3}+\binom{6}{3}\binom{3}{1}\frac{1}{4}\\ &=2+15\color{blue}{=17}\\ \color{blue}{V_4}&=\sum_{j=2}^3\binom{2j}{j}\binom{j}{4-j}\frac{4-j}{j+1}=\binom{4}{2}\binom{2}{2}\frac{2}{3}+\binom{6}{3}\binom{3}{1}\frac{1}{4}\\ &=4+15\color{blue}{=19}\\ \end{align*} in accordance with the calculations above.

Answer 2

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)$.