Aranjamente

Un aranjament de n luate câte k e o alegere ordonată a k elemente dintr-o mulțime de n elemente distincte.

Ordinea contează și elementele nu se repetă.

Formula

A(n, k) = n * (n-1) * (n-2) * … * (n-k+1) = n! / (n-k)!

Pe prima poziție: n opțiuni. Pe a doua: n-1 (una folosită). … Pe poziția k: n-k+1.

Produsul are exact k factori.

Valori mici

Exemple

Exemplul 1: medaliate la concurs

5 concurenți, 3 medalii (aur, argint, bronz). Câte moduri pentru podium?

→ A(5, 3) = 5 * 4 * 3 = 60.

Exemplul 2: parole

Câte parole de 4 litere distincte pot forma din alfabet (26 litere)?

→ A(26, 4) = 26 * 25 * 24 * 23 = 358.800.

Exemplul 3: 8 cai, primii 3

Într-o cursă cu 8 cai, câte moduri de aranjare pe primele 3 locuri?

→ A(8, 3) = 8 * 7 * 6 = 336.

Relația cu permutările

Observă că:

A(n, n) = n! = P(n)

O permutare e un aranjament în care folosim toate elementele (k = n).

Relația cu combinările

A(n, k) = C(n, k) * k!

Explicație: ca să aranjezi ordonat k elemente, alegi întâi k elemente din n (combinări C(n,k)), apoi le aranjezi în ordine (permutări k!).

Diferența aranjament vs combinare

Întrebare cheie: “(abc) și (bac) sunt considerate la fel?” Dacă DA → combinări. Dacă NU → aranjamente.

Cod

long long aranjamente(int n, int k) {
    long long rez = 1;
    for (int i = 0; i < k; i++)
        rez *= (n - i);
    return rez;
}

Pentru A(5, 3):

i=0: rez = 1 * 5 = 5
i=1: rez = 5 * 4 = 20
i=2: rez = 20 * 3 = 60

Cu long long și mod

Pentru n mare:

const long long MOD = 1000000007;

long long aranjamente(int n, int k) {
    long long rez = 1;
    for (int i = 0; i < k; i++)
        rez = rez * (n - i) % MOD;
    return rez;
}

Cod complet

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

long long aranjamente(int n, int k) {
    long long rez = 1;
    for (int i = 0; i < k; i++)
        rez *= (n - i);
    return rez;
}

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

    if (k > n) fout << "Imposibil (k > n)";
    else fout << "A(" << n << ", " << k << ") = " << aranjamente(n, k);

    return 0;
}

date.in:

8 3

date.out:

A(8, 3) = 336

Probleme clasice

1. Numere de telefon distincte

Câte numere de 7 cifre cu cifre distincte se pot forma?

Prima cifră: 9 opțiuni (1-9, nu 0). Restul: A(9, 6) = 9!/3! = 60.480.

Total: 9 * 60.480 = 544.320.

2. Funcții injective

Câte funcții injective (unu-la-unu) f: A → B cu |A| = k, |B| = n?

Fiecare element al lui A trebuie mapat unic la unul din B. Primul element are n opțiuni, al doilea n-1, etc.

→ A(n, k).

3. Cuvinte cu litere distincte

Din cuvântul “ALGORITM” (8 litere distincte), câte cuvinte de 5 litere pot forma?

→ A(8, 5) = 8*7*6*5*4 = 6720.

Aranjamente cu repetiție

Dacă elementele se pot repeta, formula devine:

A_rep(n, k) = n^k

Pe fiecare poziție: n opțiuni (nu elimin nimic).

Exemplu: parole cu repetiție

Câte parole de 4 caractere din 26 litere + repetiție?

→ 26^4 = 456.976.

Fără repetiție erau 358.800 - repetiția crește numărul.

Greșeli frecvente

1. Confuzia cu combinări

“Câte echipe de 3 din 10?” → combinări (ordinea nu contează). “Câte moduri de alegere a unui șef, un vicepreședinte și un secretar din 10?” → aranjamente (ordinea = rolurile contează).

2. k > n

A(5, 7) = 0 (nu poți alege 7 distincte din 5). Verifică mereu condiția k ≤ n.

3. Aranjamente cu vs fără repetiție

“Cate numere de 3 cifre?” - cifrele se pot repeta → 9 * 10 * 10 = 900. “Cate numere de 3 cifre distincte?” - fără repetiție → 9 * 9 * 8 = 648.

4. Overflow

int a = 1;
for (int i = 0; i < 10; i++) a *= (20 - i); // OVERFLOW!

Pentru n ≥ 12, folosește long long.

Ce să reții

• Aranjament = alegere ordonată de k din n, fără repetiție.
• A(n, k) = n!/(n-k)! = n * (n-1) * … * (n-k+1).
• A(n, n) = P(n) = n! (permutare = aranjament cu k=n).
• A(n, k) = C(n, k) * k! (alege + ordonează).
• Cu repetiție: n^k.
• Ordinea contează = aranjament. Ordinea nu contează = combinare.