Faktoriál

EU Agency -- individuální doučování a jazyková výuka po celé ČR

Faktoriál čísla n je součin všech celých kladných čísel, která jsou menší nebo rovna číslu n. Faktoriál zapisujeme pomocí vykřičníku n!. Přičemž pro nulu platí: 0! = 1. Faktoriál se využívá především v kombinatorice, kde se pomocí něj počítá například permutace. Například faktoriál z pěti by se rovnal 5 · 4 · 3 · 2 · 1, tedy sto dvaceti.

Definice faktoriálu

Faktoriál můžeme definovat různými způsoby. Ten nejjednodušší je asi tento:

$n!=\left\{\begin{array}{cc}n=0&1\\n>0&n\cdot (n-1)!\end{array}$

Můžeme uvést i další definice:

$n!=\prod_{k=1}^nk$

…či ještě bláznivější definici :-).

$(z-1)!=\Gamma (z):=\int_{0}^{\infty}t^{z-1}\mathrm{e}^{-t}\mathrm{d}t,\qquad\Re (z)>0.$

zdroj: Matematické fórum.

Počítání s faktoriály

S faktoriály se často počítá ve zlomcích. Zde se pak využívá faktu, že n! = n·(n-1)!. Díky tomu můžeme mnoho různých faktoriálů ve zlomcích efektivně zkrátit. Ukázkový příklad – zjednodušte výraz:

$\frac{n!}{(n-2)!}$

Zjednodušení provedeme podle vzorce, který jsem před chvíli zmínil. V čitateli můžeme faktoriál rozdělit na n·(n-1)! a toto ještě (podle stejného vzorce) můžeme rozložit na n·(n-1)·(n-2)!. Nyní už můžeme zlomek hezky zkrátit:

$\frac{n!}{(n-2)!}=\frac{n\cdot(n-1)\cdot(n-2)!}{(n-2)!}=\frac{n\cdot(n-1)\cdot\strike{(n-2)!}}{\strike{(n-2)!}}=n\cdot(n-1)$

Další příklad. Budeme stále využívat stejného faktu jako v předchozím případě. Jen explicitně zmíním, že stejně jako můžeme rozložit n! = n·(n-1)!, můžeme udělat (n+2)! = (n+2)·(n+1)!.

$\frac{n!\cdot(n+1)!}{(n-1)!(n+2)!}=\frac{n\cdot(n-1)!\cdot(n+1)!)}{(n-1)!(n+2)!}=\frac{n\cdot\strike{(n-1)!}\cdot(n+1)!}{\strike{(n-1)!}(n+2)!}=\\=\frac{n\cdot(n+1)!}{(n+2)!}=\frac{n\cdot(n+1)!}{(n+2)\cdot(n+1)!}=\frac{n\cdot\strike{(n+1)!}}{(n+2)\cdot\strike{(n+1)!}}=\frac{n}{n+2}$

Klasický příklad v programování

Vzhledem k tomu, že faktoriál je obvykle všem, i začínajícím, programátorům dobe známá věc, bývá faktoriál oblíbeným příkladem na demonstraci rekurze v tom či onom programovacícm jazyku. Následuje ukázka řešení funkce pro výpočet faktoriálů ve dvou různých programovacích jazycíh. Nejprve C#:

// Asi nejkratší zápis, ne zrovna moc čitelný.
public static long Faktoriál(int n)
{
    return n == 0 ? 1 : n * Faktoriál(n - 1);
}

// Patrně nejobvyklejší zápis faktoriálu
public static long Faktoriál2(int n)
{
    if(n == 0)
        return 1;
    else
        return n * Faktoriál2(n - 1);
}

// Iterativní verze s koncovou rekurzí
// Musí se volat se dvěma parametry, 
// výsledek musí být na začátku jedna.
// (Lze pochopitelně obejít přes přetížení metody.)
public static long Faktoriál3(int vstup, int výsledek)
{
    if(vstup == 0)
        return výsledek;
    else
        return Faktoriál3(vstup - 1, vstup * výsledek);
}

// Verze pomocí cyklu. 
// V běžných jazycích nejrychlejší verze,
// protože se nemusí vytvářet mnoho rámců volání.
public static long Faktoriál4(int n)
{
    int výsledek = 1;
    for(; n > 0; n--)
        výsledek *= n;

    return výsledek;
}

Jako zástupce méně běžných jazyků si zvolím Lisp. Výpočet faktoriálu by tam mohl probíhat takto:

(defun factorial (n)
  (if (zerop n)
      1
    (* n (factorial (1- n)))))

(defun factorial2 (vstup vysledek)
  (if (zerop vstup)
      vysledek
    (factorial2 (1- vstup) (* vstup vysledek))))