# 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 numberC(n). ## We strongly recommend that you click here and practice it, before moving on to the solution.

Below are the implementations to find count of Dyck Paths (or n’th Catalan number).

## C++

 `// C++ program to count  ` `// number of Dyck Paths ` `#include ` `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 Code ` `int` `main() ` `{ ` `    ``int` `n = 4; ` `    ``cout << ``"Number of Dyck Paths is "`  `         ``<< countDyckPaths(n); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count ` `// number of Dyck Paths ` `class` `GFG ` `{ ` `    ``// Returns count Dyck  ` `    ``// paths in n x n grid ` `    ``public` `static` `int` `countDyckPaths(``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 code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``int` `n = ``4``; ` `        ``System.out.println(``"Number of Dyck Paths is "` `+ ` `                                    ``countDyckPaths(n)); ` `    ``} ` `} `

## Python3

 `# Python3 program to count  ` `# number of Dyck Paths ` ` `  `# Returns count Dyck  ` `# paths in n x n grid ` `def` `countDyckPaths(n): ` `     `  `    ``# Compute value of 2nCn ` `    ``res ``=` `1` `    ``for` `i ``in` `range``(``0``, n): ` `        ``res ``*``=` `(``2` `*` `n ``-` `i) ` `        ``res ``/``=` `(i ``+` `1``) ` ` `  `    ``# return 2nCn/(n+1) ` `    ``return` `res ``/` `(n``+``1``) ` ` `  `# Driver Code ` `n ``=` `4` `print``(``"Number of Dyck Paths is "``, ` `    ``str``(``int``(countDyckPaths(n)))) ` ` `  `# This code is contributed by ` `# Prasad Kshirsagar `

## C#

 `// C# program to count ` `// number of Dyck Paths ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``// Returns count Dyck  ` `    ``// paths in n x n grid ` `    ``static` `int` `countDyckPaths(``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 code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `n = 4; ` `        ``Console.WriteLine(``"Number of "` `                  ``+ ``"Dyck Paths is "` `+ ` `                   ``countDyckPaths(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` `

Output :

`Number of Dyck Paths is 14`

Exercise :

1. Find number of sequences of 1 and -1 such that every sequence follows below constraints :
a) The length of a sequence is 2n
b) There are equal number of 1’s and -1’s, i.e., n 1’s, n -1s
c) Sum of prefix of every sequence is greater than or equal to 0. For example, 1, -1, 1, -1 and 1, 1, -1, -1 are valid, but -1, -1, 1, 1 is not valid.
2. .

3. Number of paths of length m + n from (m-1, 0) to (0, n-1) that are restricted to east and north steps.

## tags:

Mathematical catalan Mathematical