Open In App

Applications of Catalan Numbers

Last Updated : 01 Feb, 2023
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Background :

Catalan numbers are defined using below formula:
 C_{n} = (2n)!/(n+1)!n! = \prod^{n}_{k=2} \frac{n+k}{k} for_ n >= 0

Catalan numbers can also be defined using following recursive formula.
 C_{0} = 1 C_{n+1} = \sum ^{n} _{i=0} C_{i}C_{n-i} for_ n>=0

The first few Catalan numbers for n = 0, 1, 2, 3, … are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … 

Refer this for implementation of n’th Catalan Number.

Applications :

  1. Number of possible Binary Search Trees with n keys.
  2. Number of expressions containing n pairs of parentheses which are correctly matched. For n = 3, possible expressions are ((())), ()(()), ()()(), (())(), (()()).
  3. Number of ways a convex polygon of n+2 sides can split into triangles by connecting vertices. 
    convex
  4. Number of full binary trees (A rooted binary tree is full if every vertex has either two children or no children) with n+1 leaves.
  5. Number of different Unlabeled Binary Trees can be there with n nodes.
  6. The number of paths with 2n steps on a rectangular grid from bottom left, i.e., (n-1, 0) to top right (0, n-1) that do not cross above the main diagonal.
     rectangle
  7. Number of ways to insert n pairs of parentheses in a word of n+1 letters, e.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)). For n=3 there are 5 ways, ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).
  8. Number of noncrossing partitions of the set {1, …, 2n} in which every block is of size 2. A partition is noncrossing if and only if in its planar diagram, the blocks are disjoint (i.e. don’t cross). For example, below two are crossing and non-crossing partitions of {1, 2, 3, 4, 5, 6, 7, 8, 9}.  The partition {{1, 5, 7},  {2, 3, 8}, {4, 6}, {9}} is crossing and partition {{1, 5, 7}, {2, 3}, {4}, {6}, {8, 9}} is non-crossing. 
    partitiom
  9. Number of Dyck words of length 2n. A Dyck word is a string consisting of n X’s and n Y’s such that no initial segment of the string has more Y’s than X’s.  For example, the following are the Dyck words of length 6: XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.
  10. Number of ways to tile a stairstep shape of height n with n rectangles. The following figure illustrates the case n = 4: 
    stair
  11. Number of ways to connect the points on a circle disjoint chords.  This is similar to point 3 above.
  12. Number of ways to form a “mountain ranges” with n upstrokes and n down-strokes that all stay above the original line.The mountain range interpretation is that the mountains will never go below the horizon.
    Mountain_Ranges
  13. Number of stack-sortable permutations of {1, …, n}. A permutation w is called stack-sortable if S(w) = (1, …, n), where S(w) is defined recursively as follows: write w = unv where n is the largest element in w and u and v are shorter sequences, and set S(w) = S(u)S(v)n, with S being the identity for one-element sequences.
  14. Number of permutations of {1, …, n} that avoid the pattern 123 (or any of the other patterns of length 3); that is, the number of permutations with no three-term increasing subsequence. For n = 3, these permutations are 132, 213, 231, 312 and 321. For n = 4, they are 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312 and 4321

Sources:

  1. https://en.wikipedia.org/wiki/Catalan_number
  2. http://mathworld.wolfram.com/CatalanNumber.html
  3. http://www-groups.dcs.st-and.ac.uk/history/Miscellaneous/CatalanNumbers/catalan.html
  4. http://www.mhhe.com/math/advmath/rosen/r5/instructor/applications/ch07.pdf
  5. https://oeis.org/A000108

 


Previous Article
Next Article

Similar Reads

