The 9 step problem A man can take a step forward, backward,left and right with equal probability. Find the probability that after 9 steps he will be just 1 step away from his initial point.
I have done similar questions with movement restricted to forward and backward only ,but this one just blows my mind.
 A: The original poster suggested I turn my comment into a solution, so here it is.
All possible 9-step paths (there are $4^9$ of them) can be generated by the polynomial $\left(L+R+U+D\right)^9$.
Since $L$ and $R$ cancel each other out, as do $U$ and $D$, the number of paths that terminate at the point $(m,n)$ is the coefficient of $R^mU^n$ in $\left(R^{-1}+R+U+U^{-1}\right)^9$.
$$\mbox{Let  } P(R,U)=\left(R^{-1}+R+U+U^{-1}\right)^9=\sum_{m,n}p_{m,n}R^mU^n.$$
Also note that by the multinomial theorem, 
$$P(R,U)=\left(R^{-1}+R+U+U^{-1}\right)^9=\sum_{i+j+k+\ell=9}\binom{9}{i,j,k,\ell}R^{\,j-i}U^{k-\ell}\mbox{, with }i,j,k,\ell\in\mathbb{Z}^+\cup\{0\}.$$
By symmetry, the number of paths that terminate one step from home is $4$ times the number of paths that terminate at $(1,0)$, or $4p_{1,\,0}$, where $p_{1,\,0}$ is the coefficient of $R^1U^0$. Using the multinomial theorem equation above,
$$p_{1,0}=\sum_{i+j+k+\ell=9\\j=i+1, k=\ell}\binom{9}{i,j,k,\ell}=\sum_{2i+1+2k=9}\binom{9}{i,j,k,\ell}=\sum_{2i+2k=8}\binom{9}{i,i+1,k,k}.$$
The sum $\displaystyle\sum_{2i+2k=8}\binom{9}{i,i+1,k,k}$ equals $\displaystyle\sum_{i=0}^4 \binom{9}{i,i+1,4-i,4-i}=\\$
$$\binom{9}{0,1,4,4}+\binom{9}{1,2,3,3}+\binom{9}{2,3,2,2}+\binom{9}{3,4,1,1}+\binom{9}{4,5,0,0}$$
$$= 630+5040+7560+2520+126=15876.$$
The desired probability is therefore $\dfrac{4\cdot15876}{4^9}=\dfrac{3969}{16384}$.
This is no less work than the answers already given, but it avoids combinatorial arguments, and it generalizes nicely to answer similar questions.
A: Think of the man starting at $(0,0)$.
Pick out one of the $4$ points $1$ step away from $(0,0)$. For instance $(1,0)$. 
In order to arrive there after the $9$-th step the number of "horizontal" (parallel to the $x$-as) steps must be odd and the number of "vertical" (parallel to the $y$-as) steps must be even. 
Secondly the number of steps to the right (horizontal) must exceed the number of steps to the left with $1$, and the number of steps forward (vertical) must equalize the number of steps backwards.
So we get the splitups:


*

*$9=1+8$ resulting in $\binom9{0,1,4,4}=630$ routes

*$9=3+6$ resulting in $\binom9{1,2,3,3}=5040$ routes

*$9=5+4$ resulting in $\binom9{2,3,2,2}=7560$ routes

*$9=7+2$ resulting in $\binom9{3,4,1,1}=2520$ routes

*$9=9+0$ resulting in $\binom9{4,5,0,0}=126$ routes


The summation of these numbers is $15876$ and is the total number of routes to $(1,0)$.
Multiplying this with $4$ we find a total number of $63504$ routes to one of the elements of $\{(0,-1),(0,1),(1,0),(-1,0)\}$
The routes are equiprobable so in order to find the probability it remains to divide by the total number of routes, wich is $4^9=262144$.
End result:$$p=\frac{63504}{262144}\simeq0.2422$$

A general solution with $2n+1$ steps will take the form:$$4\sum_{k=0}^n\binom{2n+1}{k,k+1,n-k,n-k}$$
Maybe there is a closed form for that, but uptil now I don't know.
A: Here's a new combinatorial approach. 
Assume that there are $2n+1$ steps.    
Denote directions $H$ (Horizontal) and $V$ (Vertical) and polarities $+$ and $-$,
(ie. $H+$ is right, $H-$ left, $V+$ forward, $V-$ backward).
Of the $2n+1$ steps, choose any $\color{red}{n}$ steps. Number of ways: $\binom {2n+1}n$. 


*

*For the chosen steps, assign polarity "$+$".  

*For the remaining $n+1$ steps, assign polarity "$-$". 


$$\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &? &?\\
V&  &? &?\\
\hline
& &\color{red}{n} &n+1  &2n+1\\
\hline\end{array}$$
Again, of the $2n+1$ steps, choose any $\color{orange}{n}$ steps. Number of ways: $\binom {2n+1}n$. 


*

*For these $n$ steps,  mark $H$ for those with polarity "$+$" and mark $V$ for those with polarity "$-$".  

