Dyck Palabras de longitud dada

Dado un número entero n , la tarea es contar las palabras Dyck posibles de longitud n . Una palabra DYCK es una palabra que contiene solo los caracteres ‘X’ e ‘Y’ de modo que en cada prefijo de la palabra frecuencia(‘X’) ≥ frecuencia(‘Y’)
Ejemplos: 
 

Entrada: n = 2 
Salida: 2 
“XY” y “XX” son las únicas palabras DYCK posibles de longitud 2.
Entrada: n = 5 
Salida: 42 
 

Acercarse: 
 

Interpretación Geométrica: Se basa en la idea de DYCK PATH. 
 

Los diagramas anteriores representan RUTAS DE DYCK de (0, 0) a (n, n). 
 

Una RUTA DE DYCK contiene n segmentos de línea horizontal y n segmentos de línea vertical que no cruzan el segmento AB. 
La idea principal detrás de este problema es encontrar el número total de rutas DYCK de (0, 0) a (n, n). 
Para abordar este problema la idea principal es encontrar el número total de caminos de Distancia Manhattan entre (0, 0) a (n, n) y excluir todos aquellos caminos que cruzan el segmento AB.
 

¿Cómo calcular el número de caminos que cruzan el segmento AB? 
Llamemos a todos esos caminos que cruzan AB como ‘incorrectos’. Los caminos ‘incorrectos’ que cruzan AB deben pasar por la línea CD. 
 

1. Tome la simetría del punto A a través de la línea A.
2. Dibujar una línea simétrica de la línea incorrecta tomando como referencia CD.

 

Un CD con línea simétrica.
 

FG-Línea simétrica de una línea incorrecta.
 

Todas aquellas rectas que cruzan AB su recta simétrica que empieza en F termina en G(n-1, n+1).
Por lo tanto, el número de líneas incorrectas es: 
^{2 * n} C _{n – 1}
Por lo tanto, el número de palabras DYCK con n ‘X’ y n ‘Y’ es: 
^{2 * n} C _n – ^{2 * n} C _{n – 1} = (2 * n )! / (n)! * (n + 1)! 
 

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <iostream>
using namespace std;
 
// Function to return the count of
// Dyck Words of length n possible
long long int count_Dyck_Words(unsigned int n)
{
    // Calculate the value of 2nCn
    long long 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 = 5;
    cout << count_Dyck_Words(n);
    return 0;
}

// Java implementation of the approach
class GFG
{
     
// Function to return the count of
// Dyck Words of length n possible
static int count_Dyck_Words( int n)
{
    // Calculate the 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 = 5;
    System.out.println(count_Dyck_Words(n));
}
}
 
// This code is Contributed by Code_Mech.

# Python3 implementation of the approach
 
# Function to return the count of
# Dyck Words of length n possible
def count_Dyck_Words(n) :
     
    # Calculate the value of 2nCn
    res = 1;
    for i in range(n) :
        res *= (2 * n - i);
        res //= (i + 1);
     
    # Return 2nCn/(n+1)
    return (res / (n + 1));
 
# Driver Code
if __name__ == "__main__" :
 
    n = 5;
    print(count_Dyck_Words(n));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the count of
// Dyck Words of length n possible
static int count_Dyck_Words( int n)
{
    // Calculate the 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 = 5;
    Console.WriteLine(count_Dyck_Words(n));
}
}
 
// This code is Contributed by Code_Mech.

<?php
// PHP implementation of the approach
 
// Function to return the count of
// Dyck Words of length n possible
function count_Dyck_Words( $n)
{
    // Calculate the 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 = 5;
echo(count_Dyck_Words($n));
 
// This code is contributed
// by Code_Mech.
?>

<script>
    // Javascript implementation of the approach
     
    // Function to return the count of
    // Dyck Words of length n possible
    function count_Dyck_Words(n)
    {
        // Calculate the value of 2nCn
        let res = 1;
        for (let i = 0; i < n; ++i)
        {
            res *= (2 * n - i);
            res = parseInt(res / (i + 1), 10);
        }
 
        // Return 2nCn/(n+1)
        return parseInt(res / (n + 1), 10);
    }
     
    let n = 5;
    document.write(count_Dyck_Words(n));
     
    // This code is contributed by suresh07.
</script>

42