This is the integer sequences A006933, describing Sloane's Eban numbers, $2, 4, 6, 30, 32, 34, 36, 40, 42, 44, 46, 50, 52, 54, 56, 60, 62, 64, 66, 2000, 2002, 2004, 2006$, $2030, 2032, 2034, 2036, 2040, 2042, 2044, 2046, 2050, 2052, 2054, 2056, 2060, 2062, 2064$, $2066, 4000, 4002, 4004, 4006, 4030, 4032, 4034, 4036, 4040, 4042, 4044, 4046, 4050, ...$
More information is here.
Here we show the main term $\frac{2}{\sqrt{\pi}}\frac{1}{\sqrt{66k}}$ in OPs asymptotic expansion is correct using the saddle-point method.
The coefficients in the expansion of the polynomials
\begin{align*}
\left(\frac{1-z^{10}}{1-z}\right)^{k}=\left(1+z+z^2+z^3+z^4+z^5+z^6+z^7+z^8+z^9\right)^{k}\tag{1}
\end{align*}
form a unimodal sequence. Taking even values $2k$ the maximum is the coefficient of the middle term
\begin{align*}
[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\qquad k\geq 0\tag{2}
\end{align*}
The coefficients in (2) form a sequence starting with $(1,10,670, 55\,252,4\,816\,030,\ldots)$. These numbers are called Lucky ticket numbers and are stored in OEIS. In fact they are the even central decanomial coefficients which are the largest coefficients in the expansion of (1).
They also cite an asymptotic formula for the largest coefficient of $\left(1+z+\cdots+z^q\right)^k$ which gives in the case (2)
\begin{align*}
\color{blue}{[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\sim 10^{2k}\frac{1}{\sqrt{33\pi k}}}\tag{3}
\end{align*}
corresponding to OPs main term in his expansion ($k$ even).
We can prove the asymptotic expansion (3) using the saddle-point method. In order to do so we closely follow section VIII.8 Large Powers in Analytic Combinatorics by P. Flajolet and R. Sedgewick. We also give a little bit of surrounding information to ease readability.
VIII.8 Large powers:
- (p. 585): The extraction of coefficients in powers of a fixed function and more generally in functions of the form $A(z)B(z)^k$ constitutes a prototypical and easy application of the saddle-point method. We will accordingly be concerned here with the problem of estimating
\begin{align*}
[z^K]A(z)\cdot B(z)^k=\frac{1}{2\pi i}\oint A(z)B(z)^k\frac{dz}{z^{K+1}}
\end{align*}
as both $k$ and $K$ get large.
In our situation (3) we have $A(z)=1$ and $B(z)=\left(1+z+z^2+\cdots+z^9\right)^2$ with $K=9k$. What follows are conditions which need to be fulfilled by $A(z)$ and $B(z)$ in order to apply the saddle-point method.
VIII. 8.1. Large powers: saddle-point bounds: We consider throughout this section two fixed functions, $A(z)$ and $B(z)$ satisfying the following conditions.
L1: The functions $A(z)=\sum_{j\geq 0}a_jz^j$ and $B(z)=\sum_{j\geq 0}a_jz^j$ are analytic at $0$ and have non-negative coefficients; furthermore it is assumed (without loss of generality) that $B(0) \ne 0$.
L2: The function $B(z)$ is aperiodic in the sense that $\gcd\{j|b_j>0\}=1$. (Thus $B(z)$ is not a function of the form $\beta(z^p)$ for some integer $p\geq 2$ and some $\beta$ analytic at $0$.)
L3: Let $R\leq \infty$ be the radius of convergence of $B(z)$; the radius of convergence of $A(z)$ is at least as large as $R$.
We observe conditions L1 to L3 are fulfilled for $A(z)=1$ and $B(z)=\left(1+z+z^2+\cdots+z^9\right)^2$ with radius of convergence $R=\infty$. In the following we need the quantity $T$ called spread which is defined as
\begin{align*}
\color{blue}{T}&:=\lim_{z\to R^{-}}\frac{zB^{\prime}(z)}{B(z)}\\
&=\lim_{z\to \infty}\frac{2z\left(1+z+\cdots+z^9\right)\left(1+2z+\cdots+9z^8\right)}{\left(1+z+\cdots+z^9\right)^2}\\
&=\lim_{z\to\infty}\frac{2z\left(1+2z+\cdots+9z^8\right)}{1+z+\cdots+z^9}\\
&\,\,\color{blue}{=18}
\end{align*}
The purpose is to analyse the coefficients
\begin{align*}
[z^K]A(z)\cdot B(z)^k
\end{align*}
when $K$ and $k$ are linearly related. In order to do so the condition $K<Tk$ will be imposed which is inherent in the nature of the problem. Note that in our case we have $K=9k$ and with $T=18$ the condition $K<Tk$ evaluates to $9k<18k$ which is valid.
We also need a quantity $\zeta$ which is introduced in Proposition VIII.7 and since this is a useful and easily derived upper bound for the coefficients we note
Proposition VIII.7 (Saddle-point bounds for large powers):
- Consider functions $A(z)$ and $B(z)$ satisfying the conditions L1,L2,L3 above. Let $\lambda$ be a positive number with $0<\lambda <T$ and let $\zeta$ be the unique positive root of the equation
\begin{align*}
\zeta\frac{B^{\prime}{(\zeta)}}{B(\zeta)}=\lambda \tag{4}
\end{align*}
Then, for $K=\lambda k$ an integer; one has
\begin{align*}
[z^K]A(z)\cdot B(z)^k\leq A(\zeta)B(\zeta)^k\zeta^{-K}\tag{5}
\end{align*}
We start with calculating the roots of (4). We set $\lambda =9$ and obtain according to (4)
\begin{align*}
z\frac{B^{\prime}(z)}{B(z)}&=9\\
\end{align*}
which gives with $B(z)=\left(1+z+\cdots+z^9\right)^2$:
\begin{align*}
\color{blue}{9z^9+7z^8+5z^7+3z^6+z^5-z^4-3z^3-5z^2-7z-9=0}
\end{align*}
from which we easily derive the positive root $\color{blue}{\zeta =1}$.
We find as upper bound according to (5)
\begin{align*}
[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}\leq \left(\sum_{k=0}^91\right)^{2k}\cdot 1^{-9k}=10^{2k}
\end{align*}
This upper bound isn't really sharp but it may be useful whenever only rough order of magnitude estimates are sought.
Now we are well prepared for the main theorem.
Theorem VIII.8 (Saddle-point estimates of large powers).
Under the conditions of Proposition VIII.7, with $\lambda = K/k$, one has
\begin{align*}
\color{blue}{[z^K]A(z)\cdot B(z)^k=A(\zeta)\frac{B(\zeta)^k}{\zeta^{K+1}\sqrt{2\pi n \xi}}\left(1+o(1)\right)}\tag{6}
\end{align*}
where $\zeta$ is the unique root of $\zeta B^{\prime}(\zeta)B(\zeta)=\lambda$ and
\begin{align*}
\xi=\frac{d^2}{d\zeta^2}\left(\log B(\zeta)-\lambda\log \zeta\right).\tag{7}
\end{align*}
- In addition, a full expansion in descending powers of $k$ exists.
These estimates hold uniformly for $\lambda$ in any compact interval of $(0,T)$, i.e., any interval $[\lambda^{\prime},\lambda^{\prime\prime}]$
with $0<\lambda^{\prime}<\lambda^{\prime\prime}<T$, where $T$ is the spread.
Now it's time to harvest. At first we calculate $\xi$ according to (7). We obtain with $B(z)=\left(1+z+\cdots+z^9\right)^{2}$ and $\lambda=9$:
\begin{align*}
\color{blue}{\xi}&=\left.\left(\frac{d^2}{dz^2}\left(\log (B(z)-9\log z\right)\right)\right|_{z=1}\\
&=\left.\left(\frac{d}{dz}\left(\frac{B^{\prime}(z)}{B(z)}-\frac{9}{z}\right)\right)\right|_{z=1}\\
&=\frac{B^{\prime\prime}(1)}{B(1)}-\left(\frac{B^{\prime}(1)}{B(1)}\right)^2+9\\
&=\frac{177}{2}-81+9\\
&\,\,\color{blue}{=\frac{33}{2}}\tag{8}
\end{align*}
Putting all together into (6) we finally obtain with $B(\zeta)=B(1)=\left.\left(1+z+\cdots+z^9\right)^{2k}\right|_{z=1}=10^{2k}$:
\begin{align*}
\color{blue}{[z^{9k}]\left(\frac{1-z^{10}}{1-z}\right)^{2k}}
&=\frac{10^{2k}}{1^{9k+1}\sqrt{2\pi k \frac{33}{2}}}(1+o(1))\\
&\,\,\color{blue}{=10^{2k}\frac{1}{\sqrt{33\pi k}}(1+o(1))}
\end{align*}
in accordance with the claim (3).
Note: We have according to theorem VIII.8 the possibility to calculate a full expansion in descending powers of $k$. We can also study asymptotic expansions of $[z^K]B(z)^{k}$ for other quantities of $K$ as long as we fulfill the spread condition $K<Tk$.
Best Answer
The limiting ratio is not hard to derive via the method of moments.
In a random permutation $\sigma$ of $\{1,2,\dots,n\}$ (not necessarily a derangement), let $X_n$ be
We'll show that for any fixed $k$, we have $\lim_{n \to \infty} \mathbb E[\binom{X_n}{k}] = \frac{3^k}{k!}.$ If a random variable $X$ is Poisson with mean $3$, we also have $\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$. The Poisson distribution is determined by its moments, so it follows that $X_n$ converges in distribution to $X$, and in particular $\lim_{n \to \infty} \Pr[X_n = 0] = e^{-3}$.
To see this, note that $X_n$ is the sum of $3n-2$ indicator variables corresponding to each of the events (listed above) that $X_n$ counts, so $\binom{X_n}{k}$ counts the number of size-$k$ sets of events that occur. The calculation is difficult to do exactly but more or less straightforward asymptotically. Out of the $\binom{3n-2}{k}$ choices of $k$ events, $(1-o(1))\binom{3n-2}{k}$ never involve the same value $\sigma(i)$ more than once, so the probability that they occur is $(1+o(1))n^{-k}$. These contribute $(1+o(1))\frac{3^k}{k!}$ to the expected value $\mathbb E[\binom{X}{k}]$, which is all that we wanted.
So it remains to reassure ourselves that the contribution from all other choices of $k$ events is insignificant in the limit. Muddying the picture, some groups of $j \le k$ events that overlap have a significantly higher probability than a group of $j$ nonoverlapping events. For example, the events that $\sigma(3)=3$, that $\sigma(4)=4$, and that $\sigma(4)=\sigma(3)+1$ have this property.
However, we can never win this way, because there are $O(n)$ ways to pick that a group of $j$ overlapping events (with a constant factor depending on $k$) but a $O(n^{-2})$ chance that all of the events occur (since at least two values of $\sigma$ are involved). So for any possible overlapping structure, the contribution to $\mathbb E[\binom{X}{k}]$ is $O(n^{-1})$, and there is a constant number (depending only on $k$) of overlapping structures.
As a result, we can ignore all overlaps, conclude that $\lim_{n\to\infty}\mathbb E[\binom{X}{k}] = \frac{3^k}{k!}$, and deduce that $\lim_{n\to\infty} \Pr[X_n = 0] = e^{-3}$. Therefore $$\lim_{n\to\infty} \Pr[X_n = 0 \mid \text{$\sigma$ is a derangement}] = \lim_{n\to\infty} \frac{\Pr[X_n=0]}{\Pr[\text{$\sigma$ is a derangement}]} = \frac{e^{-3}}{e^{-1}} = e^{-2}.$$