Tight upper bound for the following expression

Question

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?

Answer 1

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$$