Reader, you can refer to the solution video of this problem which explains the concept in detail.

You are given that the 0th Catalan number is 1 and the first Catalan number is also 1. You have to find the nth Catalan number given that the nth Catalan number can be calculated as shown in below.

We take a look at some of the Catalan numbers that can be derived from the formula above.

Let's look at the number of BSTs that can be formed for different nodes:

• 0 nodes: The number of BSTs that we can create if we are not given any node is 1. This is because a tree with no node does not disobey the Binary Search Tree Property (BTP).
• 1 node: A tree with only a single node will have only one Binary Search Tree. Say if the data of the node was 10 for instance, we will have only one BST with the only node with data 10 as the root node.
• 2 nodes: If we are given 2 nodes, two BSTs are possible because once we will select one node as the root node and the other time the other.
• 3 nodes: Now things will get interesting for us. Let us assume the three nodes given to us are 10, 20, and 30. Let us try to make BSTs from them.

So, we have made 5 BSTs from the given number.

As you can see above,

• For input 0, we assume that the output is 1.
• For input 1, it implies that we have 1 upstroke and 1 downstroke i.e. one pair and we can arrange this in only one way.
• For input 2, we have 2 pairs. We can either put one pair inside another pair or not. This way we can arrange 2 pairs in two ways.
• For input 3, we have 3 pairs. We can arrange these 3 pairs in 3 ways.
1. To start with, we can place 2 pairs inside 1 pair. There are 2 ways of doing so.
2. We can also place 1 pair inside 1 pair and one outside it. There is only one way of doing this.
3. We can also place 0 pairs inside 1 pair and 2 pairs outside. This can be done in 2 ways.

So, in total we will have 5 different ways which is also the output for 3.

This question is very similar to the previous question. Here you are required to find the number of ways in which you can arrange the brackets if the closing brackets should never exceed the opening brackets.

Figure 7 explains the output for the following inputs:

• For input 0, we assume that the output is 1.
• For input 1, it implies that we have 1 opening bracket and 1 closing bracket i.e. one pair and we can arrange this in only one way (valid).
• For input 2, we have 2 pairs. We can either put one pair inside another pair or not. This way we can arrange 2 pairs in two ways.
• For input 3, we have 3 pairs. We can arrange these 3 pairs in 3 ways.
1. To start with, we can place 2 pairs inside 1 pair.
2. We can also place 1 pair inside 1 pair and one outside it.
3. We can also place 0 pairs inside 1 pair and 2 pairs outside.

This problem is not directly a Catalan problem but is reducible to a Catalan problem.

We are given a number N as the input and there are 2N points on a circle. We have to tell the number of ways in which we can draw N non-intersecting chords on this circle.

• When N=0: When N=0, the number of points on the circle is 2N=0. There is still one way to draw N non-intersecting chords. Do not draw anything on the circle. This will result in 0 non-intersecting chords.
• When N=1: This means that we have to draw 1 chord in a circle (a single chord will be non-intersecting only). So, N=1 means 2N=2 points are there on the circle and we can draw 1 non-intersecting chord in 1 way.
• When N=2: So, when N=2, 2N=4. We have 4 points on the circle. We have only 2 ways to draw 2 non-intersecting chords on the circle because the position of the points is fixed on the circle (as it should be).
• When N=3: When N=3, there are 2N=6 points on the circle. If we start from P1, we can draw the first chord in 3 different ways such that on either side of the chord, we have enough points in such an arrangement that we can draw non- intersecting chords on both sides.

When N=0 or N=1 or N=2: When the input value of N is less than 3, our answer will be 0. This is because we cannot triangulate a shape with less than three sides.
The minimum sized polygon is a triangle and we need three sides for it. So, if we are given less than three sides, the shape is not even a polygon and we cannot triangulate it.
When N=3: The given polygon is a triangle itself. So, there is only one way to triangulate it, do not do anything with the polygon.
When N=4: We have 2 ways to triangulate it as shown in figure 9.
The number of ways of triangulation of an N-vertex (N-sided) polygon (when N>3) is the (N-2) th Catalan number.
When N=5: The number of ways in which we can triangulate a polygon of sides 5 is the 3 rd Catalan number. These ways are shown in figure 10.

This problem, like the previous one, is not directly a Catalan problem but can be reduced to it.

A Dyck word is a string consisting of n V's and n H's which are organized in such a way such that at no moment the number of H's is more than the number of V's.
For example, for n=3, figure 11 shows all the possible dyck words.

For n=3, HHHVVV is not a dyck word because when we are at index 0, the frequency of H is 1 and the frequency of V is 0 at that moment which does not fulfill our rule.
You need to consider V and H just as opening and closing brackets or upstroke and downstroke.

Above figure gives us all the dyck words upto n=3.

In a square matrix of dimensions nn, we need to find the paths that lead from the lower left corner to the upper right corner such that they do not touch the diagonal line from lower left to lower right. In other words, the paths that stay on or above the main diagonal.

This problem is just like the Mountains and Valleys problem. For above figure, some of the paths are shown in figure below.

The green path is represented as HHVV and the blue path is represented as HVVH.
All the paths possible for a grid of 3*3 are given below.

Only the paths marked with a tick are our desired paths because for them at no moment the number of H's is more than the number of V's.