Programare Competitivă

Numere Catalan

Numerele Catalan C(n) (atenție - notație diferită de combinări) formează un șir faimos în combinatorică, apărând în zeci de probleme aparent fără legătură.

E unul dintre cele mai frumoase rezultate ale combinatoricii.

Șirul

C(0) = 1
C(1) = 1
C(2) = 2
C(3) = 5
C(4) = 14
C(5) = 42
C(6) = 132
C(7) = 429
C(8) = 1430
C(9) = 4862
C(10) = 16796

Formula

C(n) = C(2n, n) / (n+1) = (2n)! / ((n+1)! * n!)

Sau, echivalent:

C(n) = C(2n, n) - C(2n, n+1)

Relația de recurență

C(n+1) = Σ C(i) * C(n - i) pentru i = 0..n

C(n+1) = C(n) * 2(2n+1) / (n+2)

Prima e definiția “împărțirii în două subprobleme”. A doua permite calcul iterativ rapid.

Problema 1: paranteze echilibrate

Câte secvențe de n paranteze deschise și n paranteze închise sunt echilibrate?

Pentru n = 3 (3 perechi):

((()))
(()())
(())()
()(())
()()()

5 secvențe = C(3) ✓.

Problema 2: drumuri care nu depășesc diagonala

Câte drumuri pe grilă de la (0,0) la (n,n), mergând doar dreapta (D) sau sus (S), care nu trec deasupra diagonalei (adică în orice moment, numărul de D ≥ S)?

Pentru n = 3:

Drum 1: DDDSSS
Drum 2: DDSDSS
Drum 3: DDSSDS
Drum 4: DSDDSS
Drum 5: DSDSDS

5 drumuri = C(3).

Bijectia cu paranteze