GFact | Catalan Numbers
The number of structurally different Binary Trees with n nodes is Catalan number Cn = (2n)!/(n+1)!*n! References: http://mathworld.wolfram.com/BinaryTree.html
1 min read
Minimum changes required to make a Catalan Sequence
Given an array arr[] of N integer elements, the task is to change the minimum number of elements of this array such that it contains first N terms of the Catalan Sequence. Thus, find the minimum changes required.First few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, .....Examples: Input: arr[] = {4, 1, 2, 33, 213, 5} Output: 3 We h
8 min read
Total number of possible Binary Search Trees using Catalan Number
Given an integer N, the task is to count the number of possible Binary Search Trees with N keys. Examples: Input: N = 2 Output: 2 For N = 2, there are 2 unique BSTs 1 2 \ / 2 1 Input: N = 9 Output: 4862 Approach: The number of binary search trees that will be formed with N keys can be calculated by simply evaluating the corresponding number in Cata
13 min read
Program for nth Fuss–Catalan Number
Fuss–Catalan Numbers are a generalization of Catalan numbers that uses triplets instead of pairs. The Fuss-Catalan Numbers can be represented by a Series with the formula: The first few Fuss–Catalan Numbers are 1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675...........for n = 0, 1, 2, 3, ... respectively Applications of Fuss-Catalan number: Count t
5 min read
Replace every node in Linked list with its closest catalan number
Given a singly linked list, the task is to replace every node with its closest Catalan number. Note: Catalan numbers are defined as mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations. The first few Catalan numbers are: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862. Exam
4 min read
Find product of nodes whose weights is catalan number in a Linked list
Given a linked list with weights, the task is to find the product of nodes whose weights are Catalan numbers. Examples: Input: 3(1) -> 7 (4) -> 5 (2) -> 12 (5) -> 14 (3) -> NULLOutput: 180Explanation: Catalan number weights are 1, 2, and 5, and the product of their nodes is 3 * 5 * 12 = 180. Input: 45 (4) -> 21 (2) -> 5 (5) -
11 min read
Program for nth Catalan Number
Catalan numbers are defined as a mathematical sequence that consists of positive integers, which can be used to find the number of possibilities of various combinations. The nth term in the sequence denoted Cn, is found in the following formula: [Tex]\frac{(2n)!}{((n + 1)! n!)} [/Tex] The first few Catalan numbers for n = 0, 1, 2, 3, … are : 1, 1,
15+ min read
Print numbers such that no two consecutive numbers are co-prime and every three consecutive numbers are co-prime
Given an integer N, the task is to print N integers ? 109 such that no two consecutive of these integers are co-prime and every 3 consecutive are co-prime. Examples: Input: N = 3 Output: 6 15 10Input: N = 4 Output: 6 15 35 14 Approach: We can just multiply consecutive primes and for the last number just multiply the gcd(last, last-1) * 2. We do thi
15+ min read
Kth element in permutation of first N natural numbers having all even numbers placed before odd numbers in increasing order
Given two integers N and K, the task is to find the Kth element in the permutation of first N natural numbers arranged such that all the even numbers appear before the odd numbers in increasing order. Examples : Input: N = 10, K = 3 Output: 6Explanation:The required permutation is {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}.The 3rd number in the permutation is
9 min read
Count of numbers of length N having prime numbers at odd indices and odd numbers at even indices
Given a number N, the task is to calculate the count of numbers of length N having prime numbers at odd indices and odd numbers at even indices. Example: Input : N = 1Output: 5Explanation : All valid numbers length 1 are 1, 3, 5, 7, 9, here we have only 1 odd index, therefore we have 5 valid numbers. Input: N = 2Output: 20 Explanation: There are 20
5 min read
Applications of Queue Data Structure
Introduction : A queue is a linear data structure that follows the "first-in, first-out" (FIFO) principle. It is a collection of elements that supports two primary operations - enqueue and dequeue. In the enqueue operation, an element is added to the back of the queue, while in the dequeue operation, an element is removed from the front of the queu
5 min read
Analysis and applications Karger’s algorithm for Minimum Cut
We have introduced and discussed below Karger's algorithm in set 1. 1) Initialize contracted graph CG as copy of original graph 2) While there are more than 2 vertices. a) Pick a random edge (u, v) in the contracted graph. b) Merge (or contract) u and v into a single vertex (update the contracted graph). c) Remove self-loops 3) Return cut represent
4 min read
Deque | Set 1 (Introduction and Applications)
Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends. Operations on Deque: Below is a table showing some basic operations along with their time complexity, performed on deques. Operation Description Time Complexitypush_front() Inserts the element at the beginning. O(1) push_back() A
5 min read
Applications, Advantages and Disadvantages of Circular Doubly Linked List
The circular doubly linked list is a combination of the doubly linked list and the circular linked list. It means that this linked list is bidirectional and contains two pointers and the last pointer points to the first pointer. Applications of Circular Doubly Linked List: Music and video playlists: Circular doubly linked lists are commonly used to
4 min read
Applications of Graph Data Structure
A graph is a non-linear data structure, which consists of vertices(or nodes) connected by edges(or arcs) where edges may be directed or undirected. In Computer science graphs are used to represent the flow of computation.Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vert
3 min read
Applications of linked list data structure
A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: Applications of linked list in computer science:Implementation of stacks and queuesImplementation of graphs: Adjacency list representation of graphs is th
5 min read
Applications, Advantages and Disadvantages of Doubly Linked List
Doubly linked list is a type of linked list in which nodes contains information and two pointers i.e. left pointer and right pointer. The left pointer in the doubly linked list points to the previous node and the right pointer points to the next node in the linked list. The first node of the doubly linked list has NULL in its left pointer and the l
4 min read
Class 10 RD Sharma Solutions - Chapter 12 Some Applications of Trigonometry - Exercise 12.1 | Set 3
Question 53. From the top of a building AB, 60 m high, the angles of depression of the top and bottom of a vertical lamp post CD are observed to be 30° and 60° respectively. Find (i) the horizontal distance between AB and CD. (ii) the height of the lamp post (iii) the difference between the heights of the building and the lamp post. Solution: Let u
15+ min read
Abstract data types, Applications, Advantages and Disadvantages of Circular Queue
Circular Queue is a linear data structure that follows FIFO (first in first out) principle which means the item that is inserted first in the queue can be taken out first. It is also known as circular/ring buffer because the last position of the queue is circled back and connected with the first element thereby, forming a circular structure. Abstar
3 min read
Different Types of Queues and its Applications
Introduction : A Queue is a linear structure that follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first. In this article, the different types of queues are discussed. Types of Queu
8 min read
Class 10 RD Sharma Solutions - Chapter 12 Some Applications of Trigonometry - Exercise 12.1 | Set 2
Question 27. A T.V. tower stands vertically on a bank of a river of a river. From a point on the other bank directly opposite the tower, the angle of elevation of the top of the tower is 60°. From a point 20 m away this point on the same bank, the angle of elevation of the top of the tower is 30°. Find the height of the tower and the width of the r
15+ min read
Applications of Dijkstra's shortest path algorithm
Dijkstra’s algorithm is one of the most popular algorithms for solving many single-source shortest path problems having non-negative edge weight in the graphs i.e., it is to find the shortest distance between two vertices on a graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. Dijkstra’s Algori
4 min read
Applications of String Matching Algorithms
String matching algorithms have greatly influenced computer science and play an essential role in various real-world problems. It helps in performing time-efficient tasks in multiple domains. These algorithms are useful in the case of searching a string within another string. String matching is also used in the Database schema, Network systems.Let
5 min read
Top 12 Data Structure Algorithms to Implement in Practical Applications in 2021
New Year...New Beginning...!!! What's your plan for this year??? (Being a programmer) Of course, if you're a programmer then this year you will also write the code, build the projects and you will solve a lot of coding questions. Let's talk about Data Structures and Algorithms... Heart of computer science and the programmer's breath to live in the
14 min read
Applications, Advantages and Disadvantages of Red-Black Tree
Red-Black Tree is one type of self-balancing tree where each node has one extra bit that is often interpreted as colour of the node. This bit (the colour) is used to ensure that the tree remains balanced. Properties of Red-Black Trees: Red-Black Trees have the accompanying properties: Each hub has a variety.The root is black.Each leaf is an excepti
4 min read
Applications, Advantages and Disadvantages of Array
Array is a linear data structure that is a collection of similar data types. Arrays are stored in contiguous memory locations. It is a static data structure with a fixed size. It combines data of similar types. Applications of Array Data Structure: Below are some applications of arrays. Storing and accessing data: Arrays are used to store and retri
7 min read
Applications, Advantages and Disadvantages of Directed Graph
Directed graphs are graphs that have directed edges between the nodes. If a directed edge points from u to v then, v is adjacent to u and u is adjacent to v. In the directed graph edges have directions and indicated with an arrow on edge. Directed graph is also known as Digraph. Applications of Directed Graph: Directed graphs are used to find the s
2 min read
Applications, Advantages and Disadvantages of Unweighted Graph
An unweighted graph is a graph in which the edges do not have weights or costs associated with them. Instead, they simply represent the presence of a connection between two vertices. In this article we will explore the simplicity of unweighted graphs, where connections between vertices are represented without the complexity of edge weights. From so
3 min read
Applications, Advantages and Disadvantages of Deque
Deque is a type of queue in which insert and deletion can be performed from either front or rear. It does not follow the FIFO rule. It is also known as double-ended queue Operations on Deque: Deque consists of mainly the following operations: Insert FrontInsert RearDelete FrontDelete Rear 1. Insert at the Front: This operation is used to add an ele
4 min read
What is Weighted Graph with Applications, Advantages and Disadvantages
What is Weighted Graph? A weighted graph is defined as a special type of graph in which the edges are assigned some weights which represent cost, distance, and many other relative measuring units. Applications of Weighted Graph:2D matrix games: In 2d matrix, games can be used to find the optimal path for maximum sum along starting to ending points
5 min read
Practice Tags :
three90RightbarBannerImg