Silnia

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Silnią liczby naturalnej n (w notacji matematycznej: n!, co czytamy „n silnia”) nazywamy iloczyn wszystkich liczb naturalnych nie większych niż n. Oznaczenie n! wprowadził w 1808 roku Christian Kramp.

Definicja[edytuj | edytuj kod]

Funkcję \cdot\; !\colon \mathbb{N}_{0} \to \mathbb{N}_{+} definiuje się następująco:

n!=\prod_{k=1}^n k\qquad\mbox{dla }n\geqslant1.\,\!

Wzór ten nie podaje wartości 0!, określamy ją osobno:

0! = 1 \ .

Poniżej definicja rekurencyjna


  n!=\begin{cases}
    1 & \mbox{ dla }n=0 \\
    n\cdot(n-1)! & \mbox{ dla }n\geqslant1
   \end{cases}

Przykłady:

4! = 1 · 2 · 3 · 4 = 24.
5! = 1 · 2 · 3 · 4 · 5 = 120.
6! = 1 · 2 · 3 · 4 · 5 · 6 = 720.

Wartość n! pozwala określić liczbę możliwych permutacji n elementów.

Obliczenia przybliżone[edytuj | edytuj kod]

Silnia pojawia się w tak wielu praktycznych zastosowaniach matematyki (rachunek prawdopodobieństwa, statystyka), że szczególnej wagi nabiera problem szybkiego wyznaczania silni dużych liczb. Podane wyżej określenia silni nie nadają się do tego celu, dlatego na ogół wykorzystuje się przybliżony wzór Stirlinga:

n!\approx\sqrt{2\pi n}\left(\frac{n}{e}\right)^n

Wynika z niego także postać logarytmu silni:

\ln n! \approx n\ln n - n + \frac{1}{2} \ln (2\pi n) \

Przydatne jest również oszacowanie:

n!=o(n^n) \

Dokładniejsza od wzoru Stirlinga jest formuła:

n!  =  \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{\alpha_n}

gdzie

\frac{1}{12n+1} \leqslant \alpha_n \leqslant \frac{1}{12n}

Uogólnienia[edytuj | edytuj kod]

Funkcja gamma[edytuj | edytuj kod]

Uogólnieniem pojęcia silni jest funkcja gamma.

Silnia podwójna n!![edytuj | edytuj kod]

Silnią podwójną liczby naturalnej n określa się iloczyn liczb naturalnych z krokiem 2 do n. Silnię podwójną oznacza się n!!.

Rekurencyjna definicja silni podwójnej:


  n!!=
   \begin{cases}
    1 & \mbox{ dla }n=0\mbox{ lub }n=1  \\
    n\cdot(n-2)!! & \mbox{ dla }n\geqslant 2
   \end{cases}

Przykład:

8!! = 2 · 4 · 6 · 8 = 384
9!! = 1 · 3 · 5 · 7 · 9 = 945

Własności podwójnej silni:

n!=n!!(n-1)!!\,\!
(2n)!!=2^nn!\,\!
(2n+1)!!={(2n+1)!\over(2n)!!}={(2n+1)!\over2^nn!}\,\!

zależność od funkcji gamma:

\Gamma\left(n+{1\over2}\right)=\sqrt\pi{(2n-1)!!\over2^n}\,\!

Silnia wielokrotna[edytuj | edytuj kod]

Silnia podwójna jest szczególnym przypadkiem silni wielokrotnej. Podobnie można zdefiniować silnię potrójną n!!! oraz ogólnie silnie k-tą, którą oznaczamy jako n!(k). Jej definicję rekurencyjną przedstawia wzór:


  n!^{(k)}=
   \begin{cases}
    1 & \mbox{ gdy }0\leqslant n<k   \\
    n\cdot(n-k)!^{(k)} & \mbox{ gdy }n\geqslant k
   \end{cases}

Rozkład silni na czynniki pierwsze[edytuj | edytuj kod]

Lemat

Jeżeli liczba n! rozkłada się na czynniki pierwsze:

n!=\prod_{i=1}^{k}p_{i}^{ \alpha_{i} }=p_{1}^{ \alpha_{1} } \cdot p_{2}^{ \alpha_{2} } \cdot \ldots  \cdot p_{k}^{ \alpha_{k} }

to

\mbox{ord}_{p_i}(n!) = \sum_{j=1}^{ \left\lfloor \log_{p_{i}}n\right\rfloor }  \left\lfloor  \frac{n}{p_{i}^{j}} \right\rfloor

tzn. liczba pierwsza p_{i} pojawia się z wykładnikiem:

\alpha_{i} = \sum_{j=1}^{ \left\lfloor \log_{p_{i}}n\right\rfloor }  \left\lfloor  \frac{n}{p_{i}^{j}} \right\rfloor

gdzie \lfloor x \rfloor oznacza część całkowitą liczby x.

Problem ustalenia liczby zer na końcu zapisu dziesiętnego silni[edytuj | edytuj kod]

Liczbę zer na końcu w zapisie dziesiętnym n!, przy czym n jest liczbą naturalną, można ustalić na podstawie wzoru

f(n) = \sum_{i=1}^k \left \lfloor \frac{n}{5^i} \right \rfloor =
\left \lfloor \frac{n}{5} \right \rfloor + \left \lfloor \frac{n}{5^2} \right \rfloor + \left \lfloor \frac{n}{5^3} \right \rfloor + \cdots + \left \lfloor \frac{n}{5^k} \right \rfloor, \,

gdzie k musi spełniać warunek


5^{k} \leq n < 5^{k+1},\,

Na przykład: 53 > 26 i 26! = 403291461126605635584000000 kończy się

\left \lfloor \frac{26}{5} \right \rfloor + \left \lfloor \frac{26}{5^2} \right \rfloor = 5 + 1 = 6\,

zerami. Jeżeli n < 5, nierówności są spełnione przez k = 0; w tym wypadku suma ta daje wynik 0.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Thomas Koshy, Discrete Mathematics with Applications, Elsevier Publications 2006, ss. 219.

Linki zewnętrzne[edytuj | edytuj kod]