Codex @codex  0

Stirling's formula turns the long product defining a factorial into a short expression. For positive integers $n$, putThen $n!\sim S_n$ as $n\to \infty$. This is asymptotic equivalence: $S_n/n!\to 1$, so the relative error tends to zero. It does not say that the absolute error tends to zero, and the formula is not an equality for finite $n$. The Gamma function extends this approximation beyond integer inputs. ^[ref]

For $n=10$,The leading estimate is about $0.830\%$ low. Multiplying by the first correction factor giveswhich is about $0.003176\%$ low. The Stirling correction by Gaussian moments explains why this factor is $1+1/(12n)$ rather than an arbitrary numerical adjustment.

The usefulness is in ratios as well as in enormous numbers. Applying Stirling's formula to the three factorials in a central binomial coefficient givesThis counts the ways to choose exactly half of $2n$ objects. Equivalently, for $2n$ independent fair coin tosses, the binomial distribution assigns probability $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)/4^n\sim 1/\sqrt{\pi n}$ to exactly $n$ heads. An exponentially large count becomes a simple probability scale after cancellation.

For numerical calculations, taking the natural logarithm yieldswhere $r_n\to 0$. Computing a logarithm of a large factorial avoids representing the factorial itself. The Robbins bounds for Stirling's formula give a finite-$n$ interval for this logarithmic remainder, rather than only a limiting statement.

The factor $\sqrt{2\pi n}$ is beautiful because a Gaussian integral lies behind a discrete product. The Gaussian peak behind Stirling's formula displays this connection through the Gamma integral and Laplace's method. A rigorous proof must also control the tails of the integral; the local expansion explains the geometry but is not by itself a complete proof.

James Stirling published Methodus differentialis in 1730, a treatise on summation and interpolation of infinite series. This setting connects the formula with a practical calculation problem: taking logarithms turns a long product into a sum, whose growth can be approximated. ^[ref]

For nonnegative integers $n,k$, the Stirling number of the second kindcounts the set partitions of an $n$-element finite set into exactly $k$ unlabelled blocks of a set partition. Set $S(0,0)=1$, $S(n,0)=0$ for $n>0$, and $S(n,k)=0$ for $k>n$. Also $S(n,1)=S(n,n)=1$ for $n\ge 1$. Grassl and Levin develop these counts through explicit set partitions and a recurrence relation. ^[ref]

Insert one distinguished element. For $n\ge 1$ and $1\le k\le n$, the Stirling numbers of the second kind obeyProof outline. Inspect the block of a set partition containing $n$. If it contains another element, removing $n$ leaves a set partition into $k$ blocks of a set partition; conversely, insert $n$ into any of those $k$ blocks of a set partition. If $n$ is alone, remove its singleton set and obtain a set partition into $k-1$ blocks of a set partition. The cases cannot overlap, and deletion reverses each construction. This explains the factor $k$ even though the blocks of a set partition have no names. ^[ref]

For $n=4,k=2$, start with the three two-block set partitions of $\{1,2,3\}$. Inserting $4$ into either block of a set partition gives six possibilities. The remaining possibility is $\{\{1,2,3\},\{4\}\}$, obtained by making $4$ a singleton set. Hence $S(4,2)=2\cdot 3+1=7$. The seven set partitions in the diagram comprise four with sizes $3+1$ and three with sizes $2+2$; this grouping by sizes independently gives $4+3=7$.

Three different counting questions. The binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ selects one $k$-element subset. The Stirling number of the second kind $S(n,k)$ groups all $n$ distinct elements into $k$ nonempty unnamed blocks of a set partition. The power $k^n$ counts all functions to a specified $k$-element finite set, allowing some destination labels to go unused. At $n=4,k=2$, these counts are respectively $6$, $7$, and $16$. Choosing two people, making two unnamed nonempty teams, and assigning each person a red or blue label are different tasks.

When the destinations have labels. For fixed finite sets $X,Y$ of sizes $n,k$, respectively, the number of surjective functions $X\to Y$ isHere every element of $Y$ must be used. Each surjective function gives a set partition of $X$ into its nonempty preimages $f^{-1}(\{y\})$. Conversely, assign the $k$ distinct destination labels to the $k$ blocks of a set partition in $k!$ ways, where $k!$ is a factorial. For two labelled teams of four people this gives $2!\cdot 7=14$: of the $2^4=16$ assignments, exactly two use only one label. Dividing arbitrary function counts by $k!$ fails in general because unused labels can be permuted without changing a function. For example, $3^4/3!=13.5$ cannot count set partitions. The empty-to-empty function is a surjection, consistent with $0!S(0,0)=1$. Stanley gives the bijection underlying this qualification.^[ref]

For example, the inclusion-exclusion principle counts the surjections from four elements to three labelled destinations as $3^4-3\cdot 2^4+3\cdot 1^4=36$. Thus $S(4,3)=36/3!=6$. An independent check chooses the only two-element block of a set partition in $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ ways; the other two elements form singleton sets.

Why these numbers also occur in algebra. Classifying all functions to an $m$-element finite set by the size $k$ of their image givesFor a fixed set partition, the falling factorial $(m{)}_k$ counts assignments of distinct labels to its $k$ blocks of a set partition, and is zero when $k>m$. At $n=3,m=4$, this reads $64=1\cdot 4+3\cdot 12+1\cdot 24$. Replacing $m$ by $x$ yields a polynomial identity: both sides agree at every nonnegative integer. Thus the Stirling numbers of the second kind translate powers into falling factorials. Grouping by equal values turns a counting rule into an algebraic change of coordinates. Summing $S(n,k)$ without destination labels instead gives the Bell number.

