Faktoriāls

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt
n n!
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
14 87178291200
15 1307674368000
16 20922789888000
17 355687428096000
18 6402373705728000
19 121645100408832000
20 2432902008176640000
25 1,5511210043 × 1025
50 3,0414093202 × 1064
70 1,1978571670 × 10100
100 9,3326215444 × 10157
450 1,7333687331 × 101000
1000 4,0238726008 × 102567
3249 6,4123376883 × 1010000
10000 2,8462596809 × 1035659
25206 1,2057034382 × 10100000
100000 2,8242294080 × 10456573
205023 2,5038989317 × 101000004
1000000 8,2639316883 × 105565708
1723508 5,2900703070 × 1010000001
2000000 3,7768210576 × 1011733474
10000000 1,2024234005 × 1065657059
14842907 2,7886629747 × 10100000000
10100 109,9565705518 × 10101

Matemātikā par naturāla skaitļa n ≥ 1 faktoriālu sauc visu naturālo skaitļu no 1 līdz n reizinājumu. To apzīmē ar n!. Piemēram, 3! = 1 · 2 · 3 = 6, 4! = 1 · 2 · 3 · 4 = 24 utt.

Apzīmējumu n! ieviesis franču matemātiķis K. Kramps 1808. gadā.

Definīcija[izmainīt šo sadaļu | labot pirmkodu]

Naturāla skaitļa n ≥ 1 faktoriālu definē šādi:


  n! = \prod_{i=1}^n i = 1 \cdot 2 \cdot \dots \cdot n,

kur simbols "Π" (lielais grieķu burts ) apzīmē reizinājumu (tāpat kā burts "Σ" apzīmē summu).

Matemātikā ir pieņemts, ka tukšais reizinājums jeb reizinājums, kurā neietilpst neviens skaitlis, ir vienāds ar 1, tāpēc

 0! = 1. \,

Šī vienošanās nodrošina to, ka daudzas formulas, kurās ietilpst faktoriāls, ir spēkā arī robežgadījumos, kad kāds mainīgais kļūst vienāds ar 0. Piemēri:

  • rekurenta sakarība (n+1)! = n!×(n+1) ir pareiza arī pie n = 0, ne tikai pie n > 0.
  • binomiālais koeficients \scriptstyle C^{n}_{n} = \tbinom{n}{n} = \tfrac{n!}{n!(n-n)!} = \tfrac{1}{0!} = 1, jo n elementus no n elementiem var izvēlēties tieši vienā veidā.
  • tas dod iespēju kompakti pierakstīt dažādas rindas, piemēram
e^x = \sum_{n = 0}^{\infty}\frac{x^n}{n!}

Faktoriāla rekursīva definīcija[izmainīt šo sadaļu | labot pirmkodu]

Faktoriālu ir iespējams definēt arī rekursīvi:


  n! =
  \begin{cases}
    1,              & \text{ ja } n = 0; \\
    n \cdot (n-1)!, & \text{ ja } n > 0.
  \end{cases}

Piemēram, pēc šīs definīcijas 3! = 3 · 2! = 3 · 2 · 1! = 3 · 2 · 1 · 0! = 3 · 2 · 1 · 1 = 6. Šai definīcijai var saskatīt līdzību ar matemātisko indukciju: pirmais gadījums n = 0 atbilst indukcijas bāzei, bet otrais gadījums n > 0 atbilst induktīvajai pārejai.

Faktoriāls ir viena no visvienkāršākajām rekursīvi definējamajām funkcijām, tāpēc to bieži izmanto kā piemēru mācot rekursiju programmēšanā. Programmēšanas valodā C funkciju, kas aprēķina faktoriālu, var definēt šādi:[1]

int factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return n * factorial(n - 1);
}

Īpašības[izmainīt šo sadaļu | labot pirmkodu]

Svarīga faktoriāla īpašība ir tāda, ka n dažādus objektus rindā var izvietot tieši n! dažādos veidos. Tātad, n! ir permutāciju skaits no n elementiem.

Saistība ar Gamma funkciju[izmainīt šo sadaļu | labot pirmkodu]

