2
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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! $\endgroup$
    – Tony419
    May 21, 2022 at 21:40
  • $\begingroup$ 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. $\endgroup$
    – Henry
    May 21, 2022 at 21:46
  • $\begingroup$ 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. $\endgroup$
    – Henry
    May 21, 2022 at 21:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .