Numărarea aranjamentelor — alegi și ordonezi

De ce A(n,k) = n·(n-1)·...·(k factori)

Vrei să alegi și să ordonezi k elemente distincte din n disponibile. Gândește pe poziții, una câte una:

• pentru prima poziție ai n variante (orice element);
• după ce ai fixat-o, pentru a doua poziție ai rămas cu n - 1 variante;
• pentru a treia poziție: n - 2 variante;
• ... și tot așa, până la poziția k, unde mai ai n - k + 1 variante.

Înmulțești toate aceste numere (regula produsului, fiindcă alegerile sunt independente una de alta):

A(n,k) = n · (n-1) · (n-2) · ... · (n-k+1)

Observă că ai exact k factori, care scad din 1 în 1 pornind de la n. Forma compactă cu factoriale este A(n,k) = n! / (n-k)!, dar pentru calcul e mai ușor și mai sigur să înmulțești direct cei k factori — nu aduni la nesfârșit factori care oricum se simplifică.

Exemplu pas cu pas: A(4,2) = 12

Ai elementele {A, B, C, D} și vrei să alegi și să ordonezi 2 dintre ele.

• prima poziție: 4 variante → A, B, C sau D;
• a doua poziție: 3 variante rămase (oricare în afară de cea deja folosită).

Deci A(4,2) = 4 · 3 = 12. Le poți enumera ca să te convingi:

AB AC AD BA BC BD CA CB CD DA DB DC

Sunt 12 perechi ordonate. Atenție: AB și BA apar amândouă, fiindcă ordinea contează. Dacă ordinea NU ar conta (combinări), AB și BA ar fi una singură, iar răspunsul ar fi pe jumătate: C(4,2) = 6.

Implementare C++

Calculăm produsul celor k factori, aplicând modulo la fiecare pas ca să nu depășim domeniul lui long long când n e mare.

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

// A(n, k) = n * (n-1) * ... * (n-k+1), modulo MOD
long long aranjamente(long long n, long long k) {
    if (k < 0 || k > n) return 0;   // nu poti ordona mai multe decat ai
    long long rezultat = 1;
    for (long long i = 0; i < k; i++) {
        // factorii sunt n, n-1, ..., n-k+1
        rezultat = (rezultat * ((n - i) % MOD)) % MOD;
    }
    return rezultat;
}

int main() {
    cout << aranjamente(4, 2) << "\n";   // 12
    cout << aranjamente(5, 5) << "\n";   // 120 (permutari: A(n,n) = n!)
    cout << aranjamente(3, 5) << "\n";   // 0  (k > n)
    return 0;
}

Folosim long long și înmulțim modulo la fiecare pas: chiar dacă n are sute de mii, fiecare produs intermediar rămâne sub MOD * MOD, deci încape lejer în long long (care ține valori până la aproximativ 9.2 · 10^18).

Complexitate

Calculul e direct și rapid: nu ai nevoie de tablouri sau de precalcularea factorialelor pentru o singură valoare A(n,k).

Recapitulare

• Aranjamentele A(n,k) numără în câte feluri alegi ȘI ordonezi k din n elemente; ordinea contează — aceasta e diferența-cheie față de combinări.
• Formula este produsul a exact k factori: A(n,k) = n · (n-1) · ... · (n-k+1), calculat în O(k) cu long long și % MOD la fiecare pas.
• Cazul A(n,n) = n! sunt permutările; dacă ordinea nu contează, vorbim despre combinări (alegi fără să ordonezi).