Proofing Catalan Numbers: A Combinatoric Approach

[msmith12]

I'm working on a problem that has to do with catalan numbers, and I'm just trying to figure out how to make a proof that shows what I am dealing with does in fact have to do with catalan numbers.

I know this is very general, but I don't want someone to do my problem for me, I just want to know how to do a combinatoric proof of anything that has to do with these numbers...

any help would be greatly appreciated

~matt

 

[TenaliRaman]

One way if you can "whatever" in your problem with the actual catalan number expression (1/n+1)C(2n,n) or if it has to do anything with the generating function of the catalan number.

Another way could be to reduce "whatever" in your problem to the known problems which have to do something with catalan number. (e.g number of binary trees of n nodes is a catalan number or the euler polygon problem or ballot problem)

-- AI

 

[msmith12]

I worked on the problem again, and tried to find a relationship between the formula C(n)=C(0)C(n-1)+C(1)C(n-2)+...+C(n-1)C(0), and my problem.

The problem is to find the number of possible 2xn matrices consisting of the first 2n integers so that the numbers in both the first and second rows are increasing, and the number in row 1, column j is less than the number in row 2 (for any j)...

I've been trying to come up with something using a tree, since the problem can easily be divided into two distinct halves-- notably

12xxx...x
xxxxx...2n

and

13xxx...x
2xxxx...2n

from this, it is really easy to divide each side into the sum of smaller matrices that satisfy the necessary conditions.

I guess the point I am now, is how can I turn this into a combinatoric proof that there are exactly Cn possible combinations?

Thanks

 

[robert Ihnot]

There is a counting argument to obtain Catalan Numbers, which involves the use of Dyck numbers discovered by D Andre. It is a little too long to write it in here, but it is used to determine:

C(n) = \frac{(2n)!}{n!n!} -\frac{(2n)!}{(n-1)!(n+1)!}

See: http://www.answers.com/topic/catalan-number