I was wondering whether there is a closed form (or asymptotic expression) for the following binomial sum:
$$\sum_{m=0}^n \frac{1}{m^m} \binom{n}{m},$$
where we use the convention $0^0=1$. I feel like during my university studies we were taught a trick to solve problems like this by playing around with the binomial theorem, exponentials and sometimes calculus. However, nothing I've tried so far seems to work.
At the very least, a non-trivial upper bound would be handy.
Edit: Thanks all for the answers, they're very helpful and it's so fun to see all the different approaches
Best Answer
Another approach to large $n$ asymptotics.
Use the identity $$ m^{-m}=\frac 1{(m-1)!}\int_0^1(-\phi(x))^{m-1}dx,\qquad \phi(x):=x\log(x) $$ to rewrite $$ a(n):=\sum_{m=1}^n\binom nm m^{-m} = \int_0^1\sum_{m=1}^n\binom nm \frac{(-\phi(x))^{m-1}}{(m-1)!}dx. $$ It turns out that $$ \sum_{m=1}^n\binom nm \frac{(-t)^{m-1}}{(m-1)!}=L^{(1)}_{n-1}(t) $$ is a Laguerre polynomial. We have the following asymptotics for large $n$ (e.g., see the Wikipedia page about Laguerre polynomials) $$ L^{(1)}_{n-1}(-t)\sim\frac{n^{1/4}}{2\sqrt\pi\,t^{3/4}}\exp(-\frac t2+2\sqrt{tn}),\quad n\to+\infty,\ t>0. $$ Plug it into the expression for $a(n)$ $$ a(n)\sim \frac{n^{1/4}}{2\sqrt\pi}\int_0^1\frac{\exp(\phi(x)/2)}{(-\phi(x))^{3/4}}\exp(2\sqrt{-n\phi(x)})dx,\quad n\to+\infty. $$ Finally, this integral is amenable to Laplace's method, yielding $$ a(n)\sim\frac{n^{1/4}}{2\sqrt\pi}\frac{\exp(\phi(1/e)/2)}{(-\phi(1/e))^{3/4}}e^{2\sqrt{-n\phi(1/e)}}\sqrt{\frac{2\pi}{2\sqrt n \bigg|\frac{d^2\sqrt\phi}{dx^2}\big|_{x=1/e}\bigg|}},\quad n\to+\infty, $$ and so, after some algebra, $$ \boxed{a(n)\sim\frac 1{\sqrt 2}e^{2\sqrt {\frac ne}-\frac{1}{2 e}},\quad n\to+\infty } $$
(There are a few details missing to get a complete proof, but the final asymptotics seems to be numerically correct.)