Asymptotics of $1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1$ Suppose $n\in\mathbb{Z}$ and $n > 0$.
Let $$H_n = 1^n + 2^{n-1} + 3^{n-2} +\cdots + (n-1)^2 + n^1.$$
I would like to find a Big O bound for $H_n$.  A Big $\Theta$ result would be even better.
 A: My approach is very much along the same line as that of leonbloy.
Let $f(k) = k^{n+1-k}$. Use Euler-Maclaurin formula:
$$
 \begin{eqnarray}
   \sum_{k=1}^n f(k) &=& \int_1^n f(x) \mathrm{d} x + \frac{1}{2} \left( f(1) + f(n) \right) + \sum_{m=1}^q \frac{B_{2m}}{(2m)!} \left( f^{(2m-1)}(n) - f^{(2m-1)}(1) \right) \\ 
   &&+  \frac{1}{(2q)!} \int_1^n B_{2q}(\{t\}) f^{(2q)}(t) \mathrm{d} t
  \end{eqnarray}
$$
Since $f(1) = 1$ and $f(n)=n$. Asymptotically,  $f^{(2m-1)}(1) \sim -n \cdot \log^{2m-1}(n)$ and $f^{(2m-1)}(n) \sim n^{2m-1}$.
Thus the main term comes from the integral. Let $x=1+(n-1)t$.
$$
   \int_1^n x^{n+1-x} \mathrm{d} x = (n-1) \int_0^1 \left( 1 + (n-1) t \right)^{t+n(1-t)} \,\, \mathrm{d} t
$$
The integrand is sharp-peaked with peak location at 
$$
    t_0 = \frac{1}{n-1} \left( \frac{n+1}{W((n+1) \, \mathrm{e})} -1 \right)
$$
Logarithm of the integrand, expanded in the vicinity of $t_0$:
$$
  \left( n + t - n t \right) \log\left(1 + (n-1) t \right) = (n+1) \left( w_n + \frac{1}{w_n} - 2 \right) - \frac{\sigma_n}{2} ( t-t_0)^2 + o((t-t_0)^2)
$$
where $w_n = W((n+1)\mathrm{e})$ and $\sigma_n = \frac{(n-1)^2 w_n ( w_n + 1)}{n+1}$.
Thus 
$$
    \sum_{k=1}^n k^{n+1-k} \sim  \exp\left( (n+1) \left( w_n + \frac{1}{w_n} - 2 \right) \right) \sqrt{\frac{2\pi (n+1)}{w_n (1+w_n)}}
$$
Here is the numerical simulation, showing the agreement on logarithmic scale:

A: Another idea, aproximating to an integral and using Laplace
$$H_n=\sum_{k=1}^{n} k^{n+1-k} \approx \int_1^n x^{n+1-x} dx$$
Let $m=n+1$:
$$\int x^{m-x} dx = \int e^{m g(x)} dx  \hspace{20px} , \hspace{20px} g(x)=\left(1- \frac{x}{m}\right)\log(x)$$
The global maximum of $g(x)$ is attained (after some manipulation) at $$x_0(m)=\frac{m}{W( e \; m)} \approx \frac{m}{1+ \log m - \log (1 +\log m)}$$
where $W(\cdot)$ is the Lambert function (the last asymptotic approximation is to get an idea of the order, but it can/should be refined see here - all asymptotics are tricky here.)
Now, we approximate the integral by Laplace method:
$$I(m) \approx e^{m g(x_0)} \sqrt{\frac{2 \pi}{m |g''(x_0)|}}=x_0^{m+1-x_0} \sqrt{\frac{2 \pi}{m+x_0}}$$
Or
$$\log H_n \approx (n+2-x_0) \log(x_0) + \frac{1}{2}\log{\frac{2 \pi}{n+1+x_0}}$$
with
$x_0 = (n+1) /W(e \; (n+1))$ 
Some Maxima code
g(x,M):=(1-x/M)*log(x);
define(g1(x,M) , diff(g(x,M),x)); 
define(g2(x,M) , diff(g(x,M),x,2));
h1(M):=M/lambert_w(M * %e); 
s(M):=sum(k^(M-k), k,1, M-1);
ap1(M):= h1(M)^(M+1-h1(M)) * sqrt(2*%pi/(M+h1(M)));
ap1l(N) := (N+2-h1(N+1)) * log(h1(N+1));
ap2l(N) := ap1l(N) + log(2*%pi/(N+1+h1(N+1)))/2;

