Uma mesma sucessão conta parênteses, árvores e triangulações

Porque um analisador não pode tentar tudo

O número de maneiras de pôr parênteses numa cadeia de multiplicações é um número de Catalan, e passa os mil milhões antes de a cadeia chegar a vinte termos. A multiplicação de matrizes é associativa, pelo que todas as parentizações dão o mesmo produto — mas não custam todas o mesmo, e a diferença entre a melhor e a pior ordem pode ser de ordens de grandeza de operações. Enumerar as possibilidades para achar a mais barata é portanto inútil para lá de um punhado de matrizes, e a solução padrão é a programação dinâmica, que encontra o ótimo em tempo cúbico sem resolver duas vezes o mesmo subproblema. O número de Catalan é o que esse algoritmo evita.

A imagem dos parênteses explica toda a família

Cada um destes problemas é uma sequência de passos que nunca deve tornar-se negativa. Lê um parêntese de abertura como mais um e um de fecho como menos um: uma cadeia válida é exatamente um passeio que acaba em zero sem nunca descer abaixo. Uma árvore binária percorrida por ordem dá o mesmo passeio; uma triangulação também, e também uma fila que nunca deve atender um cliente ainda não chegado. Caído o disfarce, um só argumento de contagem cobre-os todos, e a demonstração padrão é um truque de reflexão que conta os passeios maus espelhando-os num conjunto fácil de contar.

Perguntas frequentes

Porque começa a sucessão com dois uns?

Porque há exatamente uma maneira de não fazer nada e exatamente uma de fazer a coisa mais pequena possível. Com zero pares de parênteses, a cadeia vazia é o único arranjo válido, e com um par só há uma colocação. As sucessões que contam arranjos começam muitas vezes assim, e o um repetido assinala que a definição foi estendida com bom senso ao caso vazio em vez de arrancar arbitrariamente no primeiro valor interessante. Também conta no cálculo: a recorrência precisa de ambos como base antes de poder gerar seja o que for.

A que velocidade crescem realmente estes números?

Um pouco menos de quatro vezes por passo, e a razão aproxima-se devagar de quatro à medida que n cresce: do décimo nono para o vigésimo termo vale 3,714, e do vigésimo nono para o trigésimo 3,807. Isso coloca-os entre o crescimento exponencial das potências de dois e o bem mais violento dos fatoriais — suficiente para derrotar cedo a força bruta, não suficiente para a derrotar de imediato. Na prática a fronteira anda pelos vinte: abaixo, uma busca exaustiva costuma servir; acima é preciso algo mais fino, e o ponto exato depende do custo de cada caso.