I think this is a natural question but am not sure where to find resources.
Consider the possible multisets arising from choosing $n$ times an item from one of $k$ categories. We can represent one such multiset by a vector $\vec{x} = (x_1,\dots,x_k)$ with $\sum_i x_i = n$.
Question. I would like to upper-bound the quantity
$$ \sum_\vec{x} \frac{n!}{x_1! \cdots x_k!} x_1^{x_1} \cdots x_k^{x_k} $$
This is equivalent to
$$ k^n \mathbb{E} \left[ x_1^{x_1} \cdots x_k^{x_k} \right] $$
where the expectation is over $\vec{x}$ as the outcome of a uniform multinomial distribution ($n$ draws and $k$ equally likely categories). I'd rather not assume that either $k$ or $n$ is large with respect to the other (or assume both; both cases are interesting).
My approaches so far.
If we are sloppy about how many $x_i$ are nonzero (for instance if $n \gg k$) then we expect most cases have all $x_i > 1$, and we can use Stirling's approximation for all of the factorials. (If this is not the case, we have to be more careful and talk about only the nonzero $x_i$, so the below is not correct as stated, but hopefully can be modified.) We get that our sum is \begin{align} &\approx \sum_{\vec{x}} \frac{\left(\frac{n}{e}\right)^n \sqrt{2\pi n}}{\left(\frac{x_1}{e}\right)^{x_1} \cdots \left(\frac{x_k}{e}\right)^{x_k} \sqrt{\left(2\pi x_1\right)\cdots\left(2\pi x_k\right)}} x_1^{x_1} \cdots x_k^{x_k} \\ &= \frac{n^n}{(2\pi)^{(k-1)/2}} \sum_{\vec{x}} \frac{1}{\sqrt{x_1 \cdots x_k}} \end{align}
Perhaps this sum can be approximated by an integral or volume of some sort? (Again, it is over all vectors $\vec{x}$ consisting of natural numbers and summing to $n$.) But I'm not sure how to do so, it got messy fast for me.
Another thought I had is to say that "most" vectors $\vec{x}$ have each $x_i \approx \Theta\left(\frac{n}{k}\right)$ (again being careful about regimes where many $x_i = 0$), and go from there. But I couldn't bound the contributions from the "tail" well.
