Number of permutations on $n$ letters that have only cycles of length $3$ or less (Hayman's method)

Taken from: [1, Exercise 5.8].

Introduction

We will asymptotically analyze the sequence $a_n$ derived from the exponential generating function $\exp\left(z + z^2/2 + z^3/3 \right)=\sum_{n \geq 0} \frac{a_n}{n!} z^n$, which corresponds to the number of permutations on $n$ letters that have only cycles of length $3$ or less (OEIS A057693). We employ Hayman’s method, explained in [1, Ch. 5.4], and follow the steps suggested in Exercise 8.

As noted in the hint from the book, by Theorem 3.15.2 (Schur), the function $f(z)=\exp\left(z + z^2/2 + z^3/3 \right)$ is admissible (also item (A), p. 184).

Our goal will then be to provide asymptotic approximations for $r_n^{-n}$, $f(r_n)$, and $b(r_n)$ and ultimately apply this theorem.

Formula for $1/r_n^n$

Initially, for our case, the functions $a(r)$ and $b(r)$ correspond to

\[\begin{align*} a(r) &=r\frac{f'(r)}{f(r)}\\ &=r\frac{(1+r+r^2)\exp\left(r+\frac{r^2}{2}+\frac{r^3}{3}\right)}{\exp\left(r+\frac{r^2}{2}+\frac{r^3}{3}\right)}\\ &=r^3+r^2+r,\\[5mm] b(r) &=ra'(r)\\ &=r\left(3r^2+2r+1\right)\\ &=3r^3+2r^2+r. \end{align*}\]

The solutions of $a(r_n)=n$ satisfy

\[\begin{align} r_n^3+r_n^2+r_n-n=0. \label{eq:arn} \end{align}\]

Let $p(r_n)=a(r_n)-n=r_n^3+r_n^2+r_n-n$. The discriminant of $p$ is equal to \(\Delta_p=-(27n^2+14n+3)<0\) for all $n\in\mathbb{N}$, so there exists only one real root. Explicitly, it is given by

\[\begin{align*} r_n=\frac{\sqrt[3]{3 \sqrt{3} \sqrt{27 n^2+14 n+3}+27 n+7}}{3 \sqrt[3]{2}}-\frac{2 \sqrt[3]{2}}{3 \sqrt[3]{3 \sqrt{3} \sqrt{27 n^2+14 n+3}+27 n+7}}-\frac{1}{3}. \end{align*}\]

It can be verified that $r_n>0$ for $n\geq 1$. Finding an asymptotic formula for $r_n$ directly may prove to be a tedious task, so in the book it is suggested to introduce the change of variables $u=r_n^{-1}$ and $t=n^{-1/3}$ in equation \eqref{eq:arn}. Then

\[\begin{align*} u^{-3}+u^{-2}+u^{-1}&=n\\ 1+u+u^2&=u^3n\\ u^3&=\frac{1+u+u^2}{n}\\ u&=\frac{(1+u+u^2)^{1/3}}{n^{1/3}}\\ u&=t\phi(u), \end{align*}\]

where $\phi(t)=(1+t+t^2)^{1/3}$. By the Lagrange inversion formula, for $m\geq1$,

\[\begin{align*} [t^m]u(t) &=\frac{1}{m}[t^{m-1}]\phi^m(t)\\ &=\frac{1}{m}[t^{m-1}](1+t+t^2)^{m/3}\\ &=\frac{1}{m}[t^{m-1}]\sum_{l\geq0}\binom{m/3}{l}(t+t^2)^l\\ &=\frac{1}{m}[t^{m-1}]\sum_{l\geq0}\binom{m/3}{l}t^l(1+t)^l\\ &=\frac{1}{m}[t^{m-1}]\sum_{l\geq0}\sum_{j=0}^l\binom{m/3}{l}\binom{l}{j}t^{l+j}. \end{align*}\]

Taking $j=m-l-1$ in the last equality,

\[\begin{align*} [t^m]u(t) &=\frac{1}{m}\sum_{l\geq0}\binom{m/3}{l}\binom{l}{m-l-1}. \end{align*}\]

The first values of this last sequence are $1,\frac{1}{3},\frac{1}{3},\frac{8}{81},\frac{19}{243},0,\frac{41}{6561},\ldots$. Thus,

\[\begin{align} u&=t+\frac{1}{3}t^2+\frac{1}{3}t^3+\frac{8}{81}t^4+\frac{19}{243}t^5+\cdots, \nonumber\\ \frac{1}{r_n}&=\frac{1}{n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{1}{3n}+\frac{8}{81n^{4/3}}+\frac{19}{243n^{5/3}}+\cdots. \label{1/rn-nt} \end{align}\]

We will first compute an asymptotic formula for $r_n^{-n}$. It is possible to truncate the formula \eqref{1/rn-nt} up to the fourth summand and still obtain a correct approximation for $r_n^{-n}$. We will notice that, when expanding this formula, the terms that are $o(n^{-5/3})$ become irrelevant.

\[\begin{align} \frac{1}{r_n} &=\frac{1}{n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{1}{3n}+\frac{8}{81n^{4/3}}+O(n^{-5/3}) \label{1/rn-t1}\\ &=n^{-1/3}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}+O(n^{-4/3})\right). \label{1/rn-t2} \end{align}\]

Using formula \eqref{1/rn-t2}, the following expansion for $r_n^{-n}$ is obtained.

\[\begin{align*} \frac{1}{r_n^n} &=n^{-n/3}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}+O(n^{-4/3})\right)^n\\ &=n^{-n/3}\exp\left(n\ln\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}+O(n^{-4/3})\right)\right). \end{align*}\]

