Posted 05/10/2017

----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

In this problem, we are interested in enumerating $1$-dimensional random walks with $n$ steps such that the last position have the maximun distance to the origin.

A $1$-dimensional random walk on $\mathbb Z$ of length $n$ is an $n$-step walk using $E(1)$ and $W(-1)$ as steps starting at the origin $(0)$ of the number axis. For an $n$-step $1$-dimensional random walk $w$, we define $X(w)=\{x_0(w),x_1(w),x_2(w),\cdots,x_n(w)\}$ as follows. We let $x_0(w)=0$ and let $x_i(w)$ to be the distance between the position after the $i^\textrm{th}$ move and the origin $(0)$. For example, $w=EEWEWWEEEE$ is a $10$-step walk, and $X(w)=\{0,1,2,1,2,1,0,1,2,3,4\}$.

Let $a_n$ be the number of $n$-step $1$-dimensional random walk $w$ such that $x_n(w)=\mathrm{max}\{x_0(w),x_1(w),x_2(w),\cdots,x_n(w)\}$, then $a_n$ counts the number of $n$-step $1$-dimensional random walks such that the last position have the maximun distance to the origin.


Our problem is to find $a_n$.