Catalan Numbers (Part I)
What are Catalan numbers? To put it shortly, Catalan numbers is a sequence of infinite numbers with its own property. In mathematics, we have different sequence of number patterns that we’ve all have come across. Of course no other sequence would be possible with out our basic counting numbers sequence(1,2,3,4,5…). From that we can derive other sequences such as perfect squares ( 1,4,9,16,25...) and powers of two (1, 2, 4, 8, 16 …). Our perfect squares sequence can be rewritten as (1², 2², 3² ,4² ,5²…), and our powers of two can be rewritten as (2⁰, 2¹, 2², 2³, 2⁴ …). Another example would be Fibonacci numbers where the next number of the list is the sum of the previous two (1, 1, 2, 3, 5, 8, 13 …)
Now that you have a general idea and refresher on number sequences, lets see what type of number sequence are Catalan numbers. Lets say you have to draw a mountain ( triangular like shape) with the use of up slashes and down slashes and with the condition of not going below the horizon. How many mountain arrangements can you draw with given set of slashes? In order to come complete one a mountain, you need at least one up slash and one down slash. Right away, any odd number of slashes would result in an error or at least one unfinished mountain. This would mean we would always need a pair of up slashes and down slashes. Second, since we can’t go below the horizon or the horizontal line, our first slash will always have to be a up slash.
Given one pair of slashes, we can only make one variation of a mountain. When we have a two pair limit, we can have two variations of mountains. One variation would be a big mountain using two up slashes and two down slashes and the other one being two small mountains using one up slash and one down slash each. Now if we increase our total up slash and down slash to three each, we would have 5 variations of drawing these mountains.
Taking a look back to the previous week where we went over the leetcode problem Valid Parentheses, we now have another parentheses related question. Give an N number pair of parentheses, how many ways can you arrange them? Just like our mountain draw questions, we have a very similar approach. If you take your time to draw it out, you will see that one pair will result in one arrangement, two pairs will result in two arrangements, three pairs will result in five arrangements and so on.
This is the general application of Catalan numbers. There are many questions that are similar which eventually leads back to the use of Catalan numbers. In our next part we will take a look at how Binary tree arrangement uses Catalan numbers and a deeper dive in to the actual formula for Catalan numbers.
