Question 21
C1 (IND). Let $n\ge1$ be an integer. A path from $(0,0)$ to $(n,n)$ in the $xy$ plane is a chain of consecutive unit moves either to the right (move denoted by $E$) or upwards (move denoted by $N$), all the moves being made inside the half-plane $x\ge y$. A step in a path is the occurrence of two consecutive moves of the form $EN$.
Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps ($n\ge s\ge1$) is
$$\frac1s\binom{n-1}{s-1}\binom n{s-1}.$$
Show that the number of paths from $(0,0)$ to $(n,n)$ that contain exactly $s$ steps ($n\ge s\ge1$) is
$$\frac1s\binom{n-1}{s-1}\binom n{s-1}.$$