# Catalan number

Published: Sep 9, 2019

What is Catalan number ? The Catalan number belongs to the domain of combinatorial mathematics. It is a sequence of natural numbers such that: `1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, ...` The sequence appears in counting problems. Wikipedia has the details about the sequence: Catalan Number.

The algorithm of the Catalan number calculation is not difficult. Once the problem is identified as the Catalan number, the solution will come up relatively easy. However, something not easy is to identify it is the Catalan number problem.

#### Various types of counting problems

The Wikipedia article mentions various types of counting problems which are solved by the Catalan number. One more great resource is “Catalan Numbers” (http://www.geometer.org/mathcircles/catalan.pdf). The document refers to multiple counting problems as well as how to solve those. For a reference, it’s worth writing a memo what kind of problems are out there.

1. Balanced parentheses

Problem: Given `n` pairs of parentheses, how many patterns exist to create valid (balanced) combinations of parentheses.

Example:

`````` n  counts  patterns
0  1       *
1  1       ()
2  2       (()) ()()
3  5       ((())) ()(()) ()()() (())() (()())
``````

Note: This is a basic pattern of the Catalan number.

2. Dyck words

Problem: Given `n`, how many patterns exist to create words of n Xs and n Ys such that in every prefix of the word frequency(‘X’) ≥ frequency(‘Y’)

Example:

`````` n  counts  patterns
0  1       *
1  1       XY
2  2       XXYY XYXY
3  5       XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY
``````

Note: If X and Y are mapped ( and ) respectively, the problem is the same as the balanced parentheses.

3. Mountain Ranges

Problem: Given `n` pairs of sticks, how many patterns exist to create mountains.

`````` n  counts  patterns
0  1       *
1  1       /\
2  2       /\
/  \  /\/\
3  5        /\
/  \     /\             /\      /\/\
/    \  /\/  \  /\/\/\  /  \/\  /    \
``````

Note: If / and \ are mapped to ( and ) respectively, the problem is the same as the balanced parentheses.

4. Binary Search Trees

Problem: Given `n`, how many unique binary search tress exist to create node value `1 to n`.

Example:

`````` n  counts  patterns
0  1       *
1  1       1
2  2         2  1
/    \
1      2
3  5           3    3     2    1    1
/    /     / \    \    \
2    1     1   3    3    2
/      \            /      \
1        2          2        3
``````
5. Diagonal Paths

Problem: Given `n x n` grid, how many paths of length `2n` exist from bottom left to upper right corner.

Example:

`````` n  counts  patterns
0  1       *
1  1        ↑
→
2  2         ↑       ↑
↑    ↑ →
→ →    →
3  5           ↑        ↑         ↑        ↑          ↑
↑        ↑      ↑ →      ↑ →           ↑
↑   ↑ → →    ↑ →         ↑         ↑ →
→ → →   →        →         → →      → →
``````

Note: If → and ↑ are mapped to ( and ), the problem is the same as the balanced parentheses.

6. Multiplication orderings

Problem: Given `n+1` numbers to multiply together, how many patterns exist to make multiplication precedences without changing the order of numbers.

Example:

`````` n  counts  patterns
0  1       (a)
1  1       (ab)
2  2       ((ab)c) (a(bc))
3  5       (((ab)c)d) ((ab)(cd)) ((a(bc))d) (a((bc)d)) (a(b(cd)))
``````
7. Polygon Triangulation

Problem: Given `n+2` sides of convex polygon, how many patterns exist to cut into triangles of non-crossing line segments.

8. Handshaking

Problem: Given `2n` people seated around the round table, how many patterns exists to shake hands without crossing arms.

#### Code Example

For all problems above, the number of patterns can be found the code below:

The first `numPatterns` method runs faster if the problem asks only one number such as:

However, when problem asks accumulation of patterns such as:

the second DP solution works to avoid repetition.

#### Resources

Latest Posts

Ruby on Rails Secrets Management

A web application needs various kinds of values, params and etc which should not be revealed to the public, say GitHub repo. For example, API keys, tokens, passwords, and endpoints, all those should be kept secret. Another important factor is that such secrets should be shared among the team members. Additionally, all those secrets should come along with the deployment.

OAuth2 PKCE With Rails 7, React/Redux and esbuild

Logging in to a web site is what users do quite a lot. Suppose it is a blog site. Once a user completes a log-in process, the user is allowed to create a new post, update contents and delete a post. The blog site might have a feature to leave comments by logged in users.

Rails 7 React/Redux Development with esbuild

Rails 7 provides a couple of approaches to bundle a rich JavaScript application such as SPA. To create the JavaScript application, we should specify `j|--javascript` option with importmap (default), webpack, esbuild or rollup when `rails new` command gets run. Although webpack is still among the choices, it has been retired as describe in the https://github.com/rails/webpacker/blob/master/README.md. The choice here is esbuild since it is friendly to JavaScript development, for example, starting from `yarn create react-app ...`. The esbuild is gaining popularity and known to run very fast with its Go-lang implementation.