We use the series $\ln(1+z)=\sum_{n\geq0}\frac{(-1)^{n+1}}{n}z^n$ to expand the last expression.

\[\begin{align*} \frac{1}{r_n^n} &=n^{-n/3}\exp\left[ n\left(\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)-\frac{1}{2}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^2\right.\right.\\ &\quad\left.\left.+\frac{1}{3}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^3+O(n^{-4/3})\right)\right]\\ &=n^{-n/3}\exp\left[ n\left(\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)-\frac{1}{2}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^2\right.\right.\\ &\quad\left.\left.+\frac{1}{3}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^3\right)+O(n^{-1/3})\right]. \end{align*}\]

The reason for truncating the expansion \eqref{1/rn-t1} was to ensure that, in the last expression, we could neglect terms that are $o(n^{-1})$. Thus,

\[\begin{align} \frac{1}{r_n^n} &\sim n^{-n/3}\exp\left[ n\left(\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)-\frac{1}{2}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^2\right.\right.\nonumber\\ &\quad\left.\left.+\frac{1}{3}\left(1+\frac{1}{3n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{8}{81n}\right)^3\right)\right]\nonumber\\ &= n^{-n/3}\exp\left(\frac{n^{2/3}}{3}+\frac{5}{18}n^{1/3}+O(n^{-1/3})\right)\nonumber\\ &\sim n^{-n/3}\exp\left(\frac{n^{2/3}}{3}+\frac{5}{18}n^{1/3}\right). \label{1/rn^n} \end{align}\]

Formulas for $f(r_n)$ and $b(r_n)$

Now we will find an asymptotic expansion for $f(r_n)=\exp\left(r_n+\frac{r_n^2}{2}+\frac{r_n^3}{3}\right)$. Using formula \eqref{eq:arn}, it is possible to eliminate the cubic term,

\[\begin{align} f(r_n) &=\exp\left(r_n+\frac{r_n^2}{2}+\frac{1}{3}\left(n-r_n^2-r_n\right)\right)\nonumber\\ &=\exp\left(\frac{n}{3}+\frac{2}{3}r_n+\frac{r_n^2}{6}\right).\label{frn-ne} \end{align}\]

