# Upper bound for a certain sum involving multinomial coefficients

It is clear that

$$\sum_{\vert \alpha \vert=k}\frac{k!}{\alpha!}=n^k,$$

where $$k$$ is a given positive integer and $$\alpha\in \mathbb{N}^{n}$$ such that $$\alpha=(a_1, \dots, \alpha_n)$$, $$\vert \alpha \vert=\sum_{i=1}^{n}\alpha_i$$ and $$\alpha! = \alpha_1! \alpha_2! \cdots \alpha_n!$$.

I would like to get an upper bound for the variant of the above sum with the additional restriction that $$\alpha_i\ge 1$$ for each $$i$$. I think I saw somewhere an estimate

$$\sum_{\vert \alpha \vert=k, \alpha_i\ge 1}\frac{k!}{\alpha!}\le \frac{n^k}{n!}.$$

Is the above estimate true and if so, could you help me prove it?

Your $$\sum\limits_{\vert \alpha \vert=k}\frac{k!}{\alpha!}=n^k$$ is counting the number of was of putting $$k$$ labelled balls into $$n$$ labelled boxes. $$\alpha_i$$ is the number of balls in the $$i$$th box.
I think your $$\sum\limits_{\vert \alpha \vert=k, \alpha_i\ge 1}\frac{k!}{\alpha!} =n!\, S_2(k,n)$$ using Stirling numbers of the second kind, since you are counting the number of ways of putting $$k$$ labelled balls into $$n$$ labelled boxes so each box has at least one ball.
Let's take an easy counter-example to your conjecture where $$n=k=3$$: here $$\sum\limits_{\vert \alpha \vert=k, \alpha_i\ge 1}\frac{k!}{\alpha!} = \frac{3!}{1!1!1!}=6$$ while $$\frac{n^k}{n!} = \frac{3^3}{3!}=4.5$$ which is smaller.
• There was a typo in my conjectured bound, it should be $n^k$ in place of $k^n$ on the RHS. With that modification the bound seems true (at least asymptotically). One can prove it using the estimates for Stirling numbers (my sum seems to be simply equal to $S_2(n,k)$; no need for $n!$ in your formula, I think). Thanks for your help! May 21, 2022 at 21:40
• The counter-example still works with the typo corrected. Since $S_2(3,3)=1$, I suspect I do need the $n!$ to get to $6$. Here $S_2(k,n)$ counts the number of ways of putting $k$ labelled balls into $n$ unlabelled boxes so each box has at least one ball and the $n!$ in effect labels the boxes. May 21, 2022 at 21:46
• I also think $\lim\limits_{k \to \infty} \left(\dfrac{\sum\limits_{\vert \alpha \vert=k, \alpha_i\ge 1}\frac{k!}{\alpha!}}{n^k}\right) =1$ for all $n$ since if the number of boxes is fixed then, as the number of balls increases, the vast majority of the original cases have a ball in every box. May 21, 2022 at 21:48