Parantezări — numerele lui Catalan

De ce contează?

Pui pe masă trei perechi de paranteze și vrei să le aranjezi într-un șir corect: fiecare paranteză deschisă să aibă mai târziu o paranteză care o închide, fără să închizi vreodată ceva ce n-ai deschis. În câte feluri diferite poți face asta? Surprinzător, răspunsul (5, pentru trei perechi) apare în zeci de alte probleme care par fără legătură. Numărul acela are un nume: numărul lui Catalan.

Ce numără numerele lui Catalan

Al n-lea număr Catalan, notat C_n, numără câte parantezări corecte poți forma cu n perechi de paranteze. Un șir e corect dacă, citindu-l de la stânga la dreapta, niciodată numărul de paranteze închise nu îl depășește pe cel de paranteze deschise, iar la final sunt egale.

Aceeași formulă numără, surprinzător, multe alte lucruri:

șiruri de paranteze echilibrate cu n perechi (interpretarea de bază);
arbori binari distincți cu n noduri;
drumuri pe grilă de la colț la colț care nu trec peste diagonală;
moduri de a triangula un poligon convex cu n + 2 laturi.

Toate dau același șir de numere: 1, 1, 2, 5, 14, 42, 132, ...

Exemplu pas cu pas: C_3 = 5

Pentru n = 3 perechi, enumerăm toate șirurile echilibrate. Pornim mereu cu o paranteză deschisă și nu lăsăm niciodată închiderile să o ia înainte:

((())) — toate deschise întâi, apoi toate închise;
(()()) — un bloc interior format din două perechi alăturate;
(())() — o pereche care conține o pereche, apoi una separată;
()(()) — o pereche separată, apoi o pereche care conține o pereche;
()()() — trei perechi una după alta.

Sunt exact 5 șiruri, deci C_3 = 5. Observă cum recurența le explică: fixează perechea care închide tot șirul. În interiorul ei stau i perechi, iar după ea 3 - 1 - i perechi. Sumăm peste i = 0, 1, 2 și obținem C_0*C_2 + C_1*C_1 + C_2*C_0 = 1*2 + 1*1 + 2*1 = 5.

Implementare C++

Calculăm C_n cu recurența C_0 = 1, C_(n+1) = suma C_i * C_(n-1-i). Folosim programare dinamică: fiecare C_k se obține din valorile deja calculate.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

int main() {
    int n = 10;
    long long catalan[105];

    catalan[0] = 1;             // cazul de baza: o singura parantezare goala

    // catalan[k+1] = suma catalan[i] * catalan[k-i], i de la 0 la k
    for (int k = 0; k < n; k++) {
        catalan[k + 1] = 0;
        for (int i = 0; i <= k; i++) {
            // adunam produsul perechilor interioare * exterioare
            catalan[k + 1] += (catalan[i] * catalan[k - i]) % MOD;
            catalan[k + 1] %= MOD;      // tinem rezultatul sub MOD
        }
    }

    // afisam primele cateva numere Catalan
    for (int i = 0; i <= 5; i++) {
        cout << catalan[i] << " ";      // 1 1 2 5 14 42
    }
    cout << "\n";

    cout << catalan[3] << "\n";         // C_3 = 5
    return 0;
}

Pentru valori mici poți renunța la MOD și păstra doar long long, dar atenție: numerele cresc foarte repede, așa că modulo devine necesar la n mare.

Complexitate

Pas	Cost
Calcul `catalan[k+1]` (o sumă)	O(k)
Toate cele `n` valori	O(n²)
Memorie (vectorul `catalan`)	O(n)

Recurența cu DP este O(n²). Formula închisă C_n = combinari(2n, n) / (n + 1) dă o singură valoare în O(n), dar sub modulo cere invers modular pentru împărțire.

Observația-cheie

Multe probleme de concurs care par diferite (numără arbori binari, drumuri pe grilă, triangulări de poligon, șiruri echilibrate) ascund aceeași formulă: numerele lui Catalan. Dacă recunoști tiparul, soluția devine o recurență scurtă în loc de o căutare obositoare a unui pattern nou.

Greșeli frecvente

Off-by-one la indici: în recurența C_(n+1) = suma C_i * C_(n-1-i), partenerul lui C_i este C_(k-i) când calculezi catalan[k+1], nu C_(k-1-i). Verifică manual cu C_3 = 5 înainte să te încrezi în buclă.
C_0 = 1 uitat: dacă pui catalan[0] = 0, întreaga recurență colapsează la zero. Cazul de bază este 1 (parantezarea goală), nu 0.
Overflow: numerele Catalan cresc aproape ca 4^n. Pe int se strică deja la C_19. Folosește long long și aplică MOD la fiecare adunare și produs.
Formula închisă fără invers modular: combinari(2n, n) / (n + 1) sub MOD NU se face cu împărțire obișnuită — ai nevoie de inversul modular al lui n + 1.

C	1	1	2	5	14	42
	0	1	2	3	4	5

Primele numere Catalan: C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, C_4 = 14, C_5 = 42.

Vizualizare

Indiciu

Observă cum fiecare număr e suma celor doi de deasupra — numerele Catalan se sprijină pe aceleași coeficienți; folosește ← / → pentru a avansa pas cu pas.

Recapitulare

C_n numără parantezările corecte cu n perechi, dar și arbori binari, drumuri pe grilă și triangulări — toate cu aceeași formulă.
Recurența C_0 = 1, C_(n+1) = suma C_i * C_(n-1-i) se calculează cu DP în O(n²); verific-o pe C_3 = 5.
La n mare folosește long long și MOD = 1000000007; formula închisă cere invers modular pentru împărțirea la n + 1.