Sum of multi-index factorials

Question

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?

Answer 1

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<n!<(2\pi(n+1))^{1/2}(n/e)^n \tag{1}$$ 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.

Answer 2

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.

Answer 3

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.