Programa para el enésimo Número Catalán

Los números catalanes son una secuencia de números naturales que se presenta en muchos problemas de conteo interesantes como los siguientes.

1. Cuente el número de expresiones que contienen n pares de paréntesis que coinciden correctamente. Para n = 3, las expresiones posibles son ((())),()(()),()()(), (())(), (()()).
2. Cuente el número de posibles árboles binarios de búsqueda con n claves (ver esto )
3. Cuente el número de árboles binarios completos (un árbol binario enraizado está lleno si cada vértice tiene dos hijos o ningún hijo) con n+1 hojas.
4. Dado un número n, devuelva el número de formas en que puede dibujar n cuerdas en un círculo con 2 xn puntos de modo que no se crucen 2 cuerdas.

Vea esto para más aplicaciones. 
Los primeros números catalanes para n = 0, 1, 2, 3,… son 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…  

#include <iostream>
using namespace std;
 
// A recursive function to find nth catalan number
unsigned long int catalan(unsigned int n)
{
    // Base case
    if (n <= 1)
        return 1;
 
    // catalan(n) is sum of
    // catalan(i)*catalan(n-i-1)
    unsigned long int res = 0;
    for (int i = 0; i < n; i++)
        res += catalan(i)
            * catalan(n - i - 1);
 
    return res;
}
 
// Driver code
int main()
{
    for (int i = 0; i < 10; i++)
        cout << catalan(i) << " ";
    return 0;
}

class CatalnNumber {
 
    // A recursive function to find nth catalan number
 
    int catalan(int n)
    {
        int res = 0;
 
        // Base case
        if (n <= 1)
        {
            return 1;
        }
        for (int i = 0; i < n; i++)
        {
            res += catalan(i)
                * catalan(n - i - 1);
        }
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        CatalnNumber cn = new CatalnNumber();
        for (int i = 0; i < 10; i++)
        {
            System.out.print(cn.catalan(i) + " ");
        }
    }
}

# A recursive function to
# find nth catalan number
def catalan(n):
    # Base Case
    if n <= 1:
        return 1
 
    # Catalan(n) is the sum
    # of catalan(i)*catalan(n-i-1)
    res = 0
    for i in range(n):
        res += catalan(i) * catalan(n-i-1)
 
    return res
 
 
# Driver Code
for i in range(10):
    print (catalan(i),end=" ")
# This code is contributed by
# Nikhil Kumar Singh (nickzuck_007)

// A recursive C# program to find
// nth catalan number
using System;
 
class GFG {
 
    // A recursive function to find
    // nth catalan number
    static int catalan(int n)
    {
        int res = 0;
 
        // Base case
        if (n <= 1)
        {
            return 1;
        }
        for (int i = 0; i < n; i++)
        {
            res += catalan(i)
                * catalan(n - i - 1);
        }
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
        for (int i = 0; i < 10; i++)
            Console.Write(catalan(i) + " ");
    }
}
 
// This code is contributed by
// nitin mittal.

<?php
// PHP Program for nth
// Catalan Number
 
// A recursive function to
// find nth catalan number
function catalan($n)
{
     
    // Base case
    if ($n <= 1)
        return 1;
 
    // catalan(n) is sum of
    // catalan(i)*catalan(n-i-1)
    $res = 0;
    for($i = 0; $i < $n; $i++)
        $res += catalan($i) *
                catalan($n - $i - 1);
 
    return $res;
}
 
// Driver Code
for ($i = 0; $i < 10; $i++)
    echo catalan($i), " ";
 
// This code is contributed aj_36
?>

<script>
 
// Javascript Program for nth
// Catalan Number
 
// A recursive function to
// find nth catalan number
function catalan(n)
{
     
    // Base case
    if (n <= 1)
        return 1;
 
    // catalan(n) is sum of
    // catalan(i)*catalan(n-i-1)
    let res = 0;
    for(let i = 0; i < n; i++)
        res += catalan(i) *
                catalan(n - i - 1);
 
    return res;
}
 
// Driver Code
for (let i = 0; i < 10; i++)
    document.write(catalan(i) + " ");
 
// This code is contributed _saurabh_jaiswal
 
</script>

#include <iostream>
using namespace std;
 
// A dynamic programming based function to find nth
// Catalan number
unsigned long int catalanDP(unsigned int n)
{
    // Table to store results of subproblems
    unsigned long int catalan[n + 1];
 
    // Initialize first two values in table
    catalan[0] = catalan[1] = 1;
 
    // Fill entries in catalan[] using recursive formula
    for (int i = 2; i <= n; i++) {
        catalan[i] = 0;
        for (int j = 0; j < i; j++)
            catalan[i] += catalan[j] * catalan[i - j - 1];
    }
 
    // Return last entry
    return catalan[n];
}
 
