Upper bound for $\frac{2^n}{n!} \sum_{m=1}^n \frac{\#\{\text{surjections } [n] \to [m]\}}{m}$

77 Views Asked by At

In connection with this question, I would like to do some estimates using the Baker-Campbell-Hausdorff formula.

Let us define

$$a_n= \frac{2^n}{n!} \sum_{m=1}^n \frac{ \mathrm{Surj}(n,m)}{m}$$

where $\mathrm{Surj}(n,m)$ denotes the number of surjective maps from an $n$-element set to an $m$-element set. If one prefers, one may use $\mathrm{Surj}(n,m)=m! S(n,m)$, where $S(n,m)$ denotes the Stirling number of the second kind (i.e. the number of partitions of an $n$-element set into $m$ nonempty parts).

Question: What kind of upper bounds for $a_n$ can we come up with? Can we prove that the power series $\sum_{n=1}^\infty a_n x^n$ has a positive radius of convergence?

1

There are 1 best solutions below

4
On BEST ANSWER

Let us see... as correctly stated by the OP, $\text{Surj}(n,m)=m!{n\brace m}=\sum_{j=0}^{m}(-1)^{m-j}\binom{m}{j}j^n$, hence:

$$ a_n = \frac{2^n}{n!}\sum_{m=1}^{n}\Gamma(m){n\brace m}=\frac{2^n}{n!}\int_{0}^{+\infty}\sum_{m=1}^{n}\lambda^m{n \brace m}\frac{d\lambda}{\lambda e^{\lambda}}$$ equals: $$ a_n=\frac{2^n}{n!}\int_{0}^{+\infty}\mathbb{E}[X_{\mu=\lambda}^n]\frac{d\lambda}{\lambda e^{\lambda}}=\frac{2^n}{n!}\int_{0}^{+\infty}\sum_{k\geq 0}\frac{\lambda^k e^{-\lambda}k^n}{k!}\cdot\frac{d\lambda}{\lambda e^{\lambda}}\,d\lambda $$ where $X_{\mu=\lambda}$ is a Poisson random variable with expected value $\lambda$. By switching $\int$ and $\sum$ we get:

$$ a_n = \frac{2^n}{n!}\sum_{k\geq 0}\frac{k^{n-1}}{2^k}\approx\frac{2^n}{n!}\int_{0}^{+\infty}k^{n-1}2^{-k}\,dk=\frac{1}{n}\left(\frac{2}{\log 2}\right)^n $$ hence the radius of convergence of $\sum_{n\geq 0}a_n x^n$ is positive but finite, around $\frac{\log 2}{2}\approx \frac{1}{3}$.