The counting problem of paths Consider a one-dimension $10$-step random walk with step size $1$, namely $S_n=\sum_{n=1}^{10} X_n$ and $X_i = 1$ or $-1$ for all $i\in\{1,2,...,10\}$. Further we require $S_i \geq 0$ for any $i$. And we have $S_{10} = 4$. How many paths satisfy this condition?
Actually it is a counting problem. It troubles me due to the requirement of $S_i \geq 0$. Could anyone give me some hint? Thank you!
 A: Method I (brute force):  Clearly we must have seven $+1's$ and three $-1's$.  Also clearly, $X_1=1$.   If the third $+1$ occurs after the third $-1$ then we violate positivity, so the third $+1$ can only occur at $X_3,X_4,X_5$.  Easy to count each case.  
If it occurs at $X_3$ all subsequent paths are good, so this case contributes $\binom 74=35$
if it occurs at $X_4$ then there are $2$ ways to place the first $-1$ and after that all subsequent paths are good, so $2\times \binom 64=30$.
if it occurs at $X_5$ then there are $2$ ways to place the second $+1$ and after that all subsequent paths are good, so $2\times \binom 54=10$.
Thus the final answer is $$35+30+10=\boxed {75}$$
Method II (reflection):   if you ignore positivity there are $\binom {10}7=120$ paths.  The bad ones touch the line $y=-1$.  From the first point of contact with that line we could reflect our path to get a path that ends at $(10,-6)$.  Thus there is a bijection between bad paths in our problem and paths that end at $(10,-6)$.  There are $\binom {10}8=45$ paths that end at $(10,-6)$ so the answer is $$\binom {10}7-\binom {10}8=120-45=\boxed {75}$$
A: This is a pretty big spoiler but you could try to go check up the Catalan numbers
A: If there are $n$ step 1 and $m$ step $-1$ to be placed in a row such that number of 1s is always equal or more than the number of $-1$s, the number of ways is $\frac{n-m+1}{n+1}\binom{n+m}{m}$. In this case, $n=7, m= 3$ and hence equals $\frac{5}{8}\binom{10}{3} = 75$.
