Aranjamente cu repetiție

Aranjamentele cu repetiție seamănă cu aranjamentele obișnuite, doar că permitem elementelor din mulțimea de bază M să se repete.

Definiție și formulă

Începem cu un exemplu clasic: câte cuvinte diferite putem forma cu literele alfabetului englez (abc … xyz, sunt 26), dacă vrem ca un cuvânt să aibă lungimea 6? Șase litere nu sunt multe, totuși cuvintele vor fi destul de multe. Nu ne interesează sensul cuvintelor, așa că și „weqrww” îl considerăm un cuvânt valid de lungime șase.

Pentru calcul ne trebuie doar regula produsului. Avem în total 26 de litere diferite pe care le putem folosi. Pe primul loc putem pune deci una dintre cele 26 de litere. Dar și pe al doilea loc putem pune una dintre cele 26 de litere, pentru că nu am pus condiția ca literele să nu se repete. Ajungem astfel la faptul că pe fiecare poziție alegem din 26 de litere, iar numărul total de aranjamente este, conform regulii produsului, 26⁶ = 308.915.776. Este destul de mult, având în vedere că am folosit doar 26 de litere.

Spunem că un aranjament cu repetiție de k elemente din mulțimea M cu n elemente este orice k-uplu ordonat ale cărui elemente sunt din mulțimea M și în care fiecare element poate apărea de până la k ori. Dacă avem deci mulțimea M = {1, 2, 3}, atunci toate acestea sunt aranjamente cu repetiție valide de câte 4 elemente: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Numărul unor astfel de aranjamente cu repetiție, notat ${\bar{A}}_n^k$, este egal cu

$${\bar{A}}_n^k=n^k.$$

Exemple rezolvate

1. Câte numere de șase cifre se pot forma din cifrele {2, 4, 6, 8}, dacă cifrele se pot repeta? Pur și simplu înlocuim în formulă, mulțimea are 4 elemente și alegem grupe ordonate de câte șase:

   $${\bar{A}}_4^6=4^6=4096.$$

2. În calculatoare se folosește de obicei sistemul de numerație binar, adică sistemul care folosește doar cifrele 0 și 1. Acolo se introduc unități noi, de exemplu un bit reprezintă un fel de celulă în care se memorează exact fie zero, fie unu. Mai mare este octetul (în engleză byte), care conține 8 biți. Deci 1 este un bit, în timp ce 01110001 este un octet. În câte moduri diferite se poate umple un octet cu 8 biți?

   Alegem din mulțimea {0, 1}, adică din două elemente. Alegem un k-uplu cu k = 8, deci numărul tuturor posibilităților este egal cu

   $${\bar{A}}_2^8=2^8=256.$$

3. Din exemplul anterior știm că un octet poate distinge până la 256 de valori diferite. În câte moduri se pot umple 4 octeți?

   Patru octeți conțin 4 · 8 = 32 de biți, iar noi alegem în continuare dintr-o mulțime cu 2 elemente. Deci rezultatul este:

   $${\bar{A}}_2^{32}=2^{32}=4.294.967.296.$$

   Vedem că doar patru octeți pot distinge peste patru miliarde de valori. Ca să-ți faci o idee: calculatoarele de azi au discuri de sute de gigaocteți sau chiar de teraocteți. Un teraoctet conține 1.000.000.000.000 de octeți și deci 8.000.000.000.000 de biți. Pe un disc de un teraoctet putem deci stoca până la 2^{8.000.000.000.000} de valori diferite.

   Observație: în prezent există o ușoară confuzie în legătură cu noțiunea de kilooctet (megaoctet etc.). Din motive tehnologice, un kilooctet nu conținea 1000 de octeți, cum se obișnuiește la celelalte unități (un kilogram este egal cu o mie de grame), ci era egal cu 2¹⁰ octeți, adică 1024 de octeți. Un megaoctet era apoi 2²⁰ octeți sau, la fel, 2¹⁰ kiloocteți.

   În prezent distingem deci două feluri de notații: 1 kB (se citește kilooctet) este 1000 de octeți, iar 1 KiB (se citește kibioctet) este 2¹⁰ = 1024 de octeți.

4. Un alt exemplu se găsește într-un articol separat, dedicat securității parolei.

Surse și lecturi suplimentare

• Bělohlávek, Vychodil: Diskrétní matematika (în limba cehă)