Factorial

În matematică factorialul unui număr întreg pozitiv n este notat cu n! și este egal cu produsul numerelor naturale mai mici sau egale cu n. Prin definiție, 0!=1.

Factorialul unui număr oarecare n indică numărul de permutări (numărul de posibilități de rearanjare) ale unei mulțimi finite având n elemente.

Definiții

Factorialul poate fi definit:

• iterativ: \( n! = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot n \), \(0!=1\)
• recursiv: \( n! = \begin{cases}
  1& \text{dacă } n = 0 ,\\
  n \cdot (n-1)! & \text{altfel}.
  \end{cases} \)

Observații

Obs. 1: Factorialul crește foarte repede. Pentru valori mici ale lui n, valoarea lui n! depășește tipurile de date standard:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800 -> depaseste tipul int  
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000 
21! = 51090942171709440000 -> depaseste tipul long long int

Obs. 2: Pentru n≥5, ultima cifră a lui n! este 0.

Cifra 0 de la finalul unui produs, provine din 2*5. Numărul de zerouri de la finalul unui este egal cu minimul dintre exponentul lui 2 și exponentul lui 5 în descompunerea în factori prim a produsului, aceasta obținându-se din descompunerea în factori prim a fiecărui factor. În cazul lui n!, numărul de zerouri de la final este egal cu exponentul lui 5 în descompunerea în factori. El poate fi determinat astfel:

Obs. 3: Numărul de zerouri de la finalul lui n! este egal cu \( [\frac {n}{5}] + [\frac {n}{5^2}] + [\frac {n}{5^3}] + \cdots\ + [\frac {n}{5^k}] + \cdots \), unde \( [x] \) reprezintă partea întreagă a numărului real \( x \). Pentru \( k \) suficient de mare \( 5^k > n\) și \( [\frac {n}{5^k}] \) devine 0.

O sursă C++ care determină rezultatul este:

#include <iostream>

using namespace std;

int main()
{
    int n, p = 5, s = 0;
    cin >> n;

    while(p <= n)
        s += n / p, p *= 5;

    cout << s;

    return 0;
}

Observația de mai sus este o consecință a:

Obs. 4: Pentru un n dat și un număr prim p, exponentul lui p în descompunerea în factori primi a lui n! este \( [\frac {n}{p}] + [\frac {n}{p^2}] + [\frac {n}{p^3}] + \cdots\ + [\frac {n}{p^k}] + \cdots \), rezultat cunoscut ca formula lui Legendre.

O scriere alternativă este dată în următoarea observație:

Obs. 5: Pentru un n dat și un număr prim p, exponentul lui p în descompunerea în factori primi a lui n! este \( \frac {n-s_{p}(n)}{p-1}\), unde \( s_{p}(n)\) reprezintă suma cifrelor reprezentării în baza p a numărului n.

Pentru mai multe informații, vizitați pagina Factorial – Wikipedia.