Stirling's approximation is the following well-known asymptotic result:


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


This result has several analytical proofs, for example via Laplace's method, the trapezoidal rule (and Euler–Maclaurin formula for an asymptotic expansion) or Hayman's method (essentially Cauchy's formula). There are also other (usually ad-hoc) proofs.


The result is applied often in combinatorics and probability, especially in the study of random walks. I want a result which is the other way around - a combinatorial\probabilistic proof for Stirling's approximation. I'm not sure if this is possible, but to convince you that it might be I'll give some partial results.


First, write $n! = \left(\frac{n}{e}\right)^n f(n)$. We'll obtain bounds related to $f(n)$:


* Consider $\{S\_n\}\_{n\ge 0}$, the random walk on $\mathbb{Z}^{d}$, with $S\_0=\vec{0}$. It is recurrent iff $\sum\_{n\ge 1} P(S\_{2n} = \vec{0})$ diverges. This series is $\sum\_{n\ge 1} (2d)^{-2n} \sum\_{a\_1+\cdots+a\_d=n} \binom{2n}{a\_1,a\_1,a\_2,a\_2,\cdots,a\_d,a\_d}$. For $d=1$, this becomes $\sum\_{n\ge 1} \frac{\binom{2n}{n}}{4^n} = \sum\_{n\ge 1} \frac{f(2n)}{f^2(n)}$. There's is Stirling-free proof for the recurrence of the 1-dimensional random walk, using a criterion due to Nash-Williams.
* Similarly, for $d=2$, there's a rotation trick that shows $\sum\_{n\ge 1} P(S\_{2n} = \vec{0})=\sum\_{n\ge 1} \left( \frac{\binom{2n}{n}}{4^n} \right)^2= \sum\_{n\ge 1} \left( \frac{f(2n)}{f^2(n)} \right)^2$. Again, the Nash-Williams criterion proves the recurrence of the 2-dimensional random walk without Stirling, and hence the divergence of said series.
* Back to the 1-dimensional case. Using the reflection principle, the probability that the random walk returns to the origin during the first $2n$ steps is $1-\frac{\binom{2n}{n}}{4^n} = 1-\frac{f(2n)}{f^2(n)}$, and this tends to 1 as the walk is recurrent.
* Still with the 1-dimensional case. One can calculate $E|\frac{S\_n}{\sqrt{n}}|$ explicitly - it is $2^{1-n} \sqrt{n}\binom{n-1}{\lfloor \frac{n-1}{2} \rfloor}$. On the other hand, the CLT together with the notion of uniform integrability justifies the following limit: $\lim\_{n\to\infty} E|\frac{S\_n}{\sqrt{n}}| = E|N(0,1)| = \frac{2}{\sqrt{2\pi}}$. When $n$ is odd this implies $\sqrt{n} \frac{f(n-1)}{f^2(\frac{n-1}{2})} \to \frac{2}{\sqrt{2\pi}}$.


So if we assume $f(n) \approx C \cdot n^{\alpha}$, the first results give bounds on $\alpha$ ($\alpha \le 1, \alpha \le 0.5, \alpha >0$) and the last one gives the true value of $\alpha$ and $C$. The fact that the 3-dimensional random walk is transient implies $\alpha \ge \frac{1}{3}$, but I don't know how to prove it without tools that prove Stirling's approximation.


Questions:


Can we remove\relax the assumption $f(n) \approx C \cdot n^{\alpha}$ somehow? Can we use less analysis than we used in the 3rd result? Are there other combinatorial approaches to the problem that give partial results (or even the full one)? Can the fact that the 3-dimensional random walk is transient be proved Stirling-free (and preferably combinatorially)?



Combinatorial\Probabilistic Proof of Stirling's Approximation
The Wikipedia page [List of probabilistic proofs of non-probabilistic theorems](http://en.wikipedia.org/wiki/List_of_probabilistic_proofs_of_non-probabilistic_theorems) has a reference to the paper:



> 
> Blyth, Colin R.; Pathak, Pramod K.
>  A Note on Easy Proofs of Stirling's Theorem.
>  *Amer. Math. Monthly* **93** (1986), no. 5, 376–379. [MR 1540867](http://www.ams.org/mathscinet-getitem?mr=1540867) [DOI 10.2307/2323600](http://dx.doi.org/10.2307/2323600)
> 
> 
> 


in which several simple proofs of Stirling's approximation are given, using the central limit theorem on Gamma or Poisson random variables.


