Find the number of valid parentheses expressions of given length

Dyck path

Last Updated : 11 Apr, 2023

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

dyckpaths

The number of Dyck paths from (n-1, 0) to (0, n-1) can be given by the Catalan numberC(n).
$C_n=\frac{(2n)!}{(n+1)!n1}=\prod_{k=2}^{n}\frac{n+k}{k} \ for\ n\geq 0$

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<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 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

Javascript

<script>
 
// JavaScript program to count
// number of Dyck Paths
 
    // Returns count Dyck 
    // paths in n x n grid
    function countDyckPaths(n)
    {
     
        // Compute value of 2nCn
        let res = 1;
        for (let i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res /= (i + 1);
        }
   
        // return 2nCn/(n+1)
        return res / (n + 1);
    }
 
// Driver Code
 
        let n = 4;
        document.write("Number of Dyck Paths is " +
                                    countDyckPaths(n));
     
    // This code is contributed by target_2.
</script>

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

<?php
// PHP program to count 
// number of Dyck Paths
 
// Returns count Dyck 
// paths in n x n grid
function countDyckPaths( $n)
{
    // Compute value of 2nCn
    $res = 1;
    for ( $i = 0; $i < $n; ++$i)
    {
        $res *= (2 * $n - $i);
        $res /= ($i + 1);
    }
 
    // return 2nCn/(n+1)
    return $res / ($n + 1);
}
 
// Driver Code
$n = 4;
echo "Number of Dyck Paths is " , 
              countDyckPaths($n);
 
// This code is contributed by anuj_67.
?>

Output

Number of Dyck Paths is 14

Time complexity: O(n).
Auxiliary space: O(1).

Exercise :

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.
Number of paths of length m + n from (m-1, 0) to (0, n-1) that are restricted to east and north steps.

Approach 2:-approach to count the number of Dyck paths –In this implementation, we generate all possible Dyck paths of length n by generating all binary numbers with n bits. We then traverse through each bit in the binary representation of the number and update the depth accordingly. If at any point the depth becomes negative, then the path is not a Dyck path, so we break out of the loop. If we reach the end of the path and the depth is zero, then the path is a Dyck path, so we increment the count. Finally, we return the count of Dyck paths.

C++

#include <iostream>
 
using namespace std;
 
// Function to calculate the factorial of a given number
int factorial(int n) {
    int fact = 1;
    for (int i = 1; i <= n; i++) {
        fact *= i;
    }
    return fact;
}
 
// Function to calculate the number of Dyck paths of length n using the 2 approach
int dyck_paths_2(int n) {
    int numerator = factorial(2 * n);
    int denominator = factorial(n + 1) * factorial(n);
    return numerator / denominator;
}
 
int main() {
    int n = 4;
 
    cout << "Number of Dyck paths is " << n << ": " << dyck_paths_2(n) << endl;
 
    return 0;
}

Java

import java.util.*;
 
public class DyckPaths 
{
 
  // Function to calculate the factorial of a given number
  public static int factorial(int n)
  {
    int fact = 1;
    for (int i = 1; i <= n; i++) {
      fact *= i;
    }
    return fact;
  }
 
  // Function to calculate the number of Dyck paths of
  // length n using the 2 approach
  public static int dyck_paths_2(int n)
  {
    int numerator = factorial(2 * n);
    int denominator = factorial(n + 1) * factorial(n);
    return numerator / denominator;
  }
 
  public static void main(String[] args)
  {
    int n = 4;
 
    System.out.println("Number of Dyck paths is " + n
                       + ": " + dyck_paths_2(n));
  }
}
 
// This code is contributed by Prajwal Kandekar

Python3

# Function to calculate the factorial of a given number
def factorial(n):
    fact = 1
    for i in range(1, n + 1):
        fact *= i
    return fact
 
# Function to calculate the number of Dyck paths of length n using the 2 approach
def dyck_paths_2(n):
    numerator = factorial(2 * n)
    denominator = factorial(n + 1) * factorial(n)
    return numerator // denominator
 
if __name__ == '__main__':
    n = 4
    print("Number of Dyck paths is {}: {}".format(n, dyck_paths_2(n)))

Javascript

function factorial(n) {
  let fact = 1;
  for (let i = 1; i <= n; i++) {
    fact *= i;
  }
  return fact;
}
 
function dyckPaths2(n) {
  const numerator = factorial(2 * n);
  const denominator = factorial(n + 1) * factorial(n);
  return numerator / denominator;
}
 
const n = 4;
console.log(`Number of Dyck paths is ${n}: ${dyckPaths2(n)}`);

C#

using System;
 
class Program {
    // Function to calculate the factorial of a given number
    static int Factorial(int n)
    {
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact *= i;
        }
        return fact;
    }
 
    // Function to calculate the number of Dyck paths of
    // length n using the 2 approach
    static int DyckPaths2(int n)
    {
        int numerator = Factorial(2 * n);
        int denominator = Factorial(n + 1) * Factorial(n);
        return numerator / denominator;
    }
 
    static void Main(string[] args)
    {
        int n = 4;
 
        Console.WriteLine("Number of Dyck paths is " + n
                          + ": " + DyckPaths2(n));
    }
}

Output

Number of Dyck paths is 4: 14

Time complexity: O(n).
Auxiliary space: O(1).

Find the number of valid parentheses expressions of given length

Aditya Chatterjee

Improve

Article Tags :

Practice Tags :

Mathematical

Dyck path

We strongly recommend that you click here and practice it, before moving on to the solution.

C++

Java

Python3

Javascript

C#

PHP

C++

Java

Python3

Javascript

C#

Similar Reads

Divisibility & Large Numbers

GCD and LCM

Series

Number Digits

Algebra

Number System

Prime Numbers & Primality Tests

Prime Factorization & Divisors

Modular Arithmetic

Thank You!

What kind of Experience do you want to share?