Counting Sequence of Lattice Paths going through a point

765 Views Asked by At

The length of a lattice walk is the number of steps taken. Write the counting sequence --- including the general term and starting from the walks of length zero --- for walks of length $n$ that start at $(0, 0)$ and include point $(2, 2)$ with allowable steps $\rightarrow$ and $\uparrow$. Written in terms of $n$, the general term will require restrictions on what $n$ are allowable.

For $n = 0, 1, 2, \dotsc$ what I've got is: $$0, 0, 0, 0,\ \frac{4!}{2!2!},\ 6 \cdot 2 \cdot 2 \cdot 2!,\ 6 \cdot \frac{3!}{2!},\dotsc,\ 6 \cdot 2^{|x-y|} \cdot \frac{n!}{(x-2)!(y-2)!}$$ where $n \geq 4$ and the path ends at $(x,y)$ (this is the general term).

Is this correct? If not, any tips on where I went wrong would be appreciated. Thank you!

1

There are 1 best solutions below

0
On

Since you can only go right and up, you cannot visit $(2, 2)$ after you pass out of the box defined by the two corners $(0, 0)$ and $(2, 2)$. Thus, from $(0, 0)$, you must take some steps to reach $(2, 2)$ and then you can take any steps you want. There are 6 ways to do the first part as you calculated. For the second part, at each step you have two choices (right and up) so for $k$ steps you have $2^k$ choices.

Multiplying these two, you get $6\cdot 2^{n-4}$ when $n \geq 4$ and 0 otherwise.