The division algorithm can be applied to the expression \eqref{1/rn-t1} to find asymptotic expressions for $r_n=\left(\frac{1}{r_n}\right)^{-1}$ and $r_n^2=\left(\frac{1}{r_n}\right)^{-2}$.

\[\begin{align} r_n &=\left(\frac{1}{n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{1}{3n}+\frac{8}{81n^{4/3}}+O(n^{-5/3})\right)^{-1}\nonumber\\ &=n^{1/3}-\frac{1}{3}+O(n^{-1/3}),\label{eq:rn^1}\\ r_n^2 &=\left(\frac{1}{n^{1/3}}+\frac{1}{3n^{2/3}}+\frac{1}{3n}+\frac{8}{81n^{4/3}}+O(n^{-5/3})\right)^{-2}\nonumber\\ &=n^{2/3}-\frac{2}{3}n^{1/3}-\frac{1}{3}+O(n^{-1/3}).\label{eq:rn^2} \end{align}\]

Substituting expressions \eqref{eq:rn^1} and \eqref{eq:rn^2} into \eqref{frn-ne}, we obtain¹

\[\begin{align} f(r_n) &\sim\exp\left(\frac{n}{3}+\frac{2}{3}\left(n^{1/3}-\frac{1}{3}\right)+\frac{1}{6}\left(n^{2/3}-\frac{2}{3}n^{1/3}-\frac{1}{3}\right)\right)\nonumber\\ &=\exp\left(\frac{5}{9}n^{1/3}+\frac{n^{2/3}}{6}+\frac{1}{3}n-\frac{5}{18}\right).\label{eq:f(rn)} \end{align}\]

From formula \eqref{eq:rn^1}, an asymptotic expression for $b(r_n)$ can be easily derived,

\[\begin{align} b(r_n) &=3r_n^3+2r_n^2+r_n\nonumber\\ &\sim 3r_n^3\nonumber\\ &=3\left(n^{1/3}-\frac{1}{3}+O(n^{-1/3})\right)^3\nonumber\\ &\sim3\left(n^{1/3}\right)^3\nonumber\\ &=3n. \label{eq:b(rn)} \end{align}\]

Conclusion

Introducing the expansions \eqref{1/rn^n}, \eqref{eq:f(rn)}, and \eqref{eq:b(rn)} into the formula from Hayman’s method, we obtain an asymptotic expansion for the counting sequence $ a_n $.

\[\begin{align*} \frac{a_n}{n!} &\sim \frac{f(r_n)}{r_n^n\sqrt{2\pi b(r_n)}}\\ &=n^{-n/3}\exp\left(\frac{n^{2/3}}{3}+\frac{5}{18}n^{1/3}\right)\exp\left(\frac{5}{9}n^{1/3}+\frac{n^{2/3}}{6}+\frac{1}{3}n-\frac{5}{18}\right)\frac{1}{\sqrt{2\pi\cdot3n}}\\ &=\frac{n^{-n/3}}{\sqrt{3}\sqrt{2\pi n}}\exp\left(\frac{5}{6}n^{1/3}+\frac{1}{2}n^{2/3}+\frac{1}{3}n-\frac{5}{18}\right). \end{align*}\]

Finally, multiplying both sides by $ n! $ and applying Stirling’s formula, we get

\[\begin{align} a_n &\sim \frac{n^{-n/3}}{\sqrt{3}\sqrt{2\pi n}}\exp\left(\frac{5}{6}n^{1/3}+\frac{1}{2}n^{2/3}+\frac{1}{3}n-\frac{5}{18}\right)\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\nonumber\\ &=\frac{n^{2n/3}}{\sqrt{3}}\exp\left(\frac{5}{6}n^{1/3}+\frac{1}{2}n^{2/3}-\frac{2}{3}n-\frac{5}{18}\right). \end{align}\]

References

1. Wilf, H. S. (2005). generatingfunctionology (3rd ed.). AK Peters/CRC. https://doi.org/10.1201/b10576