Evaluating scalar functions of vectors in multidimensional simplices.

Question

In question Multivariate sum over a simplex we deal with certain functions of vectors defined in multidimensional simplices. To be specific we are interested in evaluating a following sum: \begin{equation} {\mathcal S}^{(s,d)}(l) := \sum\limits_{\begin{array}{rr} a_0+\cdots+a_s=l\\ a_0 \ge 1, \cdots, a_s \ge 1\end{array}} \sum\limits_{0 \le \xi_1 \le \cdots \le \xi_d\le s} \prod\limits_{\eta=1}^d \left( \eta+\xi_\eta+A_{\xi_\eta-1}\right) \end{equation} where $A_\xi := \sum\limits_{\eta=0}^\xi a_\eta$. With a little help of Mathematica we have evaluated this sum for $d \le 3$. Oddly enough the results are very simple. We have: \begin{eqnarray} {\mathcal S}^{(s,3)}(l) &=& \frac{1}{48} (s+1) (s+2) (s+4)^2 (s+3)^2 \binom{l-1}{s}+\\ &&\frac{1}{48} s (s+1) (s+2) (3 s+10) (s+3)^2 \binom{l}{s+1}+\\ &&\frac{1}{48} s (s+1) (s+2) (3 s+4) (s+3)^2 \binom{l+1}{s+2}+\\ &&\frac{1}{48} s (s+1) (s+2)^2 (s+3)^2 \binom{l+2}{s+3} \end{eqnarray} The sum was done using practically the same methods as those in the question mentioned above. Unfortunately the derivation is very tedious even though it consists of simple elementary steps. The first question would of course be what is the result for generic values of $d$ and the second question would be can the result be derived using some combinatorial approach ?

Answer 1

We will be doing the sum over the $a$ parameters at first and only after we have eliminated the $a$ parameters we will sum over the $\xi$ parameters. Clearly the sum over the $a$ parameters is equivalent to summing over all possible $\{ A_\eta \}_{\eta=0}^{s-1}$ such that $1 \le A_0 < \cdots < A_{s-1} \le l-1$. Firstly note that we can easily do the sum over the "internal degrees of freedom", ie those $A$ parameters that do not appear in the term in the sum. We have: \begin{equation} {\mathcal S}^{(s,d)}(l) = \sum\limits_{1 \le A_{\xi_1-1} < \cdots < A_{\xi_d-1} \le l-1} \binom{A_{\xi_1-1}-1}{\xi_1-1} \cdot \prod\limits_{\eta=1}^d \left( \eta+\xi_\eta+A_{\xi_\eta-1}\right) \binom{A_{\xi_{\eta+1}-1} - A_{\xi_{\eta}-1} -1}{\xi_{\eta+1} - \xi_\eta -1} \end{equation} subject to $\xi_{d+1}=s+1$ and $A_s=l$. Now we will be summing over the remaining $A$ parameters from the left to the right. At each time step we absorb the appropriate factor in curly brackets to the binomial factor on the very left and then apply the following formula $\sum\limits_{A=0}^{A_1-1} \binom{A+c}{a} \binom{A_1-A-1}{b} = \binom{A_1+c}{a+b+1}$.

Summing over $A_{\xi_1-1}$: \begin{equation} (1+\xi_1) \binom{A_{\xi_2-1}-1}{\xi_2-1} +\xi_1 \binom{A_{\xi_2-1}}{\xi_2} \end{equation}

Summing over $A_{\xi_2-1}$: \begin{equation} (1+\xi_1)(2+\xi_2) \binom{A_{\xi_3-1}-1}{\xi_3-1} +\{\xi_1 (1+\xi_2) + \xi_2(1+\xi_1)\} \binom{A_{\xi_2-1}}{\xi_2}+ \xi_1 (1+\xi_2) \binom{A_{\xi_3-1}+1}{\xi_3+1} \end{equation}

From this we immediately recognize the structure of the result for generic values of $d$. We have: \begin{equation} {\mathcal S}^{(s,d)}(l) = \sum\limits_{\lambda=0}^d \binom{l-1+\lambda}{s+\lambda} \cdot {\mathcal W}^{(d)}_\lambda(\xi_1,\cdots,\xi_d) \end{equation} where the coefficients ${\mathcal W}$ satisfy following recursion relations: \begin{equation} {\mathcal W}_\lambda^{(d+1)} = (d+1-\lambda+\xi_{d+1}) {\mathcal W}_\lambda^{(d)} 1_{0 \le \lambda \le d} + (\xi_{d+1}+\lambda-1) \cdot {\mathcal W}_{\lambda-1}^{(d)} 1_{1 \le \lambda \le d+1} \end{equation} subject to ${\mathcal W}_0^{(0)} = 1$. At this stage we have done the sum over the $a$ parameters. We now sum over the $\xi$ parameters. We define: \begin{equation} {\mathcal W}^{(d)}_\lambda(s) := \sum\limits_{0 \le \xi_1 \le \cdots \le \xi_d \le s} {\mathcal W}^{(d)}_\lambda(\xi_1,\cdots,\xi_d) \end{equation} By induction in the variable $d$ we easily establish that the coefficients ${\mathcal W}$ have a following form: \begin{equation} {\mathcal W}^{(d)}_\lambda(s) = \sum\limits_{j=0}^d \binom{s+d+j}{d+j} \cdot {\mathcal C}^{(d)}_{\lambda,j} \end{equation} where the coefficients ${\mathcal C}$ do not depend on the variable $s$ and they satisfy the following recursion relations: \begin{equation} {\mathcal C}^{(d+1)}_{\lambda,j}=(d+j) \cdot \left\{{\mathcal C}^{(d)}_{\lambda,j-1} + {\mathcal C}^{(d)}_{\lambda-1,j-1}\right\} 1_{1 \le j \le d+1} - \left\{{\mathcal C}_{\lambda,j}^{(d)} \cdot (\lambda+j) + {\mathcal C}^{(d)}_{\lambda-1,j} \cdot (d+j+2-\lambda) \right\} 1_{0 \le j \le d} \end{equation} subject to ${\mathcal C}^{(0)}_{0,0}=1$. To summarize the following formula holds true: \begin{equation} {\mathcal S}^{(s,d)}(l) = \sum\limits_{\lambda=0}^d\sum\limits_{j=0}^d \binom{l-1+\lambda}{s+\lambda} \binom{s+d+j}{d+j} \cdot {\mathcal C}^{(d)}_{\lambda,j} \end{equation} where the coefficients ${\mathcal C}^{(d)}_{\lambda,j}$ depend neither on $l$ nor on $s$. It would be nice to find a closed form expression for those coefficients.