Gamma funkcija (apzīmē ar "Γ" jeb lielo grieķu burtu gamma) ir faktoriāla vispārinājums, jo tai ir spēkā vienādība \Gamma(n + 1) = n! \,, ja n = 0, 1, 2, ..., bet tā ir definēta jebkuram kompleksam skaitlim, izņemot veselus negatīvus skaitļus.
Kompleksam skaitlim z, kura reālā daļa ir pozitīva, to definē šādi:

 \Gamma(z) = \int_0^\infty  t^{z-1} e^{-t}\,dt.

Ar analītiskā turpinājuma palīdzību šo definīciju var paplašināt visiem kompleksiem skaitļiem, izņemot negatīvus veselus skaitļus. Izmantojot šo definīciju un integrāļu īpašības, var pierādīt, ka

\Gamma(n + 1) = n!, \,   ja n = 0, 1, 2, …

Izmantojot gamma funkciju, faktoriālu var aprēķināt, piemēram, skaitļiem formā n + \frac{1}{2}, kur n = 0, 1, 2, …:

 \left( n + \frac{1}{2} \right)! = \sqrt{\pi} \prod_{k=0}^n \frac{2k + 1}{2}.

Piemēram,


  3{,}5! = \sqrt{\pi}
  \cdot {1 \over 2}
  \cdot {3 \over 2}
  \cdot {5 \over 2}
  \cdot {7 \over 2}
  \approx 11{,}63.

Stirlinga formula[izmainīt šo sadaļu | labot pirmkodu]

Lai aprēķinātu faktoriālu lielam skaitlim, ir jāveic ļoti daudz reizināšanas darbību. Bieži vien (piemēram, datorzinātnē, lai novērtētu kāda algoritma sarežģītību), nav nepieciešams zināt precīzu faktoriāla vērtību, bet pietiek ar aptuvenu tā novērtējumu. Šādos gadījumos lieti noder faktoriāla asimptotiskais novērtējums, ko sauc par Stirlinga formulu:

n! \sim \sqrt{2 \pi n} \cdot \left( \frac{n}{e} \right)^n (n \to \infty),

kur π un e ir konstantes un e. Šo formulu ir ieguvis skotu matemātiķis Džeimss Stirlings.
No Stirlinga formulas seko, ka \log (n!) = \Theta(n \log n)\,.
Ir pierādīts arī, ka visiem naturāliem n

n! > \sqrt{2 \pi n} \cdot \left( \frac{n}{e} \right)^n.

Faktoriāla sadalījums pirmreizinātājos[izmainīt šo sadaļu | labot pirmkodu]

A. M. Ležandrs ir pierādījis, ka jebkurš pirmskaitlis p ietilpst skaitļa n! sadalījumā pirmreizinātājos


  \left\lfloor \frac{n}{p  } \right\rfloor +
  \left\lfloor \frac{n}{p^2} \right\rfloor +
  \left\lfloor \frac{n}{p^3} \right\rfloor +
  \ldots

reižu, kur \lfloor x \rfloor apzīmē x noapaļošanu uz leju. Šajā summā visi saskaitāmie sākot ar kādu būs vienādi ar 0, tāpēc pietiek saskaitīt tikai pirmos saskaitāmos, kuri ir lielāki par 0. Formulā ievietojot p = 5, iegūst nuļļu skaitu ar ko beidzas n!. No šīs formulas izriet arī tas, ka

 n! = \prod_{p} p^{\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \ldots},

kur reizinājums ir pār visiem pirmskaitļiem p kas nepārsniedz n.

Pielietojums[izmainīt šo sadaļu | labot pirmkodu]

Faktoriāli ir bieži sastopami kombinatorikā, varbūtību teorijā, skaitļu teorijā, grafu teorijā un matemātiskajā analīzē.

Skatīt arī[izmainīt šo sadaļu | labot pirmkodu]

Piezīmes[izmainīt šo sadaļu | labot pirmkodu]

  1. Šī funkcija nebeidz darbu, ja tai padotais arguments ir negatīvs. Lai no tā izvairītos, n == 0 var aizstāt ar n <= 0, taču tas nav darīts, lai saglabātu līdzību ar matemātisko definīciju.

Ārējās saites[izmainīt šo sadaļu | labot pirmkodu]