Programare Competitivă

Triunghiul lui Pascal

Triunghiul lui Pascal e o structură triunghiulară formată din coeficienți binomiali C(n, k). Aranjată pe linii, ea are proprietăți elegante și permite calcularea rapidă a combinărilor.

Construcția

Fiecare număr e suma celor două numere de deasupra. Marginile sunt toate 1.

n=0:                1
n=1:              1   1
n=2:            1   2   1
n=3:          1   3   3   1
n=4:        1   4   6   4   1
n=5:      1   5  10  10   5   1
n=6:    1   6  15  20  15   6   1
n=7:  1   7  21  35  35  21   7   1

Numărul de pe linia n, poziția k (de la 0) e C(n, k).

Regula fundamentală

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

Fiecare element = suma celor două de deasupra. Marginile: C(n, 0) = C(n, n) = 1.

Demonstrație combinatorică

Fie un element fix din mulțime. Când alegem k din n:

  • Îl includem: alegem restul k-1 din celelalte n-1 → C(n-1, k-1)
  • Nu-l includem: alegem k din celelalte n-1 → C(n-1, k)

Total: suma.

Proprietăți geniale

1. Simetria liniilor

Linia n e palindrom: C(n, k) = C(n, n-k)

C(5, 2) = 10 = C(5, 3).

2. Suma unei linii = 2^n

C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n

Linia 4: 1 + 4 + 6 + 4 + 1 = 16 = 2^4.

De ce? Număr total de submulțimi ale unei mulțimi de n elemente.

3. Suma alternată = 0

C(n, 0) - C(n, 1) + C(n, 2) - ... ± C(n, n) = 0  (pentru n >= 1)

Linia 4: 1 - 4 + 6 - 4 + 1 = 0.

4. Suma pe diagonală (“hockey stick”)

C(n, 0) + C(n+1, 1) + C(n+2, 2) + ... + C(n+k, k) = C(n+k+1, k)

5. Numerele triunghiulare pe diagonala a 2-a

Coloana k=2 dă numerele triunghiulare: 1, 3, 6, 10, 15, 21, …

6. Puterile lui 2 pe diagonală

Sumele liniilor: 2^0, 2^1, 2^2, 2^3, ...

Precalcul iterativ

O(n²) memorie

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

const int NMAX = 1001;
long long C[NMAX][NMAX];

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

int main() {
    int n, k;
    fin >> n >> k;
    precalculare(n);
    fout << "C(" << n << ", " << k << ") = " << C[n][k];
    return 0;
}

date.in:

10 3

date.out:

C(10, 3) = 120

Precalcul cu mod

Pentru n mare și mod prim:

const long long MOD = 1000000007;
long long C[NMAX][NMAX];

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

Nu mai avem overflow datorită mod-ului.

Cu memorie O(n)

Putem calcula linia n folosind doar linia precedentă:

long long C[NMAX];

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

Atenție: parcurgem j de la dreapta la stânga pentru a nu suprascrie valori încă nefolosite.

Generarea triunghiului pentru afișare

#include <fstream>
#include <iomanip>
using namespace std;
ofstream fout("pascal.out");

int main() {
    int n = 6;
    long long C[10][10] = {0};
    for (int i = 0; i <= n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i-1][j-1] + C[i-1][j];
    }

    for (int i = 0; i <= n; i++) {
        for (int s = 0; s < (n - i) * 2; s++) fout << " ";
        for (int j = 0; j <= i; j++)
            fout << setw(4) << C[i][j];
        fout << "\n";
    }
    return 0;
}

Ieșire:

            1
          1   1
        1   2   1
      1   3   3   1
    1   4   6   4   1
  1   5  10  10   5   1
1   6  15  20  15   6   1

Aplicații

1. Coeficienții lui (a+b)^n (Binomul lui Newton)

(a+b)^n = Σ C(n, k) * a^(n-k) * b^k

Exemplu:

(a+b)^3 = 1*a^3 + 3*a²b + 3*ab² + 1*b^3

Coeficienții 1, 3, 3, 1 vin direct din linia 3.

2. Calcul rapid al combinărilor

După precalcul, C(n, k) e în O(1).

3. Drumuri pe grilă

De la (0,0) la (m,n) fără a te întoarce: C(m+n, m).

4. Tipuri de secvențe

Numărul de șiruri binare cu exact k biți de 1 dintr-un șir de n biți: C(n, k).

Teorema lui Lucas (pentru numere mari)

Pentru a calcula C(n, k) mod p (p prim) când n și k sunt uriașe, folosim teorema lui Lucas:

C(n, k) mod p = Π C(nᵢ, kᵢ) mod p

unde nᵢ și kᵢ sunt cifrele lui n și k în baza p.

long long lucas(long long n, long long k, long long p) {
    if (k == 0) return 1;
    return (lucas(n / p, k / p, p) * combMic(n % p, k % p, p)) % p;
}

Util pentru n până la 10^18.

Greșeli frecvente

1. Neinițializarea marginii

// GRESIT - C[i][i] nu e setat
for (int j = 1; j < i; j++)
    C[i][j] = C[i-1][j-1] + C[i-1][j];

// CORECT
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
    C[i][j] = C[i-1][j-1] + C[i-1][j];

2. Ordine greșită la varianta O(n)

for (int j = 1; j <= i; j++) C[j] = C[j] + C[j-1]; // GRESIT - suprascrie
for (int j = i; j >= 1; j--) C[j] = C[j] + C[j-1]; // CORECT

3. Overflow fără mod

C(60, 30) > 10^17 - încape în long long. Dar C(70, 35) depășește. Folosește mod pentru n mare.

4. Indici greșiți

C[n][k] cu k > n e 0 (prin convenție). Asigură-te că nu accesezi C[n][k] cu k > n din greșeală.

Ce să reții

  • Triunghiul lui Pascal e aranjarea C(n, k) pe linii.
  • Regula: C(n, k) = C(n-1, k-1) + C(n-1, k).
  • Proprietăți: simetrie, sumă linie = 2^n, sume alternate = 0, hockey stick.
  • Precalcul O(n²) timp și memorie cu regula lui Pascal.
  • Varianta cu memorie O(n) - parcurgere de la dreapta la stânga.
  • Coeficienții lui (a+b)^n sunt exact linia n.
  • Pentru n uriaș: teorema lui Lucas.
Cuprins Inapoi Inainte