*For the remaining $n+1$ steps, do the opposite, i.e. 
mark $V$ for those with polarity "$+$" and 
mark $H$ for those with polarity "$-$". 
$$\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &\color{orange}{r} &?\\
V&  &? &\color{orange}{n-r}\\
\hline
& &\color{red}{n} &n+1  &2n+1\\
\hline\end{array}
\hspace{3cm}
\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &\color{orange}{r} &r+1 & 2r+1\\
V&  &n-r &\color{orange}{n-r} & 2n-2r\\
\hline
& &\color{red}{n} &n+1  &2n+1\\
\hline\end{array}$$
This ensures that $n$ matched polarity step-pairs, with one unmatched step, in this case $H-$. 
Multiply by $4$ for all four directions $(H+, H-, V+, V-)$
This gives total number of combinations as $4\large\binom {2n+1}n^2$.
Hence probability of ending up one step away from original position is $$\frac {4\large{\binom {2n+1}n} ^2}{4^{2n+1}}=\frac {\large\binom {2n+1}n ^2}{4^{2n}}$$

NOTE also that the total number of ways to end up one step away from the original position after $2n+1(=2N-1)$ steps is the same as the total number of ways to end up back at the original position after $2n+2(=2N)$ steps, where  $N=n+1$. 
Assume that there are $2N$ steps.    
Denote directions $H$ (Horizontal) and $V$ (Vertical) and polarities $+$ and $-$,
(ie. $H+$ is right, $H-$ left, $V+$ forward, $V-$ backward).
Of the $2N$ steps, choose any $\color{red}{N}$ steps. Number of ways: $\binom {2N}N$. 


*

*For the chosen steps, assign polarity "$+$".  

*For the remaining $N$ steps, assign polarity "$-$". 


$$\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &? &?\\
V&  &? &?\\
\hline
& &\color{red}{N} &N  &2N\\
\hline\end{array}$$
Again, of the $2N$ steps, choose any $\color{orange}{N}$ steps. Number of ways: $\binom {2N}N$. 


*

*For these $N$ steps,  mark $H$ for those with polarity "$+$" and mark $V$ for those with polarity "$-$". 

*For the remaining $N$ steps, do the opposite, i.e. 
mark $V$ for those with polarity "$+$" and 
mark $H$ for those with polarity "$-$". 
$$\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &\color{orange}{r} &?\\
V&  &? &\color{orange}{N-r}\\
\hline
& &\color{red}{N} &N  &2N\\
\hline\end{array}
\hspace{3cm}
\begin{array}{&c|&c &c &c | &c}
\hline
&  &+ &- &\text{Total} \\
\hline
H&  &\color{orange}{r} &r & 2r\\
V&  &n-r &\color{orange}{N-r} & 2N-2r\\
\hline
& &\color{red}{N} &N  &2N\\
\hline\end{array}$$
Total number of combinations is 
$$\binom {2N}N\cdot \binom {2N}N=\binom {2N}N^2$$
Note that this equal to 
$$\binom {2n+2}{n+1}^2=4\binom {2n+1}n^2$$
A: In another answer, @hypergeometric provides a closed-form solution. I’m posting a second answer to provide a combinatorial argument for that closed-form solution. (I wouldn’t have come up with it had I not seen the closed-form solution!)
Proposition: The number of length-$(2n+1)$ paths that begin at the origin and end at the point $(1,0)$ (call these the “admissible paths”), where each step of the path moves one unit right, left, up, or down (R, L, U, or D), is $\displaystyle{2n+1\choose n}^2$.
Combinatorial proof strategy: Note that $\displaystyle{2n+1\choose n}^2$ is the number of ordered pairs $(A,B)$, where $A$ and $B$ are cardinality-$n$ subsets of $\{1,2,\dots,2n+1\}$. I will show that there is a one-to-one correspondence between the set of such pairs $(A,B)$ and the set of admissible paths.
Proof: Given an admissible path, note that the number of steps that increase the walker’s $x$- or $y$-coordinate (R’s and U’s) must exceed the number of steps that decrease either coordinate by exactly one, because the net effect of the path changes the coordinate sum $x+y$ of the walker’s position from $0$ to $1$. Thus there are $n+1$ R or U steps and $n$ L or D steps. Write $0$ above each R and U in the path and write $1$ above each L and D. Let $A$ be the subset of positions where a $1$ was written above a step of the path.
By a similar observation, there must be $n+1$ steps of type R or D (which increase the coordinate difference $x-y$ by one), and $n$ steps of type L or U (which decrease $x-y$ by one. Write $0$ below every R and D and $1$ below every L and U. Let $B$ be the subset of positions where a $1$ was written below a step of the path.
Different paths will yield different set pairs $(A,B)$, so this construction yields a distinct $(A,B)$ from each admissible path.
Now, given $(A,B)$, where $A$ and $B$ are cardinality-$n$ subsets of $\{1,2,\dots,2n+1\}$, create a path of steps L, R, U, and D as follows: Let $A$ be the set of positions in the path that are L or D, and $B$ the set of positions in the path that are L or U. Step $k$ of the path constructed from $(A,B)$ will be L if $k$ is in both $A$ and $B$; D if $k$ is in $A$, but not $B$; $U$ if $k$ is in $B$ but not $A$; $R$ if $k$ is in neither $A$ nor $B$.
The path created in this way contains $n+1$ steps that increase $x+y$ by one and $n$ that decrease $x+y$ by 1, and it contains $n+1$ steps that increase $x-y$ by one and $n$ that decrease $x-y$ by 1. Thus the path increases $x$ by one and leaves $y$ unchanged and is an admissible path. Different pairs $(A,B)$ yield different paths, and this completes the construction of bijection between the pairs $(A,B)$ and the admissible paths.
