Exploring Catalan Numbers and Pascal's Triangle

In summary, Jeremy explains that he is having difficulty with a discrete math problem and asks for help. He provides a summary of the content, including a mention of the catalan sequence and Pascal's triangle.
  • #1
Townsend
232
0
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
 
Physics news on Phys.org
  • #2
Ok...

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

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

One more

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

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

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

Thanks

Jeremy
 
  • #3
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
 
  • #4
OlderDan said:
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.
 

Related to Exploring Catalan Numbers and Pascal's Triangle

1. What is discrete math?

Discrete math is a branch of mathematics that deals with objects that can only take on distinct, separated values. It involves the study of mathematical structures and their properties, such as graphs, trees, and logic.

2. What are some applications of discrete math?

Discrete math has a wide range of applications in computer science, cryptography, data analysis, and decision-making. It is also used in fields such as economics, engineering, and social sciences.

3. What are the basic concepts of discrete math?

Some basic concepts of discrete math include sets, relations, functions, logic, and combinatorics. These concepts are used to model and solve problems in discrete structures and systems.

4. What are some common topics in discrete math?

Common topics in discrete math include graph theory, combinatorics, probability, number theory, and formal languages. These topics are often used to solve real-world problems and develop efficient algorithms.

5. How can I improve my skills in discrete math?

Some ways to improve your skills in discrete math include practicing problem-solving, studying the fundamental concepts, and working on challenging problems. You can also attend workshops, join study groups, and read textbooks or online resources on the subject.

Similar threads

  • Introductory Physics Homework Help
Replies
14
Views
1K
  • Introductory Physics Homework Help
Replies
21
Views
1K
Replies
1
Views
442
  • Introductory Physics Homework Help
Replies
5
Views
850
Replies
4
Views
363
  • Introductory Physics Homework Help
Replies
4
Views
1K
  • Math Proof Training and Practice
Replies
23
Views
832
  • Introductory Physics Homework Help
Replies
7
Views
771
  • Introductory Physics Homework Help
Replies
2
Views
732
  • Introductory Physics Homework Help
Replies
12
Views
861
Back
Top