Una misma sucesión cuenta paréntesis, árboles y triangulaciones

Por qué un analizador no puede probarlo todo

El número de maneras de poner paréntesis en una cadena de multiplicaciones es un número de Catalan, y pasa de mil millones antes de que la cadena llegue a veinte términos. La multiplicación de matrices es asociativa, así que todos los parentizados dan el mismo producto — pero no todos cuestan lo mismo, y la diferencia entre el mejor y el peor orden puede ser de órdenes de magnitud de operaciones. Enumerar las posibilidades para hallar la más barata es por tanto inútil más allá de un puñado de matrices, y la solución estándar es la programación dinámica, que encuentra el óptimo en tiempo cúbico sin resolver dos veces el mismo subproblema. El número de Catalan es lo que ese algoritmo evita.

La imagen de los paréntesis explica toda la familia

Cada uno de estos problemas es una sucesión de pasos que nunca debe volverse negativa. Lee un paréntesis de apertura como más uno y uno de cierre como menos uno: una cadena válida es exactamente un paseo que acaba en cero sin bajar nunca por debajo. Un árbol binario recorrido en orden da el mismo paseo; también una triangulación, y también una cola que nunca debe atender a un cliente que aún no ha llegado. Caído el disfraz, un solo argumento de conteo los cubre a todos, y la demostración estándar es un truco de reflexión que cuenta los paseos malos espejándolos en un conjunto fácil de contar.

Preguntas frecuentes

¿Por qué empieza la sucesión con dos unos?

Porque hay exactamente una manera de no hacer nada y exactamente una de hacer la cosa más pequeña posible. Con cero pares de paréntesis, la cadena vacía es el único arreglo válido, y con un par solo hay una colocación. Las sucesiones que cuentan arreglos empiezan muy a menudo así, y el uno repetido señala que la definición se extendió con sensatez al caso vacío en vez de arrancar arbitrariamente en el primer valor interesante. También importa al calcular: la recurrencia necesita ambos como base antes de poder generar nada más.

¿A qué velocidad crecen de verdad estos números?

Algo menos de cuatro veces por paso, y la razón se arrima despacio a cuatro según crece n: del decimonoveno al vigésimo término vale 3,714, y del vigesimonoveno al trigésimo 3,807. Eso los sitúa entre el crecimiento exponencial de las potencias de dos y el mucho más violento de los factoriales — bastante para derrotar pronto a la fuerza bruta, no bastante para derrotarla al instante. En la práctica la frontera está en torno a veinte: por debajo, una búsqueda exhaustiva suele valer; por encima hace falta algo más fino, y el punto exacto depende de lo que cueste cada caso.