Sunday, January 31, 2010

Concept 3: CATLAN numbers

Can you tell me what is the next number of this series?
1,2,5,14,42,?

You may face trouble in finding though. But here is the formula
Tn=1/(n+1)*2nCn=(2n)!/[(n+1)!*n!] [For n>=1]
So T5=132.
The number of this series is popularly known as CATLAN numbers. And in different counting problems. I will try to explore some of them.

(A)Mountain Ranges and Diagonal Avoiding Paths

(i)How many mountain ranges you can draw using n upstrokes(/) and n downstrokes{\)
   Drawing the above phenomenon would reduce our burden.
n=1: /\ =>1 way
n=2: /\/\,  /\ => 2 ways
               /   \                                     /\
n=3: /\ /\ /\,  /\          /\     /\/\        /   \  => 5 ways
                    /   \/\, /\/  \, /      \,    /     \

Going like this it will generate nothing but the series of CATLAN numbers. For n=4 obviously we will get 14 distinct mountain ranges and so on.

(ii)Diagonal Avoiding Paths
In a grid of n×n squares, how many paths are there of length 2n that lead from the upper right corner
to the lower left corner that do not cross the diagonal dotted line from upper right to lower left? In
other words, how many paths stay on or above the main diagonal.



Again answer is noting but 4'th CATLAN numbers of the series. i.e. 14. And look it's not different than the arrangement of mountain ranges. [Follow the arrowhead paths]

(B)Triangulation of a convex polygon

 
For a convex ploygon having n sides (n>=4) total number of triangulation will be T(n-2) th term of the CATLAN series.
For n=6 obviously we will get 14 triangulations.


(C)Handshaking Lemma
If, 2n people are seated around a circular table, then in Tn ways they can shake their hands simultaneously such that at no instance the arms will cross each other.
Application
If 16 people are sitting in a circular table,in how many ways can all of them be simultaneously
shaking hands with another person at the table in such a way that none of the arms cross each other?Solution:
2n=16 =>n=8
Total ways T8 =16!/9!*8!=1430.

Hope you have enjoyed this concept session.

No comments:

Post a Comment