Module: números catalanes


Problem

1 /2


Número de números catalanes

Theory Click to read/hide

¿Dónde aparecen los números catalanes?
 

-Número de psp con un número determinado de pares de corchetes
-Número de árboles binarios con un número determinado de hojas
-Número de caminos desde la esquina inferior izquierda hasta la esquina superior derecha en el cuadrado n * n que no tocan la diagonal

-Número de divisiones del n-ágono en triángulos



¿Cómo contar?
 
1) Fórmula del enésimo número catalán:



2)
•Vamos a tener un PSS de longitud 2n
•Obviamente comienza con una llave de apertura
•Entonces, digamos P = (A)B, donde A y B – también psp (además, A y B pueden estar vacíos)
•Si la longitud de A = 2k, entonces la secuencia A se puede componer de Ck formas
•Entonces la longitud de B = 2(n – k - 1) y B se puede componer de formas Cn-k-1

Problem

Salida N-ésimo número de catalán

Entrada
La primera línea de la entrada contiene un solo número N (\(1 <= N <= 20\)) .
 
Salida
Imprimir un número - Nésimo número de catalán
 

 

Ejemplos

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Entrada Salida
1 1 1