How many number of paths are there

Question

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)  

Answer 1

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.

Answer 2

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.