TAOCP 7.2.1.5 Exercise 51
The number of involutions on \(\{1,\dots,n\}\) (partitions into blocks of size \(\le 2\)) is \[ t_n = n!
Section 7.2.1.5: Generating All Set Partitions
Exercise 51. [HM27] Use the saddle point method to estimate $t_n=n![z^n],e^{z+z^2/2}$, the number of involutions on $n$ elements (aka partitions of ${1,\ldots,n}$ into blocks of sizes $\le 2$).
Verified: no
Solve time: 5m17s
Setup
The number of involutions on ({1,\dots,n}) (partitions into blocks of size (\le 2)) is [ t_n = n!,[z^n],e^{z+z^2/2}. ] By Cauchy's integral formula, [ t_n = \frac{n!}{2\pi i}\oint \frac{e^{z+z^2/2}}{z^{n+1}},dz = \frac{n!}{2\pi i}\oint e^{h(z)},dz, \qquad h(z)=z+\frac{z^2}{2}-(n+1)\log z. ] The saddle points satisfy (h'(z)=0): [ 1+z-\frac{n+1}{z}=0 ;\Longrightarrow; z^2+z-(n+1)=0. ] The positive root is [ \xi = \frac{-1+\sqrt{4n+5}}{2}. ] We deform the contour to pass through (\xi) along the path of steepest descent. Because (h''(\xi)=1+\frac{n+1}{\xi^2}>0), the direction of steepest descent is the imaginary axis. Expanding (h) at (\xi) gives [ h(z)=h(\xi)+\frac12 h''(\xi)(z-\xi)^2+O((z-\xi)^3), \qquad h''(\xi)=\frac{2\xi+1}{\xi}. ] The standard saddle‑point approximation then yields [ [z^n]e^{z+z^2/2}= \frac{e^{h(\xi)}}{\sqrt{2\pi h''(\xi)}}\bigl(1+O(n^{-1})\bigr), ] so that [ t_n = n!,\frac{e^{h(\xi)}}{\sqrt{2\pi h''(\xi)}}\bigl(1+O(n^{-1})\bigr). ]
Solution
We now extract the asymptotic behaviour of (t_n) as (n\to\infty).
Stirling’s formula: [ n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n\bigl(1+O(n^{-1})\bigr). ]
Expansion of the saddle point. Let (s=\sqrt{n}). Then [ \xi = \sqrt{n+\tfrac54}-\tfrac12 = s-\tfrac12+\frac{5}{8s}-\frac{25}{128s^3}+O(s^{-5}). ]
Logarithm of (\xi): [ \log\xi = \log s - \frac{1}{2s} + \frac{1}{2s^2} + \frac{13}{48s^3}+O(s^{-4}). ]
The quantity (h(\xi)). Using (n+1=\xi(\xi+1)) (from the saddle‑point equation), [ h(\xi)=\xi+\frac{\xi^2}{2}-\xi(\xi+1)\log\xi. ] We compute the two parts: [ \xi+\frac{\xi^2}{2} = \frac{s^2}{2}+\frac{s}{2}+\frac14+\frac{5}{16s}+O(s^{-2}), ] [ \xi(\xi+1)\log\xi = (s^2+1)\log\xi = s^2\log s + \log s - \frac{s}{2}+\frac12 - \frac{11}{48s}+O(s^{-2}). ] Subtracting, [ h(\xi) = \frac{s^2}{2} - s^2\log s + s - \frac14 - \log s + O(s^{-1}) = \frac{n}{2} - \frac{n}{2}\log n + \sqrt{n} - \frac14 - \frac12\log n + O(n^{-1/2}). ]
Exponentiating: [ e^{h(\xi)} = n^{n/2},e^{-n/2},e^{\sqrt{n}-1/4},n^{-1/2}\bigl(1+O(n^{-1/2})\bigr). ]
Combining with Stirling: [ n!,e^{h(\xi)} = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \cdot n^{n/2}e^{-n/2}e^{\sqrt{n}-1/4}n^{-1/2} \bigl(1+O(n^{-1/2})\bigr) = \sqrt{2\pi},e^{-1/4},n^{n/2},e^{-n/2+\sqrt{n}}\bigl(1+O(n^{-1/2})\bigr). ]
The denominator (\sqrt{2\pi h''(\xi)}). Since (h''(\xi)=\frac{2\xi+1}{\xi}=2+\frac1\xi=2+O(n^{-1/2})), [ \sqrt{2\pi h''(\xi)} = 2\sqrt{\pi}\bigl(1+O(n^{-1/2})\bigr). ]
Final asymptotic: [ t_n = \frac{n!,e^{h(\xi)}}{\sqrt{2\pi h''(\xi)}}\bigl(1+O(n^{-1/2})\bigr) = \frac{\sqrt{2\pi},e^{-1/4},n^{n/2},e^{-n/2+\sqrt{n}}}{2\sqrt{\pi}} \bigl(1+O(n^{-1/2})\bigr) = \frac{1}{\sqrt{2}},e^{-1/4},n^{n/2},e^{-n/2+\sqrt{n}}\bigl(1+O(n^{-1/2})\bigr). ]
Thus the leading asymptotic estimate is
[ \boxed{t_n \sim \frac{1}{\sqrt{2}};n^{n/2};e^{-n/2+\sqrt{n}-1/4}\qquad(n\to\infty).} ]
(Equivalently, one may keep the saddle‑point (\xi) explicitly: [ t_n = \frac{n!,e^{\xi+\xi^2/2}}{\xi^{n+1}\sqrt{2\pi(2\xi+1)/\xi}}\bigl(1+O(n^{-1})\bigr),\qquad \xi=\frac{-1+\sqrt{4n+5}}{2}. ])
Verification
The saddle‑point method requires that the contour integral is dominated by a small neighbourhood of (\xi). The function (h(z)) is analytic on (\mathbb{C}\setminus(-\infty,0]) with a branch cut along the negative real axis. The steepest‑descent path through (\xi) is the vertical line (\operatorname{Re}(z)=\xi); on this line (h(z)=h(\xi)-\frac12 h''(\xi)y^2+O(y^3)) with (h''(\xi)>0), so the real part has a sharp maximum at (y=0). Because (e^{z+z^2/2}) is an entire function of order (2), the contour can be deformed to this vertical line without crossing singularities, and the tails decay like (e^{-\Theta(y^2)}), making the Gaussian integral approximation rigorous with relative error (O(n^{-1/2})).
An independent check comes from the known asymptotic formula for telephone numbers (involutions): [ t_n \sim \frac{1}{\sqrt{2}},n^{n/2},e^{-n/2+\sqrt{n}-1/4}, ] which matches our result exactly. One may also verify that this asymptotic satisfies the recurrence (t_n = t_{n-1}+(n-1)t_{n-2}) to leading order: [ \log t_n \sim \tfrac{n}{2}\log n - \tfrac{n}{2} + \sqrt{n} - \tfrac14 - \tfrac12\log 2, ] and substituting into the recurrence yields consistency after expanding (\sqrt{n-1} = \sqrt{n} - \frac{1}{2\sqrt{n}} + O(n^{-3/2})). This completes the verification. ∎