// Driver code
int main()
{
    for (int i = 0; i < 10; i++)
        cout << catalanDP(i) << " ";
    return 0;
}

class GFG {
 
    // A dynamic programming based function to find nth
    // Catalan number
    static int catalanDP(int n)
    {
        // Table to store results of subproblems
        int catalan[] = new int[n + 2];
 
        // Initialize first two values in table
        catalan[0] = 1;
        catalan[1] = 1;
 
        // Fill entries in catalan[]
        // using recursive formula
        for (int i = 2; i <= n; i++) {
            catalan[i] = 0;
            for (int j = 0; j < i; j++) {
                catalan[i]
                    += catalan[j] * catalan[i - j - 1];
            }
        }
 
        // Return last entry
        return catalan[n];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < 10; i++) {
            System.out.print(catalanDP(i) + " ");
        }
    }
}
// This code contributed by Rajput-Ji

# A dynamic programming based function to find nth
# Catalan number
 
 
def catalan(n):
    if (n == 0 or n == 1):
        return 1
 
    # Table to store results of subproblems
    catalan =[0]*(n+1)
 
    # Initialize first two values in table
    catalan[0] = 1
    catalan[1] = 1
 
    # Fill entries in catalan[]
    # using recursive formula
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j]* catalan[i-j-1]
 
    # Return last entry
    return catalan[n]
 
 
# Driver code
for i in range(10):
    print(catalan(i), end=" ")
# This code is contributed by Ediga_manisha

using System;
 
class GFG {
 
    // A dynamic programming based
    // function to find nth
    // Catalan number
    static uint catalanDP(uint n)
    {
        // Table to store results of subproblems
        uint[] catalan = new uint[n + 2];
 
        // Initialize first two values in table
        catalan[0] = catalan[1] = 1;
 
        // Fill entries in catalan[]
        // using recursive formula
        for (uint i = 2; i <= n; i++) {
            catalan[i] = 0;
            for (uint j = 0; j < i; j++)
                catalan[i]
                    += catalan[j] * catalan[i - j - 1];
        }
 
        // Return last entry
        return catalan[n];
    }
 
    // Driver code
    static void Main()
    {
        for (uint i = 0; i < 10; i++)
            Console.Write(catalanDP(i) + " ");
    }
}
 
// This code is contributed by Chandan_jnu

<?php
// PHP program for nth Catalan Number
 
// A dynamic programming based function
// to find nth Catalan number
function catalanDP( $n)
{
     
    // Table to store results
    // of subproblems
    $catalan= array();
 
    // Initialize first two
    // values in table
    $catalan[0] = $catalan[1] = 1;
 
    // Fill entries in catalan[]
    // using recursive formula
    for ($i = 2; $i <= $n; $i++)
    {
        $catalan[$i] = 0;
        for ( $j = 0; $j < $i; $j++)
            $catalan[$i] += $catalan[$j] *
                   $catalan[$i - $j - 1];
    }
 
    // Return last entry
    return $catalan[$n];
}
 
    // Driver Code
    for ($i = 0; $i < 10; $i++)
        echo catalanDP($i) , " ";
 
// This code is contributed anuj_67.
?>

<script>
// Javascript program for nth Catalan Number
 
// A dynamic programming based function
// to find nth Catalan number
function catalanDP(n)
{
     
    // Table to store results
    // of subproblems
    let catalan= [];
 
    // Initialize first two
    // values in table
    catalan[0] = catalan[1] = 1;
 
    // Fill entries in catalan[]
    // using recursive formula
    for (let i = 2; i <= n; i++)
    {
        catalan[i] = 0;
        for (let j = 0; j < i; j++)
            catalan[i] += catalan[j] *
                   catalan[i - j - 1];
    }
 
    // Return last entry
    return catalan[n];
}
 
    // Driver Code
    for (let i = 0; i < 10; i++)
        document.write(catalanDP(i) + " ");
 
// This code is contributed _saurabh_jaiswal
</script>

// C++ program for nth Catalan Number
#include <iostream>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
unsigned long int binomialCoeff(unsigned int n,
                                unsigned int k)
{
    unsigned long int res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] /
    // [k*(k-1)*---*1]
    for (int i = 0; i < k; ++i) {
        res *= (n - i);
        res /= (i + 1);
    }
 
    return res;
}
 
// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned long int catalan(unsigned int n)
{
    // Calculate value of 2nCn
    unsigned long int c = binomialCoeff(2 * n, n);
 
    // return 2nCn/(n+1)
    return c / (n + 1);
}
 
// Driver code
int main()
{
    for (int i = 0; i < 10; i++)
        cout << catalan(i) << " ";
    return 0;
}

// Java program for nth Catalan Number
 
class GFG {
 
    // Returns value of Binomial Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Calculate value of [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function
    //  to find nth catalan number in O(n) time
    static long catalan(int n)
    {
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        for (int i = 0; i < 10; i++) {
            System.out.print(catalan(i) + " ");
        }
    }
}

# Python program for nth Catalan Number
# Returns value of Binomial Coefficient C(n, k)
 
 
def binomialCoefficient(n, k):
 
    # since C(n, k) = C(n, n - k)
    if (k > n - k):
        k = n - k
 
    # initialize result
    res = 1
 
    # Calculate value of [n * (n-1) *---* (n-k + 1)]
    # / [k * (k-1) *----* 1]
    for i in range(k):
        res = res * (n - i)
        res = res / (i + 1)
    return res
 
# A Binomial coefficient based function to
# find nth catalan number in O(n) time
 
 
def catalan(n):
    c = binomialCoefficient(2*n, n)
    return c/(n + 1)
 
# Driver Code
for i in range(10):
    print(catalan(i), end=" ")
 
# This code is contributed by Aditi Sharma

// C# program for nth Catalan Number
using System;
class GFG {
 
    // Returns value of Binomial Coefficient C(n, k)
    static long binomialCoeff(int n, int k)
    {
        long res = 1;
 
        // Since C(n, k) = C(n, n-k)
        if (k > n - k) {
            k = n - k;
        }
 
        // Calculate value of [n*(n-1)*---*(n-k+1)] /
        // [k*(k-1)*---*1]
        for (int i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
 
    // A Binomial coefficient based function to find nth
    // catalan number in O(n) time
    static long catalan(int n)
    {
        // Calculate value of 2nCn
        long c = binomialCoeff(2 * n, n);
 
        // return 2nCn/(n+1)
        return c / (n + 1);
    }
 
    // Driver code
    public static void Main()
    {
        for (int i = 0; i < 10; i++) {
            Console.Write(catalan(i) + " ");
        }
    }
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program for nth Catalan Number
 
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    $res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if ($k > $n - $k)
        $k = $n - $k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] /
    //                    [k*(k-1)*---*1]
    for ($i = 0; $i < $k; ++$i)
    {
        $res *= ($n - $i);
        $res = floor($res / ($i + 1));
    }
 
    return $res;
}
 
// A Binomial coefficient based function
// to find nth catalan number in O(n) time
function catalan($n)
{
    // Calculate value of 2nCn
    $c = binomialCoeff(2 * ($n), $n);
 
    // return 2nCn/(n+1)
    return floor($c / ($n + 1));
}
 
// Driver code
for ($i = 0; $i < 10; $i++)
echo catalan($i), " " ;
 
// This code is contributed by Ryuga
?>

<script>
// Javascript program for nth Catalan Number
 
// Returns value of Binomial
// Coefficient C(n, k)
function binomialCoeff(n, k)
{
    let res = 1;
 
    // Since C(n, k) = C(n, n-k)
    if (k > n - k)
        k = n - k;
 
    // Calculate value of [n*(n-1)*---*(n-k+1)] /
    //                    [k*(k-1)*---*1]
    for (let i = 0; i < k; ++i)
    {
        res *= (n - i);
        res = Math.floor(res / (i + 1));
    }
 
    return res;
}
 
// A Binomial coefficient based function
// to find nth catalan number in O(n) time
function catalan(n)
{
 
    // Calculate value of 2nCn
    c = binomialCoeff(2 * (n), n);
 
    // return 2nCn/(n+1)
    return Math.floor(c / (n + 1));
}
 
// Driver code
for (let i = 0; i < 10; i++)
document.write(catalan(i) + " " );
 
// This code is contributed by _saurabh_jaiswal
</script>

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;
using namespace std;
 
// Function to print the number
void catalan(int n)
{
    cpp_int cat_ = 1;
 
    // For the first number
    cout << cat_ << " "; // C(0)
 
    // Iterate till N
    for (cpp_int i = 1; i <=n; i++)
    {
        // Calculate the number
        // and print it
        cat_ *= (4 * i - 2);
        cat_ /= (i + 1);
        cout << cat_ << " ";
    }
}
 
// Driver code
int main()
{
    int n = 5;
 
    // Function call
    catalan(n);
    return 0;
}

import java.util.*;
class GFG
{
   
// Function to print the number
static void catalan(int n)
{
    int cat_ = 1;
 
    // For the first number
    System.out.print(cat_+" "); // C(0)
 
    // Iterate till N
    for (int i = 1; i < n; i++)
    {
        // Calculate the number
        // and print it
        cat_ *= (4 * i - 2);
        cat_ /= (i + 1);
        System.out.print(cat_+" ");
    }
}
 
// Driver code
public static void main(String args[])
{
    int n = 5;
 
    // Function call
    catalan(n);
}
}
 
// This code is contributed by Debojyoti Mandal

# Function to print the number
def catalan(n):
     
