Numărarea permutărilor — n factorial

De ce n!

O permutare a n elemente distincte este o aranjare a lor într-o ordine. Întrebarea „câte permutări există?” se rezolvă gândind poziție cu poziție.

Imaginează-ți n locuri goale pe care le umpli de la stânga la dreapta:

• pentru prima poziție poți alege oricare dintre cele n elemente → n variante;
• pentru a doua poziție a mai rămas un element mai puțin → n-1 variante;
• pentru a treia → n-2 variante;
• ... și tot așa, până la ultima poziție, unde a rămas un singur element → 1 variantă.

Fiindcă alegerile sunt independente, le înmulțești:

n · (n-1) · (n-2) · ... · 2 · 1 = n!

Asta este definiția lui n factorial. El numără exact câte ordini distincte poți forma cu n obiecte diferite.

Exemplu pas cu pas: n = 3

Fie cele 3 elemente a, b, c. Le enumerăm complet, fixând pe rând primul element:

• începe cu a: abc, acb
• începe cu b: bac, bca
• începe cu c: cab, cba

Sunt exact 6 permutări, iar 3! = 3 · 2 · 1 = 6. Se vede și logica pozițiilor: 3 alegeri pentru primul element, apoi câte 2 pentru al doilea, apoi 1 pentru ultimul → 3 · 2 · 1.

Cazul special: pentru n = 0 avem 0! = 1. Există o singură modalitate de a aranja zero elemente — șirul gol. Convenția nu este arbitrară: ea face ca formula n! = n · (n-1)! să rămână corectă și pentru n = 1 (1! = 1 · 0! = 1).

Implementare C++

Factorial iterativ cu long long — corect pentru valori mici (n până la 20):

#include <iostream>
using namespace std;

long long factorial(int n) {
    long long rezultat = 1;
    for (int i = 2; i <= n; i++) {
        rezultat = rezultat * i;    // inmultim pe rand: 2, 3, ..., n
    }
    return rezultat;                // pentru n = 0 sau n = 1 ramane 1
}

int main() {
    cout << factorial(3) << "\n";   // 6
    cout << factorial(0) << "\n";   // 1 (conventia 0! = 1)
    cout << factorial(5) << "\n";   // 120
    return 0;
}

Pentru n mare enunțul cere răspunsul modulo 1000000007, fiindcă valoarea reală nu mai încape în niciun tip întreg:

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long factorialMod(int n) {
    long long rezultat = 1;
    for (int i = 2; i <= n; i++) {
        rezultat = (rezultat * i) % MOD;    // reducem dupa fiecare inmultire
    }
    return rezultat;
}

int main() {
    cout << factorialMod(3) << "\n";        // 6
    cout << factorialMod(20) << "\n";       // 2432902008176640000 % MOD
    cout << factorialMod(100000) << "\n";   // valoare mica, fara overflow
    return 0;
}

Reducem cu % MOD după fiecare înmulțire, nu doar la final: așa fiecare factor intermediar rămâne mai mic decât MOD, iar produsul a două astfel de valori încape lejer în long long.

Complexitate

O singură buclă care înmulțește de la 2 la n: liniar în n, fără memorie suplimentară dincolo de variabila rezultat.

Permutarea este, de fapt, un aranjament de n din n: iei toate cele n elemente și le pui în ordine. De aceea P(n) = A(n, n) = n!.

Recapitulare

• Numărul de permutări ale n elemente distincte este n! = n · (n-1) · ... · 1, prin argumentul alegerilor poziție cu poziție.
• Prin convenție 0! = 1, ceea ce păstrează valabilă relația n! = n · (n-1)!.
• La n mare folosești long long plus % MOD (cu MOD = 1000000007) după fiecare înmulțire, fiindcă 21! deja depășește long long.