I am currently working on calculating the number of legal bracket expressions of length n, that is expressions like
()(())
But not like
()())(
These are to be counted as an analogy for another problem. That is, imagine a chessboard of size n, with n being uneven, and a bishop standing in position (1,1). The bishop may only ever move one square either to the top and right, or to the bottom and right. With these moves, he must reach the square (n,1).
I went through possibly anything that I could think of. Drawing the paths made some interesting looking pyramids and I spent a bunch of time just writing all possible bracket expressions. I even already know what the answer will be, as it seems like I am looking at several problems from which one may derive the so called Catalan numbers.
The problem is, that I can't think of a way to count the amount of expressions. I have seen the formula C(2n,n) - C(2n,n+1) being used. I understand that C(2n,n) calculates all possible sequences of n left and n right brackets, legal or not, but I do not understand, why C(2n,n+1) amounts to all expression amongst those, that are not legal.
As much fun as I had with this problem, I belief I am in a spot where I just can't progress. I don't know how to look at the second binomial coefficient as something that really relates to this. I do not understand where the n+1 comes from. Any tips would be much appreciated.