    cat_ = 1
 
    # For the first number
    print(cat_, " ", end = '')# C(0)
 
    # Iterate till N
    for i in range(1, n):
         
        # Calculate the number
        # and print it
        cat_ *= (4 * i - 2);
        cat_ //= (i + 1);
        print(cat_, " ", end = '')
 
# Driver code
n = 5
 
# Function call
catalan(n)
 
# This code is contributed by rohan07

using System;
 
public class GFG {
 
    // Function to print the number
    static void catalan(int n) {
        int cat_ = 1;
 
        // For the first number
        Console.Write(cat_ + " "); // C(0)
 
        // Iterate till N
        for (int i = 1; i < n; i++) {
            // Calculate the number
            // and print it
            cat_ *= (4 * i - 2);
            cat_ /= (i + 1);
            Console.Write(cat_ + " ");
        }
    }
 
    // Driver code
    public static void Main(String []args) {
        int n = 5;
 
        // Function call
        catalan(n);
    }
}
 
// This code is contributed by Rajput-Ji

<script>
 
// Function to print the number
function catalan(n)
{
    let cat_ = 1;
 
    // For the first number
    document.write(cat_ + " "); // C(0)
 
    // Iterate till N
    for (let i = 1; i < n; i++)
    {
        // Calculate the number
        // and print it
        cat_ *= (4 * i - 2);
        cat_ /= (i + 1);
        document.write(cat_ + " ");
    }
}
 
// Driver code
    let n = 5;
 
    // Function call
    catalan(n);
 
//This code is contributed by Mayank Tyagi
</script>

import java.io.*;
import java.util.*;
import java.math.*;
 
class GFG
{
    public static BigInteger findCatalan(int n)
    {
        // using BigInteger to calculate large factorials
        BigInteger b = new BigInteger("1");
 
        // calculating n!
        for (int i = 1; i <= n; i++) {
            b = b.multiply(BigInteger.valueOf(i));
        }
 
        // calculating n! * n!
        b = b.multiply(b);
 
        BigInteger d = new BigInteger("1");
 
        // calculating (2n)!
        for (int i = 1; i <= 2 * n; i++) {
            d = d.multiply(BigInteger.valueOf(i));
        }
 
        // calculating (2n)! / (n! * n!)
        BigInteger ans = d.divide(b);
 
        // calculating (2n)! / ((n! * n!) * (n+1))
        ans = ans.divide(BigInteger.valueOf(n + 1));
        return ans;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        int n = 5;
        System.out.println(findCatalan(n));
    }
}
// Contributed by Rohit Oberoi

// C# code to implement the approach
using System;
using System.Numerics;
 
class GFG {
  public static BigInteger findCatalan(int n)
  {
    // using BigInteger to calculate large factorials
    BigInteger b = new BigInteger(1);
 
    // calculating n!
    for (int i = 1; i <= n; i++) {
      b = BigInteger.Multiply(b, new BigInteger(i));
    }
 
    // calculating n! * n!
    b = BigInteger.Multiply(b, b);
 
    BigInteger d = new BigInteger(1);
 
    // calculating (2n)!
    for (int i = 1; i <= 2 * n; i++) {
      d = BigInteger.Multiply(d, new BigInteger(i));
    }
 
    // calculating (2n)! / (n! * n!)
    BigInteger ans = BigInteger.Divide(d, b);
 
    // calculating (2n)! / ((n! * n!) * (n+1))
    ans = BigInteger.Divide(ans, new BigInteger(n + 1));
    return ans;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    int n = 5;
    Console.WriteLine(findCatalan(n));
  }
}
 
// This code is contributed by phasing17.