Përafrimi i Stirlingut

Krahasimi i përafrimit të Stirlingut me faktorialin

Në matematikë, përafrimi i Stirlingut (ose formula e Stirlingut ) është një përafrim për faktorialët . Është një përafrim i mirë, që çon në rezultate të sakta edhe për vlera të vogla të $n$ . Është emërtuar sipas James Stirling, megjithëse një rezultat i lidhur, por më pak i saktë u shpall për herë të parë nga Abraham de Moivre . [1]

Një mënyrë për të deklaruar përafrimin përfshin logaritmin e faktorialit:

$$\ln(n!)=n\ln n-n+O(\ln n),$$

ku shënimi O e madhe do të thotë se, për të gjitha vlerat mjaft të mëdha të $n$, dallimi mes $\ln(n!)$ dhe $n\ln n-n$ do të jetë të shumtën përpjestimor me logaritmin. Në zbatimet e shkencave kompjuterike të tilla si kufiri i poshtëm në rastin më të keq për renditjen krahasimore, është i përshtatshëm të përdoret në vend të kësaj logaritmi binar, duke dhënë formën ekuivalente

$$\log _{2}(n!)=n\log _{2}n-n\log _{2}e+O(\log _{2}n).$$

Termi i gabimit në secilën bazë mund të shprehet më saktë si ${\tfrac {1}{2}}\log(2\pi n)+O({\tfrac {1}{n}})$, që korrespondon me një formulë të përafërt për vetë faktorialin,

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

Këtu është shenja $\sim$ do të thotë që të dy anët e barazimit janë asimptotike, domethënë se raporti i tyre tenton drejt në 1 si $n$ tenton drejt infinitit. Versioni i mëposhtëm i kufirit vlen për të gjitha $n\geq 1$dhe jo vetëm asimptotikisht :

$${\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}e^{\frac {1}{12n+1}}<n!<{\sqrt {2\pi n}}\ \left({\frac {n}{e}}\right)^{n}e^{\frac {1}{12n}}.$$