Números de Catalan

Os números de Catalan são uma sequência numérica, considerada útil em vários problemas combinatórios, geralmente envolvendo objetos definidos recursivamente.

Esta sequência recebeu o nome do matemático belga Catalan, que viveu no século XIX. (De fato, era conhecido anteriormente por Euler, que viveu um século antes de Catalan).

Os primeiros números da sequência de Catalan, $C_n$:

$1, 1, 2, 5, 14, 42, 132, 429, 1430, \ldots$

Aplicação em alguns problemas de combinatória

Os números de Catalan $C_n$ são soluções para:

Cálculo

Existem duas fórmulas para os números de Catalan: Recursiva e Analítica. Como acreditamos que todos os problemas mencionados acima são equivalentes (têm a mesma solução), para a prova das fórmulas abaixo, escolheremos a tarefa que é mais fácil de fazer.

Fórmula recursiva

$$C_0 = C_1 = 1$$ $$C_n = \sum_{k = 0}^{n-1} C_k C_{n-1-k} , {n} \geq 2$$

A fórmula recursiva pode ser facilmente deduzida do problema da sequência de colchetes correta.

O parêntese de abertura mais à esquerda $l$ orresponde a um certo colchete de fechamento $r$, que divide a sequência em 2 partes que, por sua vez, devem ser uma sequência correta de colchetes. Assim, a fórmula também é dividida em 2 partes. Se denotarmos $k = {r - l - 1}$, então, para um $r$ fixo, haverá exatamente $C_k C_{n-1-k}$ tais sequências de colchetes. Somando isso, sobre todos os $k's$, obtemos a relação recursiva em $C_n$.

Você também pode pensar dessa maneira. Por definição, $C_n$ indica o número de sequências de colchetes corretas. Agora, a sequência pode ser dividida em 2 partes de comprimento $k$ e ${n - k}$, cada uma das quais deve ser uma sequência de colchetes correta. Exemplo:

$( ) ( ( ) )$ pode ser dividida em $( )$ e $( ( ) )$, mas não pode ser dividido em $( ) ($ e $( ) )$. Somando novamente todos os $k's$, obtemos a relação recursiva em $C_n$.

Implementação em C++:

const int MOD = ....
const int MAX = ....
int catalan[MAX];
void init() {
    catalan[0] = catalan[1] = 1;
    for (int i=2; i<=n; i++) {
        catalan[i] = 0;
        for (int j=0; j < i; j++) {
            catalan[i] += (catalan[j] * catalan[i-j-1]) % MOD;
            if (catalan[i] >= MOD) {
                catalan[i] -= MOD;
            }
        }
    }
}

Fórmula analítica

$$C_n = \frac{1}{n + 1} {\binom{2n}{n}}$$

(aqui $\binom{n}{k}$ denota o coeficiente binomial usual, ou seja, as várias maneiras de selecionar $k$ objetos de um conjunto de $n$ objetos).

A fórmula acima pode ser facilmente concluída a partir do problema dos caminhos monotônicos em um grid quadrado. O número total de caminhos monotônicos do grid de tamanho $n \times n$ é dado por $\binom{2n}{n}$.

Agora contamos o número de caminhos monotônicos que cruzam a diagonal principal. Considere esses caminhos cruzando a diagonal principal e encontre a primeira aresta acima da diagonal. Reflita o caminho sobre a diagonal até o fim, seguindo essa extremidade. O resultado é sempre um caminho monotônico no grid $(n - 1) \times (n + 1)$. Por outro lado, qualquer caminho monotônico no grid $(n - 1) \times (n + 1)$ deve cruzar a diagonal. Portanto, enumeramos todos os caminhos monotônicos que cruzam a diagonal principal no grid $n \times n$.

O número de caminhos monotônicos no grid $(n - 1) \times (n + 1)$ será $\binom{2n}{n-1}$. Vamos chamar esses caminhos de "ruins". Como resultado, para obter o número de caminhos monotônicos que não cruzam a diagonal principal subtraímos os caminhos "ruins" acima, obtendo assim a fórmula:

$$C_n = \binom{2n}{n} - \binom{2n}{n-1} = \frac{1}{n + 1} \binom{2n}{n} , {n} \geq 0$$

Referências

Problemas