Hoe groot zijn faculteiten?

Het blijkt dat er vrij interessante wiskunde achter zit om de grootte (het aantal cijfers) van een faculteit redelijk nauwkeurig te kunnen schatten. Dit artikel begint met de methode om de schatting te maken; wie nieuwsgierig is, kan verder lezen voor de wiskundige achtergrond.

Zonder verdere omhaal is de benadering als volgt:

$$\text{aantal cijfers in } n! \approx n \log_{10}\left(\frac{n}{e}\right) + 2$$

Laten we als voorbeeld mijn oorspronkelijke vraag nemen door dit te schatten voor 52!.

52 gedeeld door $e$ is ongeveer 20. $\log_{10}(20)$ is ongeveer 1,3 [1]. Daarom komt onze schatting uit op:

$$\text{aantal cijfers in } 52! \approx 52 \cdot 1,3 + 2 \approx 69$$

Het werkelijke antwoord is 68, dus dit ligt er zeer dichtbij! Bij schattingen als deze — waarbij je te maken hebt met enorme getallen — is een afwijking van een paar cijfers meestal geen probleem.

De Gamma-functie

De Gamma-functie voor reële $n > 0$ is gedefinieerd [2] als:

$$\Gamma(n) = \int_{0}^{\infty} x^{n-1} e^{-x} dx$$

Deze integraal heeft in het algemene geval geen analytische uitdrukking, maar heeft wel een zeer nuttige eigenschap waar we gebruik van kunnen maken. Laten we kijken naar $\Gamma(n+1)$:

$$\Gamma(n+1) = \int_{0}^{\infty} x^n e^{-x} dx$$

We gebruiken nu partiële integratie met: $u = x^n$ en $v = -e^{-x}$.

Dan is: $du = nx^{n-1} dx$ en $dv = e^{-x} dx$.

Dit geeft:

$$\begin{aligned} \Gamma(n+1) &= \int{0}^{\infty} x^n e^{-x} dx \\ &= \left. -x^n e^{-x} \right|0^\infty - \int{0}^{\infty} -e^{-x} n x^{n-1} dx \\ &= n \int{0}^{\infty} x^{n-1} e^{-x} dx \end{aligned}$$

Merk op dat de laatste integraal simpelweg $\Gamma(n)$ is; we hebben dus aangetoond dat:

$$\Gamma(n+1) = n\Gamma(n)$$

Laten we ook $\Gamma(1)$ berekenen — dit is een speciaal geval met een analytische oplossing:

$$\Gamma(1) = \int{0}^{\infty} e^{-x} dx = \left. -e^{-x} \right|0^\infty = 1$$

Dit helpt bij het opstellen van een inductiebewijs:

$$\begin{aligned} \Gamma(2) &= 1 \cdot \Gamma(1) = 1! \\ \Gamma(3) &= 2 \cdot \Gamma(2) = 2! \\ \Gamma(4) &= 3 \cdot \Gamma(3) = 3! \\ \dots \\ \Gamma(n+1) &= n \cdot \Gamma(n) = n! \end{aligned}$$

Met andere woorden: de Gamma-functie is een interpolatie van de faculteit over alle positieve reële getallen. Hieronder zou een grafiek van de Gamma-functie over een klein bereik staan; let op dat de y-as een logaritmische schaal heeft vanwege de snelle groei van de functie.

Stirlings benadering

Je bent wellicht al bekend met de benadering van Stirling:

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

Dit is een uitstekende benadering die redelijk goed werkt, zelfs voor kleine waarden van $n$. Deze sectie is een kort overzicht van hoe de formule van Stirling is afgeleid uit de Gamma-functie.

Uitgaande van:

$$n! = \Gamma(n+1) = \int_{0}^{\infty} x^n e^{-x} dx$$

We beginnen met het iets aanpassen van de integrand:

$$n! = \int{0}^{\infty} x^n e^{-x} dx = \int{0}^{\infty} e^{n \ln x} e^{-x} dx$$

