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

Setting Up GCP Instance for Deep Learning

This post is going to be very different from what I write here. The content is a memo how I create a GCP (Google Cloud Platform) instance for Deep Learning. While I study algorithm stuff, I also have been studying Deep Learning. In my early days, I tried to train my Deep Learning model only on a laptop. My laptop is 2012 model MacBook Pro, so I would say it is reasonably fast. However, when it comes to Deep Learning, the training was quite painful on the such machine. Often, I ran the training over night to get a disappointed result. Still, I didn’t use any of pricey cloud environment since it was my personal study unrelated to my day job. I wanted to save money.

Complete Binary Tree

Problems which ask a binary tree traverse, add/delete nodes, etc. are popular in algorithm questions. The binary trees are often just a binary tree or binary search tree. Sometimes, the problem pinpoints a particular type of a binary tree, for example, a balanced binary tree or complete binary tree.

Catalan number

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.