Catalan Numbers
The Catalan numbers are a sequence of positive natural numbers that occur in various counting problems in combinatorics.
They are named after the Belgian Mathematician Eugène Charles Catalan.
The Catalan sequence is 1,1,2,5,14,42……so on.(n =0,1,. …)
In general, the nth Catalan number in terms of Binomial coefficients is given by
Which can also be expressed as
Peculiar property of Catalan numbers
If matrices are formed from the Catalan numbers as shown below
Then the determinant of all such matrices will be 1.
Some Applications of Catalan numbers in Combinatorics
1. Lattice Paths
Consider plane divided into square boxes of side one unit each as shown. Let the point O be the origin (0,0) and P be any point (n, n).Find the number of paths that go from O to P such that each path is on or above the straight line joining O and P(indicated in pink).In any case at a time you can only go one step upward or one step towards the right.
Sol:
Let n = 2, then we have O(0,0) and P(2,2)
In this case we can have 2 paths(indicated in green) such as
Similarly, for n = 3 we have O(0,0) and P(3,3)
In this case we can have 5 paths(indicated in green) such as
Similarly, for n =4 we can have 14 paths.
Hence we have
A sequence of Catalan numbers.
Generalized solution for n:
Number of paths(paths on or above the pink line) required =
( Total number of paths from O to P) -(Number of paths violating the condition i.e. they go below the pink line)
Suppose there is no restriction on path and consider a general point Q(m, n) and O be (0,0) .
Denoting a upward step as U and right step as R, to reach point Q from O we need m steps towards right and n steps upward. These steps can be taken in any way. So, we need to arrange m R’s
and n U’s .Which can be done in the following ways
Hence the number of total number of paths from O to Q is given by
So Total number of paths from O(0,0) to P(n, n) =
To find the number of violating paths we use the reflection trick:
Let n =4 i.e. point P be (4,4) and consider any violating path, for instance the line in yellow.
Draw a line parallel to y=x (pink line) passing through first violating point marked X. This line is marked in blue.
Now from the point X draw the reflection of original path(yellow line) in the line drawn parallel to y=x (blue line).This reflected line is shown in red. Let the end point of red be P’.
For any initial violating path taken, the blue line would remain the same since all the first violating points will be on that line only.
In this case when n = 4 , following the red path from X we reach the point P’(5,3).
Similarly, for n =5 P’will be (6,4) and for n =6 P’will be (7,5) and so on.
In general, we can say that the point P’ will be (n+1,n-1).
Clearly, we get a new path that begins with (0,0) and ends at (n+1,n-1).
This procedure of finding red path given yellow path is entirely reversible i.e. we can find the yellow path if red path is given.
Hence number of violating paths from (0,0) to P will be equal to number of paths from(0,0) to P’(n+1,n-1).
Number of paths from(0,0) to P’(n+1,n-1) (using equation 1)=
Therefore, the number of paths violating the condition i.e. they go below the pink line =
.
Number of paths(paths on or above the pink line) required =
this can be simplified to
Which is the nth Catalan number .
Therefore, number of paths on and above the pink line is a Catalan number.
2. Triangulations of (n+2) sided regular polygon.
Consider a polygon of (n+2) sides we must count the number of ways to divide the polygon into triangles by drawing its diagonals such that no two diagonals intersect in the body of the polygon.
Sol: Suppose n =2, we have a square,
As shown below we can triangulate the square in two ways
Suppose n = 3, we have a pentagon,
As shown below we can triangulate the pentagon in five ways.
Similarly, for n= 4 we get hexagon and we can triangulate it in 14 ways and so on.
This sequence also forms a Catalan sequence.
3. Parenthesizing an expression:
We are given a expression containing (n+1) terms. We need to find the number of ways to parenthesize this expression such that the order of the terms doesn’t change.
Sol: For simplicity consider the operation given is multiplication.
Suppose n = 2 and given expression is “abc”.
We can parenthesize this in 2 ways -> (a(bc)) ,((ab)c)
Suppose n=3 and given expression is “abcd”.
We can parenthesize this in 5 ways
(((ab)c)d) , ((ab)(cd)), ((a(bc))d) ,(a((bc)d)) , (a(b(cd)))
Similarly for n = 4 we can do it in 14 ways and so on.
This sequence also forms a Catalan sequence.
4. Handshake problem:
There are 2n people sitting around a circular table. Find the number of ways in which they can shake hands with each other such that the hands don’t cross each other.(A handshake happens with single hand only and each person can shake hands with one person at time) .
Sol: Let n =2 , we have 4 persons sitting around the table
Here the persons are shown as 1,2,3,4 and handshakes are represented by a line .
So for n=2 we can have 2 ways
Similarly for n= 3 we can have 5 ways to shake hands
and for n =4 ,14 ways to do the same and so on.
This forms a Catalan Sequence.
These Catalan Numbers have many other applications apart from those mentioned above.
We find their application in the field of computational geometry, cryptography and many others. We can find the use of these numbers in a vast areas of expertise making them one of the most important integer sequences.
