In this post, we continue our discussion on counting paths in single dimension simple random walks. Tonight we look at Catalan numbers. The number of paths from (0, 0) to (n, 0) that remain >= 0 is given by 1 / (n+1)  times (n + 1) Choose (n/2)
How do we prove this? We take the formula we described in the previous post  for finding the number of paths from (0,0) to (n, y), where y >= 0, that remain >= 0. And in this formula we substitute y=0
That number of paths was given by n Choose (n + Y) / 2 - n Choose (( n + y ) / 2 + 1)
And substituting y = 0 we get
N Choose n/2 - n Choose (n/2 - 1)
We can expand the definition of the combination n Choose r = n! / r! (N-r)!
And we will reduce the result to 1/(n+1)  times (n+1) Choose n/2
We look at another corollary as well.  The number of paths that start from (0,0), have length n, and remain non-negative is given by :

(n Choose ceil(n/2)) where ceil(x) denotes the smallest integer that is just greater than or equal to x.

This is different from the other corollaries we have mentioned so far. This one talks about paths that have length n. We show that their number is (n Choose ceil(n/2)) this way. 

We take the number of paths we computed earlier in this post for paths from (0,0) to (n,y) that don’t touch the horizontal axis as = n Choose (n+y)/2 - n Choose ((n+y)/2 + 1)

and then we sum over all y >= 0.

If n is even (2m) then we need to take y as even (2z) otherwise the formula above is equal to zero, and we have the number of desired paths

Sum z >= 0 ( 2m Choose (m+z) - 2m Choose (m+z+1))

which we can expand the series by listing each z >= 0 and summing it.

We will see that adjacent terms cancel out and we will get the result as the first term = 2m Choose m  which is n Choose n/2

If n is odd (2m +1) then we need to take y as odd (2z + 1) otherwise the formula is again equal to zero, and we have

the number of paths from (0,0) to (2m+1, any) where paths remain above horizontal) = 

Sum ( z >= 0 [ (2m + 1) Choose (m+z+1) - (2m + 1) Choose (m+z+2)]

and again we expand this series for each term z >= 0 , we see that the adjacent terms cancel out leaving us with only the first term as 2m+1 Choose m+1 which is 

(n Choose ceil(n/2))