# Tight upper bound for the following expression

How does one go about upper bounding the following expression/what is the tightest upper bound one can achieve?

$$\prod_{i = 1}^k A_i!$$ such that $$\sum_{i}^k A_i \leq C$$.

What is the tighest upper bound for the first expression in terms of C and k?

Note that the trivial upper bound for this expression is $((\frac{C-k}{e})^C)^k$ but can we do better than this?

The Stirling approximation yields a good bound:

$$\prod_{i=1}^{k}A_i! \cong \prod_{i=1}^{k}\sqrt{2\pi A_i}\dot{} (\frac{A_i}{e})^{A_i}=\prod_{i=1}^{k}\sqrt{2\pi A_i}\prod_{i=1}^{k}(\frac{A_i}{e})^{A_i}$$ We can bound the first term on the right side by the known inequality: $$\prod_{i=1}^{k} A_i\leq (\frac 1 k \sum_{i}^k A_i)^k\implies\prod_{i=1}^{k}\sqrt{2\pi A_i}\leq(\frac{2\pi C}{k})^{k/2}$$

Now we shall bound the scound term using the fact $1\leq A_i\leq C-k$:

$$\prod_{i=1}^{k}(\frac{A_i}{e})^{A_i}=\exp[\sum_{i=1}^kA_i\log(\frac{A_i}{e})]\leq\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=(e^{(C-k)/e})^C$$ Combining the two we get: $$\prod_{i=1}^{k}A_i!\leq (\frac{2\pi C}{k})^{k/2}(e^{(C-k)/e})^C$$

• What I need is a tighter bound than that provided by Stirling's if there is such a bound. The problem with Stirling's approximation is that it asymptotically diverges from the expression given by the factorial. May 6, 2017 at 16:42
• Stirling does not diverge from the factorial. The limit of the Stirling approximation divided by the factorial is 1, and it converges very fast. May 6, 2017 at 18:22
• Be it as it my, there is some sense of inefficiency in my bound. Could you share the related problem? May 6, 2017 at 18:28
• Oh yes, you are correct. The bound doesn't diverge. Thanks for the answer. May 6, 2017 at 18:34
• How did you get the part $\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=e^{C-k-1}\dot{}C$? Isn't this supposed to be $\exp[\log(\frac {C-k} e) \sum_{i=1}^kA_i]=(\frac{C - k}{e})^C$? May 6, 2017 at 21:34