How many number of paths are there How many number of paths are there from (0, 0) to (4, 4) using the moves
R : (x, y) → (x + 1, y),  U : (x, y) → (x, y + 1), D : (x, y) → (x + 1, y + 1) ;
where a path can never rise above the line y = x.  Solve this problem by using Catalan Numbers.
I know the n-th Catalan Number formula $$C_n = \left(\frac{1}{n+1}\right) {2n \choose n}$$but I don't understand the connection between Catalan numbers and to getting (4,4) from (0,0)
 
 A: HINT: Catalan numbers, when you are allowed only the R and U steps; the green entry is the sum of the two red entries, because you can reach $\langle 3,2\rangle$ from below and from the left.
$$\begin{array}{c|cc}
4&*&*&*&*&?\\
3&*&*&*&?&?\\
2&*&*&\color{red}2&\color{green}5&9\\
1&*&1&2&\color{red}3&4\\
0&1&1&1&1&1\\\hline
&0&1&2&3&4
\end{array}$$
Your problem, with R, U, and D steps allowed:
$$\begin{array}{c|cc}
4&*&*&*&*&?\\
3&*&*&*&?&?\\
2&*&*&\color{red}6&\color{green}{16}&30\\
1&*&2&\color{red}4&\color{red}6&8\\
0&1&1&1&1&1\\\hline
&0&1&2&3&4
\end{array}$$
Since you need only the number in the upper righthand corner, you don’t need to develop a general formula: just complete the array.
A: Hint: The Catalan numbers are the number of ways to go from $(0,0)$ to $(n,n)$ with steps just $R$ and $U$ without going above $y=x.$(These are called Dyck paths) For your problem, notice that by adding the step $D$ you will never affect the condition, so what if you pick first how many diagonal steps (i.e., D) you want to take (lets say $i$) and then, for the remainder, you choose a Dyck path of lenght $n-i$?  To distribute the diagonals in between the Dyck path, notice that you have $n-i+1$ blanks to place the $i$ $ D$ steps.