En we maken een variabelenwisseling $x = ny$, wat betekent dat $dx = n dy$:

$$\begin{aligned} n! &= \int{0}^{\infty} n e^{n \ln(ny) - ny} dy = n \int{0}^{\infty} e^{n(\ln n + \ln y - y)} dy \\ &= n e^{n \ln n} \int_{0}^{\infty} e^{n(\ln y - y)} dy \end{aligned}$$

Deze stappen maken de integraal geschikt voor de toepassing van de methode van Laplace, waarmee we bepaalde integralen van de vorm $\int_{a}^{b} e^{n f(x)} dx$ kunnen benaderen.

Hierbij is $f(x)$ een tweemaal differentieerbare functie en $n$ een groot getal. Volgens de methode van Laplace kunnen dergelijke integralen worden benaderd door:

$$\int{a}^{b} e^{n f(x)} dx \approx \sqrt{\frac{2\pi}{n |f''(x0)|}} e^{n f(x_0)}$$

Waarbij $x_0$ het globale maximum is van $f(x)$.

Laten we zien hoe we deze methode [3] toepassen op de laatste vergelijking die we hebben voor $n!$ (waarbij we de dummy-integratievariabele weer terugveranderen naar $x$):

$$n! = n e^{n \ln n} \int_{0}^{\infty} e^{n(\ln x - x)} dx$$

In ons geval is $f(x) = \ln x - x$. Het is eenvoudig aan te tonen dat deze functie tweemaal differentieerbaar is en een globaal maximum heeft bij $x_0 = 1$. Bovendien geldt:

$$\begin{aligned} f(x0) &= -1 \\ f''(x0) &= -1 \end{aligned}$$

Wanneer we deze waarden op de juiste plaatsen in de benadering van Laplace invullen, krijgen we:

$$\begin{aligned} n! &\approx n e^{n \ln n} \sqrt{\frac{2\pi}{n}} e^{-n} \\ &\approx \sqrt{2\pi n} \cdot e^{n(\ln n - 1)} \\ &\approx \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \quad \blacksquare \end{aligned}$$

Aantal cijfers op basis van de benadering van Stirling

We kunnen het aantal cijfers in $n!$ berekenen door de logaritme met grondtal 10 te nemen van de formule van Stirling:

$$\begin{aligned} \text{aantal cijfers in } n! &\approx \log{10} \left( \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \right) \\ &\approx \log{10}(\sqrt{2\pi n}) + \log{10}\left(\frac{n}{e}\right)^n \\ &\approx \log{10}(\sqrt{2\pi n}) + n \cdot \log_{10}\left(\frac{n}{e}\right) \end{aligned}$$

Let op dat de eerste term niet met $n$ wordt vermenigvuldigd; daarom zal deze term steeds minder opvallend worden naarmate $n$ groeit. Desalniettemin voegt het nog steeds een paar cijfers toe — je moet dit dus meerekenen als je een nauwkeurigere benadering wilt [4].

***

Voetnoten:

[1] Mentale trucjes voor het berekenen van $\log{10}$ is een ander onderwerp, maar het helpt enorm om te onthouden dat $\log{10} 2 = 0,3$ en $\log_{10} 3 = 0,5$, en van daaruit de verschillende logaritme-wetten te gebruiken om veelvouden te schatten.

[2] In feite is de Gamma-functie gedefinieerd voor complexe getallen, maar voor ons doel is het voldoende om over reële getallen te spreken.

[3] Hoe graag ik ook zou willen dieper in te gaan op waarom deze benadering werkt, het konijnenhol in dit artikel is al diep genoeg!

[4] Het voegt maximaal 2 extra cijfers toe zolang $n$ kleiner is dan ongeveer 1600, en kan meer dan 2 toevoegen daarna, hoewel niet meer dan 3 totdat $n$ 160.000 is. Het is onduidelijk waarom iemand het aantal cijfers van 1600! (ongeveer 4450, voor het geval dat je je dat afvroeg) zou willen schatten, laat staan 160.000!.