# Sum of multi-index factorials

Fix $$d\in\mathbb{N}\setminus\{0\}$$. For $$j\in\mathbb{N}\setminus\{0\}$$, let \begin{align*} [j] = \Big\{\alpha\in \mathbb{N}^d: \sum^d_{i=1}\alpha_i=j\Big\}. \end{align*} For $$\alpha\in[j]$$, define the multi-index factorial $$\alpha! =\prod_{i=1}^d (\alpha_i !)$$. What is a good bound for \begin{align*} \sum_{\alpha \in [j]} (\alpha !) \end{align*} in terms of $$j$$, when $$d$$ is fixed and $$j$$ is large?

• You'll get different answers depending on j bigger than d or d bigger than j. Do you know which you need? Gerhard "Answer Depends On The Both" Paseman, 2020.01.25. – Gerhard Paseman Jan 26 at 2:49
• Updated the question. Please consider fixed d while j is large. – Johann Bruckner Jan 26 at 3:04
• So I believe the argument in my post actually works when d^2 is less than j and gives an upper bound of (d-1)j(j!) on your sum when d is greater than 1. It would be nice to know for what pairs (d,j) we have that the subsums involving tuples with largest element (j-k) is greater than the subsum with tuples having largest element (j-k-1). Maybe you can find the general argument. Gerhard "Staying With Specialization For Now" Paseman, 2020.01.25. – Gerhard Paseman Jan 26 at 6:12

The logarithm of the sum in question is $$\sim j\ln j$$ if $$d=o(j)$$.

Indeed, assume that $$j\ge d$$ and, moreover, $$d=o(j)$$.

By Stirling's formula (see e.g. formula (26)), $$(2\pi n)^{1/2}(n/e)^n for integers $$n\ge0$$ (with $$0^0:=1$$).

Let $$S$$ denote the sum in question. Let $$a:=\alpha$$ and $$a_i:=\alpha_i$$.

Note that $$S\ge j!$$, whence, by (1),
$$\ln S\gtrsim j\ln j.\tag{2}$$

On the other hand, again by (1), the arithmetic-geometric-mean inequality, and the convexity of $$u\ln u$$ in $$u\ge0$$ (with $$0\ln0:=0$$), for any $$a\in[j]$$ $$a!<(2\pi)^{d/2}e^{-j}\prod_1^d(a_i+1)^{1/2}\exp\sum_1^d a_i\ln a_i \\ \le (j/d+1)^{d/2}\exp(j\ln j) =\exp(j\ln j+o(j\ln j)).$$ Also, the cardinality of $$[j]$$ is $$\le j^d=\exp o(j\ln j)$$ (actually, the cardinality of $$[j]$$ is $$\binom{j+d-1}{d-1}$$). So, $$\ln S\lesssim j\ln j. \tag{3}$$

Thus, by (2) and (3), $$\ln S\sim j\ln j,$$ as claimed.

Here is an approach that suggests (for $$d$$ smaller than $$j$$, say $$d^2$$ less than $$j$$) the sum is not larger than $$dj(j!)$$. Unfortunately, we are only bounding part of the sum by $$d(j/2 - d)(j!)$$. These are the parts which have an $$\alpha_i$$ term at least as large as $$(j/2+d+1)$$.

Note that there are $$d$$ terms whose product is $$j!$$: these are the $$d$$ tuples where all but one of the $$\alpha_i$$ are zero. Now let's set $$k=0$$, and look at a single tuple whose largest $$\alpha_i$$ is $$(j-k)$$. By replacing this $$\alpha_i$$ by $$(j-k-1)$$ and adding $$1$$ to one of the other $$d-1$$ places, we get $$d-1$$ distinct tuples whose largest term is $$(j-k-1)$$ and whose sum of (the products derived from each of) these $$d-1$$ tuples is at most $$(k+d-1)/(j-k)$$ times the single tuple, meaning the sum of all (products derived from) tuples with largest element $$(j-k-1)$$ is less than the sum of all (products derived from) tuples with largest element $$(j-k)$$. So when $$2k$$ is less than $$j+1-d$$, we get the sum of tuples with largest element $$(j-k)$$ is less than $$d(j!)$$. So we can bound a large part of the sum by $$(j+1-d)d(j!)/2$$. If we could extend this argument down to $$k=j/d$$, we would have the sum bounded above by $$(j-j/d)d(j!)$$.

Gerhard "Turning Multiplication Back Into Addition" Paseman, 2020.01.25.

• Actually, the sums may be bounded by a unimodal sequence which would lead to each subsum of terms derived from tuples with largest a_i being j-k is still less than d(j!). So I think we can establish a bound of dj(j!) even in the case d is near j in size. Gerhard "Ever Hopeful For A Proof" Paseman, 2020.01.25. – Gerhard Paseman Jan 26 at 5:53

Let us also show for each natural $$d$$ $$S_{d,j}\sim j!d \tag{1}$$ (as $$j\to\infty$$), where $$S_{d,j}$$ is the sum in question.

The key here is the recursion $$S_{d,j}=\sum_{b=0}^j b!S_{d-1,j-b} \tag{2}$$ for $$d=2,3,\dots$$ and $$j=0,1,\dots$$, with the initial conditions $$S_{d,0}=1$$ and $$S_{1,j}=j!$$. The latter initial condition obviously implies (1) for $$d=1$$.

Proceed by induction on $$d$$. Take any $$d=2,3,\dots$$ and $$j=0,1,\dots$$. Then, by (2) and induction, for any fixed natural $$B$$ $$S_{d,j}=\sum_{b=0}^j (j-b)!S_{d-1,b} \\ =j!S_{d-1,0}+(j-1)!S_{d-1,1}+S_{d-1,j}+S_{d-1,j-1} \\ +\sum_{b=2}^B (j-b)!S_{d-1,b} +\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b} \\ =j!+O((j-1)!)+(d-1+o(1))j!+O((j-1)!) \\ +O((j-2)!) +\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b} \\ =(d+o(1))j!+\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b}.$$ Let now $$B\ge1$$ be large enough so that $$S_{d-1,b}\le b!d$$ for all $$b>B$$; such $$B$$ exists by induction. Then, noting that $$(j-b)!b!$$ is log-convex in $$b\in\{0,\dots,B\}$$, we see that for $$j\ge3$$ $$\sum_{b=B+1}^{j-2} (j-b)!S_{d-1,b}\le \sum_{b=B+1}^{j-2} (j-b)!b!\,d \\ \le \sum_{b=2}^{j-2} (j-b)!b!\,d\le(j-2-1)(j-2)!2!\,d=o(j!).$$ Now (1) follows by the multiline display.