Dyck path

Consider a n x n grid with indexes of top left corner as (0, 0). Dyck path is a staircase walk from bottom left, i.e., (n-1, 0) to top right, i.e., (0, n-1) that lies above the diagonal cells (or cells on line from bottom left to top right).

The task is to count the number of Dyck Paths from (n-1, 0) to (0, n-1).

Examples :

Input : n = 1
Output : 1

Input : n = 2
Output : 2

Input : n = 3
Output : 5

Input : n = 4
Output : 14

The number of Dyck paths from (n-1, 0) to (0, n-1) can be given by the Catalan number C(n).

// C++ program to count number of Dyck Paths #include<iostream> using namespace std; // Returns count Dyck paths in n x n grid int countDyckPaths(unsigned int n) {     // Compute value of 2nCn     int res = 1;     for (int i = 0; i < n; ++i)     {         res *= (2*n - i);         res /= (i + 1);     }     // return 2nCn/(n+1)     return res / (n+1); } // Driver program to test above functions int main() {     int n = 4;     cout << "Number of Dyck Paths is " << countDyckPaths(n);     return 0; } Output: Number of Dyck Paths is 14