What are the connections between Catalan numbers and Pascal's Triangle?

[Townsend]

There are a few areas I wanted to make sure I understand what is going on in with discrete math. I have a test tomorrow over these topics and so this is not exactly homework unless you count studying for a test as homework. In any case I will do my best to explain what I know or don't know and of course any help is appreciated.

I guess any place is a good place to start so let's start with catalan numbers. Here is an example test question

How many paths lead from the lower left hand corner to the upper right hand corner of an n x n grid with the following restrictions.

1) Only moves to the right or up are allowed.

I guess 2n choose n the total.

2) Same as 1 but in addition you must cross the diagonal running from the lower left hand corner to the upper right hand corner.

2n choose n-1 ways, I guess.

3) Same as 1 but you are allowed to touch but not cross the diagonal running from the lower left hand corner to the upper right hand corner.

This would be the total from #1 minus the bad from number 2 or
2n choose n minus sn choose n-1.

4) (a) Given a bad path in a 5 by 5 grid what is the corresponding path in a 4 by 6 gird?
This is where I get a little bit sketchy. I know that we need to reverse the direction of the path at the first place we go bad, i.e. the first place where we have crossed the diagonal line. I guess that is all I need to answer this question but I am not completely sure why this works.

(b) Given a path in a 4 by 6 grid find the corresponding bad path in a 5 by 5 grid.
To do this I guess I could just follow the path from the 4 by 6 until I find the first place I go bad and then just switch the order.

...

There are many more but something just came up so I have to leave for about an hour. I will post the remaining questions when I can get back.

Thanks

Jeremy

 

[Townsend]

Ok...

Next I need to know how to find a formula for the sequence a_n given the recurrence relation a_n=3(n+1)a_{n-1} and a_0=5.

I guess a_n=5*3^{n+1}. Can someone confirm this answer?

One more

Find a formula for the sequence a_n given by the recurrence relation
a_n=2n^2a_{n-1}
and the initial condition a_0=3.

I tried to work this problem out but I cannot seem to find an explict formula.

I think that is about it...I think I can handle everything else with high confidence.

Thanks

Jeremy

 

[OlderDan]

Do you know about Pascal's triangle? If so, can you find it in this grid? Each number in the grid is the number of paths into that location for #1

1__6_21_56_126_252
1__5_15_35__70_126
1__4_10_20__35__56
1__3__6_10__15__21
1__2__3__4___5___6
1__1__1__1___1___1

The elements in Pascal's triangle are the binomial coefficients, or the number of combinations of n things taken r at a time nCr

 

[Townsend]

Do you know about Pascal's triangle? If so, can you find it in this grid? Each number in the grid is the number of paths into that location for #1

1__6_21_56_126_252
1__5_15_35__70_126
1__4_10_20__35__56
1__3__6_10__15__21
1__2__3__4___5___6
1__1__1__1___1___1

The elements in Pascal's triangle are the binomial coefficients, or the number of combinations of n things taken r at a time nCr

I see it...cool...basically if you write out the triangle the row corresponds to the diagonal of the triangle starting with the left most diagonal of 1's then to the 1,2,3,4,5,6 and I so on. But what is cool is how this somehow relates the catalan numbers to the binomial coefficients. However I cannot quite make the connection yet. The catalan sequence is 1,1,2,5,14,42,132,... it really amazes me how much mileage you can get from a simple set of numbers like the fibonacci sequence.