This approach might be specially useful to compute numerically the sum for large values of $N$. For example, some values of $log(H_n)$
     n             exact                 approx
    30           49.72538546           49.72496938
   100          246.40058178          246.40036689 
  1000         4271.07746405         4271.07742927

A: A rather trivial bound is
$$H_n=\sum _{k=1}^n k^{-k+n+1}\leq\sum _{k=1}^n n^{-k+n+1}=\frac{n \left(n^n-1\right)}{n-1}$$
However, I did not find a tight bound. Also for the interested ones, this sequence is known to OEIS.
A: Here is a simple idea which might or might not lead somewhere.
Note that $(k+1)^{n-k-1} \geq k^{n-k}$ if and only if 
$$\left( 1+\frac{1}{k}\right)^{n-k-1} \geq k \,.$$
For $k \leq \sqrt{n-1}$, by Bernoulli
$$\left( 1+\frac{1}{k}\right)^{n-k-1} \geq 1+\frac{n-k-1}{k} =\frac{n-1}{k} \geq k \,.$$
Thus we get the following result:
Lemma: The sequence $k^{n-k}$ is increasing for all $k \leq \sqrt{n-1}$. 
Now, if $k > \sqrt{n-1}$, and $n$ large, we have the following approximation:
$$\left( 1+\frac{1}{k}\right)^{n-k-1} = \left[ \left( 1+\frac{1}{k} \right)^k \right]^{\frac{n-k-1}{k}} \sim e^{\frac{n-k-1}{k}}= e^{\frac{n-1}{k}-1} $$
The inequality $e^{\frac{n-1}{k}-1} < k$ is true for all $k > k_0(n)$. Unfortunatelly I cannot figure a good estimate for $k_0(n)$, rough estimates should be easy to get. 
Anyhow, this shows that for sure $k^{n-k}$ in creases up to $k=\sqrt{n-1}$ and decrease for all $k \geq k_0(n)$. A good calculation of $k_0$ should lead to a decent but not very good estimate. 
A: Let $0<a<b<1$. For every $an\leqslant k\leqslant bn$, $k^{-k+n+1}\geqslant(an)^{(1-b)n}$ hence $H_n\geqslant(b-a)n(an)^{(1-b)n}$. Thus $\log (H_n)\geqslant (1-b)n\log(n)+(1-b)n\log(a)+\log(b-a)$, which proves that 
$$
\liminf\limits_{n\to\infty}\log(H_n)/(n\log(n))\geqslant1-b.
$$
On the other hand, 
$$
H_{n+1}=n+1+\sum\limits_{k=1}^nk^{n+2-k}\leqslant n+1+n\sum\limits_{k=1}^nk^{n+1-k}=n+1+nH_n.
$$
Hence, as @J.J. noted in a comment, if $H_n<n!$ then $$H_{n+1}<n+1+n\cdot n!\leqslant(n+1)!$$ if $n+1\leqslant n!$, that is, if $n\geqslant3$. Since $H_3=8>3!$ but $H_4=22<4!$, this proves that $H_n<n!$ for every $n\geqslant4$.
Thus,
$$
\color{red}{\lim\limits_{n\to\infty}\log(H_n)/(n\log n)=1},
$$
which may be rewritten as $H_n=n^{n+o(n)}$.
To go further, rewrite the inequality between $H_n$ and $H_{n+1}$ written above as
$$
\frac{H_{n+1}}{n!}\leqslant\frac{n+1}{n!}+\frac{H_n}{(n-1)!},
$$
which, since $H_1=1$, shows that $H_{n}<(2\mathrm e)(n-1)!$ for every $n\geqslant1$. 
Be aware though, that this is not the end of the story yet since, for every positive integer $k$, there exists a finite constant $c_k$ such that $H_n<c_k(n-k)!$ for every $n\geqslant k$... hence 
$$
\color{blue}{H_n=n^{n-\alpha(n)}},
$$ 
with $\alpha(n)\to+\infty$ and $\alpha(n)/n\to0$ when $n\to\infty$.