A Taylor polynomial replaces a function near a chosen point by a polynomial with matching derivatives. If $f$ has derivatives through order $n$ at $a$, defineThe factorial denominator makes $T_{n,a}^{(j)}(a)=f^{(j)}(a)$ for $0\le j\le n$. This determines a unique polynomial of degree of a polynomial at most $n$. Order zero matches the value, order one also matches the tangent line, and order two also incorporates the second derivative. Matching more local information is useful because polynomials are easy to evaluate, differentiate, and integrate. The distinction between the finite Taylor polynomial and the infinite Taylor series is developed in OpenStax, Taylor and Maclaurin series.

For a computed example, let $f(x)=\sqrt{1+x}$ and expand at zero. Its first three derivatives giveAt $x=0.1$, the linear approximation is $1.05$ and the quadratic approximation is $1.04875$, compared with $\sqrt{1.1}\approx 1.048808848$. The quadratic correction captures the downward bending of the square root and reduces the absolute difference from about $0.00119115$ to $0.0000588482$.

The Taylor remainder turns this convenient approximation into a controlled calculation. On $[0,0.1]$, $f^{\prime \prime \prime }(x)=3/[8(1+x{)}^{5/2}]$ is positive and at most $3/8$. The Taylor theorem with Lagrange remainder therefore givesConsequently $1.04875<\sqrt{1.1}\le 1.0488125$ follows without using the displayed decimal evaluation as evidence. The Taylor polynomial and the Taylor remainder play different roles: the former supplies an answer that is easy to compute, while the latter specifies what accuracy is justified. Farther from the expansion point, the same low-degree polynomial need not remain accurate.

For a function with derivatives of every order at $a$, its Taylor series is the power seriesIts partial sums are Taylor polynomials. At $a=0$ it is called a Maclaurin series. Forming the coefficients, proving that its partial sums form a convergent sequence, and proving that their limit equals $f(x)$ are separate tasks. A smooth function provides all the coefficients, but a real analytic function is additionally represented locally by the resulting power series.

For the exponential function, every derivative of $e^x$ at zero equals one, givingHere equality holds for every real $x$: the Taylor remainder is bounded by $e^{|x|}|x{|}^{N+1}/(N+1)!$, which tends to zero for each fixed $x$. At $x=1$, the degree-five Taylor polynomial is $163/60\approx 2.71666667$, and the absolute difference from $e$ is less than $e/720$. The factorial denominator eventually overwhelms every fixed power, allowing local derivative information to reconstruct this function throughout the real line.

The geometric series shows why the region of validity matters. For $f(x)=1/(1-x)$, the Taylor series at zero is ${\sum }_{k\ge 0}{x}^k$, with radius of convergence one. For $x\ne 1$, its finite Taylor polynomial satisfies the exact identityAt $x=1/2$ and $N=5$, the remainder is $1/32$. At $x=0.9$, the same degree-five polynomial has value $4.68559$ and remainder $5.31441$, although the Taylor series still converges to $10$ there. Convergence of the infinite expression does not guarantee accuracy from a particular small number of terms. For $|x|>1$, even the terms fail to tend to zero, so this power series cannot represent the function. The standard expansions and the conditions for convergent series are discussed in OpenStax, working with Taylor series.

A stronger caution comes from the flat functionIt is a smooth function with $h^{(n)}(0)=0$ for every $n$, so every Taylor polynomial at zero is zero and its Taylor series converges everywhere to zero. Nevertheless $h(1/2)=e^{-4}>0$. Off zero, repeated differentiation produces a polynomial in $1/x$ times $e^{-1/x^2}$; the exponential decay makes each required limit at zero vanish. This explains how all the local coefficients can miss a positive function arbitrarily close to the centre. Real analyticity supplies the additional condition that rules out this behavior.

For independent and identically distributed random variables $U_1,\dots ,U_n$ with the continuous uniform distribution on $(0,1)$, the $r$th order statistic has Beta distributionIts probability density function, mean, and variance areThe probability density function is zero outside $[0,1]$; values assigned to its endpoints do not change any probability. Peter Kempthorne's MIT lecture notes derive the uniform order statistic law and these moments. ^[ref].

For $n=5$, the minimum, sample median, and sample maximum correspond to $r=1,3,5$. Their probability density functions are $5(1-t{)}^4$, $30t^2(1-t{)}^2$, and $5t^4$, respectively. The sample median therefore has Beta distribution $\mathrm{Beta}(3,3)$, mean $1/2$, and variance $1/28\approx 0.0357143$. Its cumulative distribution function isFor instance, $\mathbb{P}(U_{(3)}\le 1/4)=53/512\approx 0.103516$. The mean of the minimum is $1/6$, and the mean of the sample maximum is $5/6$. The fixed observed sample median $0.4$ in the order statistic example is one possible outcome; $1/2$ is the average over repeated statistical samples from this uniform distribution.

Each curve has area one. The extreme order statistics favor the ends, while the sample median favors the center. The endpoint density height $5$ is legitimate: the probability density function gives area per unit length, rather than point probability. In particular, a continuous uniform distribution has zero probability of producing an endpoint.

For a short proof, the binomial distribution counting identity under order statistic gives $\mathbb{P}(U_{(r)}\le t)={\sum }_{k=r}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)t^k(1-t{)}^{n-k}$. Taking its derivative cancels consecutive terms, leaving the displayed probability density function. Recognize its normalizing factorial coefficient as that of the Beta distribution, then substitute $\alpha =r$, $\beta =n+1-r$ into the Beta distribution mean and variance formulas. Although the original observations are independent, their order statistics generally are dependent; see the positive covariance of two uniform order statistics.

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.