Principii fundamentale de numărare

Combinatorica e ramura matematicii care se ocupă cu numărarea obiectelor. Înainte de formule complexe, trei principii simple rezolvă majoritatea problemelor de numărare.

1. Principiul sumei

Dacă o acțiune poate fi făcută în m moduri sau în n moduri (alternative care nu se suprapun), atunci numărul total de moduri e m + n.

Exemple

Exemplul 1: Am 3 cărți de matematică și 4 cărți de informatică. În câte moduri pot alege o singură carte?

→ 3 + 4 = 7 moduri.

Exemplul 2: Câte numere între 1 și 100 sunt divizibile cu 2 sau cu 3?

Atenție - unele numere sunt divizibile cu amândouă (6, 12, 18…). Principiul sumei nu se aplică direct. Avem nevoie de PInEx (principiul includerii-excluderii).

Condiția cheie: mulțimile să fie disjuncte

Principiul sumei funcționează doar dacă alternativele nu se suprapun. Dacă se suprapun, folosești PInEx.

2. Principiul produsului

Dacă o acțiune e făcută în două etape, prima având m opțiuni și a doua având n opțiuni (independent), numărul total de moduri e m * n.

Exemple

Exemplul 1: Am 3 tricouri și 4 pantaloni. Câte ținute distincte pot forma?

→ 3 * 4 = 12 ținute.

Exemplul 2: Câte cuvinte de 4 litere (distincte) se pot forma din alfabet (26 litere)?

→ 26 * 25 * 24 * 23 = 358800 cuvinte (prima literă 26 opțiuni, a doua 25 - nu o repet, etc).

Exemplul 3: Câte numere de telefon de 7 cifre sunt?

→ 10^7 = 10.000.000 (fiecare cifră din 10, independent).

Generalizare

Dacă ai k etape cu n₁, n₂, ..., nₖ opțiuni fiecare:

Total = n₁ * n₂ * ... * nₖ

3. Principiul lui Dirichlet (Pigeonhole)

Dacă pui n + 1 obiecte în n cutii, cel puțin o cutie va conține cel puțin 2 obiecte.

Sună banal, dar e extrem de puternic pentru demonstrații.

Exemple clasice

Exemplul 1: Într-o clasă de 367 elevi, cel puțin 2 au ziua de naștere în aceeași zi a anului.

De ce? Avem 366 zile posibile (inclusiv 29 februarie) și 367 elevi. Mai mult decât zile → doi trebuie să împartă o zi.

Exemplul 2: Într-un grup de 13 oameni, cel puțin 2 se nasc în aceeași lună.

12 luni, 13 oameni → ⌈13/12⌉ = 2.

Exemplul 3: Într-un grup de 6 oameni, sigur există 3 care se cunosc sau 3 care nu se cunosc.

(Teorema lui Ramsey pentru 6 - demonstrată cu Dirichlet).

Forma generalizată

Dacă pui kn + 1 obiecte în n cutii, cel puțin o cutie conține cel puțin k + 1 obiecte.

Exemplu: 25 bile în 6 cutii → cel puțin o cutie are ⌈25/6⌉ = 5 bile.

Combinarea principiilor

Majoritatea problemelor combină aceste principii.

Exemplu: parole

Câte parole de 4 caractere se pot forma dacă: - Primul caracter e literă mare sau mică (26 + 26 = 52 opțiuni - sumă) - Celelalte 3 sunt litere sau cifre (52 + 10 = 62 fiecare - sumă)

Total: 52 * 62 * 62 * 62 = 52 * 62^3 = 12.388.736 parole (produs).

Exemplu de cod: calculăm numărul de moduri

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

int main() {
    int n, m;
    fin >> n >> m;

    // Exemplu: n tipuri de haine de top, m tipuri de pantaloni
    fout << "Tinute posibile: " << (long long)n * m << "\n";

    return 0;
}

date.in:

3 4

date.out:

Tinute posibile: 12

Cum recunoști ce principiu să folosești?

Greșeli frecvente

1. Suma când trebuie produs

“Aleg o cămașă dintre 3 și pantaloni dintre 4” → ÎNMULȚEȘTI, nu aduni. Total 12 ținute.

“Aleg o cămașă sau o bluză” → ADUNI.

Cuvântul cheie: și = produs, sau (exclusiv) = sumă.

2. Uitarea repetițiilor

“Câte numere de 3 cifre sunt?” Dacă cifra repetă: 9 * 10 * 10 = 900 (prima nu poate fi 0). Dacă cifra NU repetă: 9 * 9 * 8 = 648.

Citește atent - se permite repetiția?

3. Dirichlet - “cel puțin”

n+1 în n garantează cel puțin 2, nu exact 2. Poate fi și 10, 100, etc.

Ce să reții

• Principiul sumei: alternative disjuncte → adună numărul de opțiuni.
• Principiul produsului: etape independente → înmulțește numărul de opțiuni.
• Principiul lui Dirichlet: n+1 obiecte în n cutii → cel puțin 2 într-o cutie.
• Produs = “și”, Sumă = “sau” (exclusiv).
• Pentru alternative care se suprapun, folosește PInEx.
• Dirichlet e minunat pentru demonstrații de existență.