¿De cuántas formas se puede poner entre paréntesis una expresión?

Question

Contexto

Estoy escribiendo un programa de ordenador para hacer una búsqueda de fuerza bruta de una solución a un rompecabezas que quería ordenar cuatro números con los cuatro operadores aritméticos estándar y llegar a una respuesta dada. Aunque tengo una solución para el rompecabezas original, todavía quiero escribir un programa de resolución de casos generales para n números. He desglosado el problema en:

1. Arreglos de los números (¡n!)
2. Disposiciones de los operadores (4 n-1 )
3. Arreglos de asociatividad. O paréntesis, si lo prefiere.

Es en este último en el que no puedo encontrar la respuesta de caso general a "¿cuántos habrá?", pero si voy a escribir un programa para resolverlo, entonces necesito mis casos de prueba para demostrar que mi implementación es correcta.

Progreso

Tengo una notación para esto, que funciona descomponiendo la fórmula considerada en notación polaca inversa, y expresándola como 1 para una operación "Pulsar número", o 0 para la operación "Pop dos números, aplicar operador, empujar resultado". Está claro que los cuatro operadores son operadores binarios, por lo que las dos primeras operaciones deben ser necesariamente operaciones "Push". Del mismo modo, la última debe ser un cálculo.

Además, al contar N ₁ - el número de empujones - y N ₀ - el número de cálculos, desde el inicio hasta cualquier punto, N ₁ debe ser siempre superior a N ₀

Por inspección, he determinado los siguientes resultados:

 n | C(n) | 
---+------+-
 2 |   1  | 110
 3 |   2  | 11010 11100
 4 |   5  | 1101010 1101100 1110010 1110100 1111000
 5 |  14  | 

Creo que C ₆ tiene 42 años, pero aún no estoy seguro de ello.

Pregunta

¿Cuál es el valor en el caso general de C _n ?

Answer 1

En Gerry señalado en los comentarios, estos son los Números catalanes . El artículo de Wikipedia tiene una sección http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics que incluye, como uno de sus ejemplos,

C _n es el número de maneras diferentes en que n + 1 factores pueden ser completamente entre paréntesis (o el número de maneras de asociar n aplicaciones de un operador binario).

que es exactamente el caso de la pregunta. De hecho, el primer ejemplo que se da en ese artículo habla de

C _n es el número de palabras Dyck de longitud 2n. Una palabra Dyck es una cadena formada por n X e n Y de tal forma que ningún segmento inicial de la cadena tiene más Y que X.

que corresponde casi exactamente a la observación del PO en la tabla de resultados bajo "Progreso".

Por lo tanto, la respuesta es

$$C_n = \frac{1}{(n+1)}.{2n \choose n} = \frac{(2n)!}{n!(n+1)!}$$

A continuación, sólo hay que adaptarlo a las necesidades de la pregunta original para obtener los resultados siguientes $C_4 = 14$ Considerando que la pregunta expresaba sus exigencias de tal manera que $C_5 = 14$ . La alternativa es adaptar la pregunta de forma que tenga en cuenta los operadores en lugar de los términos.