D ↔︎ (, S ↔︎ ). “Nu trece deasupra diagonalei” ↔︎ “niciodată mai multe ) decât (”. Aceeași problemă reformulată.

Problema 3: arbori binari

Câți arbori binari distincți cu n noduri există?

Pentru n = 3:

Arborele e definit recursiv:
  - rădăcina
  - un subarbore stâng (cu k noduri)
  - un subarbore drept (cu n-1-k noduri)

Enumerare forme pentru 3 noduri:

5 arbori distincți (exercițiu: desenează-i). = C(3) ✓.

De ce C(n)?

Recurența: dacă ai n noduri, rădăcina e unul. Subarborele stâng are k noduri și subarborele drept n-1-k.

T(n) = Σ T(k) * T(n-1-k)   pentru k = 0..n-1

Aceeași recurență ca la Catalan → T(n) = C(n).

Problema 4: triangulații de poligon

Câte triangulații distincte are un poligon convex cu n+2 laturi?

Pentru un pătrat (4 laturi, n=2): 2 triangulații (diagonala stânga-sus/dreapta-jos sau stânga-jos/dreapta-sus) = C(2).

Pentru pentagon (5 laturi, n=3): 5 triangulații = C(3).

Problema 5: șiruri de 0 și 1

Câte șiruri de 2n caractere cu n unuri și n zerouri, astfel încât orice prefix are cel puțin tot atâtea 1 cât 0?

= C(n).

Problema 6: munți

Câte secvențe de n “urcări” / și n “coborâri” \ formează un munte (nu coboară niciodată sub nivelul 0)?

Pentru n = 3: 5 munți = C(3).

/\/\/\
/\/  \
  /\
/    \
    /\
/\/  \

(Încearcă să desenezi - e același model ca parantezele.)

Cod

Cu formula directă

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

long long combinari(int n, int k) {
    if (k < 0 || k > n) return 0;
    if (k > n - k) k = n - k;
    long long rez = 1;
    for (int i = 0; i < k; i++) {
        rez *= (n - i);
        rez /= (i + 1);
    }
    return rez;
}

long long catalan(int n) {
    return combinari(2 * n, n) / (n + 1);
}

int main() {
    int n;
    fin >> n;
    fout << "C(" << n << ") = " << catalan(n);
    return 0;
}

Cu recurența (precalcul)

long long C[35];

void precalcCatalan(int n) {
    C[0] = 1;
    for (int i = 0; i < n; i++) {
        C[i + 1] = C[i] * 2 * (2 * i + 1) / (i + 2);
    }
}

O(n) timp.

Cu DP (suma produselor)

long long C[35];

void precalcCatalanDP(int n) {
    C[0] = 1;
    for (int i = 1; i <= n; i++) {
        C[i] = 0;
        for (int j = 0; j < i; j++)
            C[i] += C[j] * C[i - 1 - j];
    }
}

O(n²) timp, dar ilustrează frumos recurența.

Pas cu pas: enumerare paranteze pentru n=2

C(2) = 2 secvențe:

(())
()()

Verificare prin recurență: C(2) = C(0)*C(1) + C(1)*C(0) = 1*1 + 1*1 = 2 ✓.

Bijectii - cum apar aceleași numere peste tot

Toate problemele de mai sus au același număr de soluții pentru că între ele există bijectii (corespondențe unu-la-unu):

Paranteze  ↔  Drumuri  ↔  Arbori  ↔  Munți  ↔  Triangulații

De exemplu: - ( → urcare, ) → coborâre → muntele - ( → nod stâng, ) → nod drept → arborele binar

Combinatorica “redescoperă” numerele Catalan în multe contexte diferite.

Formula fără împărțire (Catalan = C(2n, n) - C(2n, n+1))

Demonstrație elegantă cu reflecția:

Total drumuri de la (0,0) la (n,n): C(2n, n).

Drumuri care încalcă regula (trec deasupra diagonalei): pentru fiecare drum ilegal, reflectăm partea “rea” față de linia y = x+1. Obținem drumuri de la (-1, 1) la (n, n). Număr: C(2n, n+1).

Răspuns: C(2n, n) - C(2n, n+1) = C(n).

Creșterea numerelor Catalan

Numerele Catalan cresc aproape exponențial:

C(n) ~ 4^n / (n^(3/2) * √π)
  • C(10) ≈ 16.000
  • C(20) ≈ 6.5 * 10^9
  • C(30) ≈ 3.8 * 10^15
  • C(34) depășește long long.

Pentru n mare, folosește aritmetică modulară sau BigInt.

Probleme de concurs cu Catalan

1. Numărul de expresii fără ambiguitate

Dându-se n operanzi și operatori binari, câte moduri de parantezare?

→ C(n-1).

Exemplu: a * b * c * d poate fi parantezat în C(3) = 5 moduri:

((ab)c)d
(a(bc))d
(ab)(cd)
a((bc)d)
a(b(cd))

2. Subdivizare poligon

Câte moduri de a împărți un poligon în triunghiuri neincrucișate folosind diagonale?

→ C(n-2) pentru poligon cu n laturi.

3. Arbori binari complet de înălțime fixă

Numărul de arbori binari cu anumite proprietăți → adesea Catalan.

4. Permutări “stack-sortable”

Câte permutări ale {1, 2, ..., n} pot fi sortate folosind doar o stivă?

→ C(n).

Tabel identități utile

Formula Relație
C(n) = C(2n, n) / (n+1) definiția cea mai folosită
C(n) = C(2n, n) - C(2n, n+1) reflecție
C(n+1) = Σ C(i) C(n-i) recurența fundamentală
C(n+1) = C(n) * 2(2n+1)/(n+2) recurența O(1)

Greșeli frecvente

1. Confuzia notației

C(n) pentru Catalan vs C(n, k) pentru combinări. Verifică contextul.

2. Overflow

C(34) depășește long long. Pentru n ≥ 34, folosește mod sau BigInt.

3. Recurența greșită

// GRESIT - lipseste factorul 2*(2i+1)
C[i+1] = C[i] / (i + 2);

// CORECT
C[i+1] = C[i] * 2 * (2 * i + 1) / (i + 2);

4. Împărțire înainte de înmulțire

// RISC de imprecizie sau rezultat gresit
C[i+1] = C[i] / (i + 2) * 2 * (2 * i + 1);

// BINE - inmulteste mai intai
C[i+1] = C[i] * 2 * (2 * i + 1) / (i + 2);

Ce să reții

  • Numerele Catalan apar în zeci de probleme aparent diferite.
  • Formula: C(n) = C(2n, n) / (n+1).
  • Recurența: C(n+1) = Σ C(i) * C(n-i).
  • Aplicații: paranteze echilibrate, drumuri pe grilă, arbori binari, triangulații, munți, compunere, stack-sortable.
  • Între toate problemele există bijectii (corespondențe naturale).
  • Crestere ~ 4^n / n^(3/2) - depășește long long la n ≈ 34.
  • Formulă alternativă prin reflecție: C(n) = C(2n, n) - C(2n, n+1).

Probleme

pbinfoNumarparanteze→

pbinfoCatalan→

pbinfoPlanar→

Cuprins Inapoi Inainte