Regula produsului: pe scurt

Regula produsului: dacă o alegere se face în $k$ etape succesive, iar etapa $i$ se poate realiza în $n_i$ moduri indiferent de rezultatele etapelor anterioare, atunci numărul total de posibilități este $n_1\cdot n_2\cdots n_k$. Condiția esențială privește numărul de variante, nu variantele înseși — dacă acest număr depinde de alegerea precedentă, regula nu se aplică direct și problema se împarte în cazuri.

Când elementele se pot repeta, la fiecare din cele $k$ poziții ai aceleași $n$ variante: $n^k$ posibilități (de exemplu, un cod PIN de $4$ cifre are $10^4$ variante). Când elementele nu se repetă, oferta scade cu unu la fiecare pas: $n(n-1)(n-2)\cdots$, cu exact $k$ factori.

La probleme cu restricții (o cifră nu poate fi $0$, ultima cifră trebuie să fie pară), ocupă întâi poziția cea mai restricționată, apoi completează restul — dacă începi cu poziția liberă, te încurci, pentru că numărul de variante rămase depinde de alegerea făcută anterior.

O aplicație elegantă: o mulțime cu $n$ elemente are exact $2^n$ submulțimi, pentru că fiecare element aduce o decizie independentă «îl iau / nu îl iau».

Exerciții din această mini-lecție

1. Câte coduri PIN de $3$ cifre există, dacă cifrele se pot repeta?

   • a) $1000$
   • b) $720$
   • c) $30$
   • d) $100$
   Vezi răspunsul

   Răspuns corect: a) $1000$

   Fiecare din cele $3$ poziții are $10$ variante, iar cifrele se pot repeta: $10\cdot 10\cdot 10=10^3=1000$.

2. Câte coduri PIN de $3$ cifre distincte există?

   • a) $1000$
   • b) $720$
   • c) $27$
   • d) $900$
   Vezi răspunsul

   Răspuns corect: b) $720$

   Prima poziție are $10$ variante, a doua $9$ (cifra folosită dispare), a treia $8$: $10\cdot 9\cdot 8=720$.

3. Câte submulțimi are o mulțime cu $6$ elemente?

   • a) $720$
   • b) $36$
   • c) $64$
   • d) $12$
   Vezi răspunsul

   Răspuns corect: c) $64$

   Pentru fiecare dintre cele $6$ elemente decizi, independent, dacă intră sau nu în submulțime: $2^6=64$ submulțimi (inclusiv mulțimea vidă și mulțimea întreagă).