# How to rewrite this nested summation as a single sum?

$Q$ and $p$ are natural numbers. $E$ equals the $p$-nested sum of products with $p+1$ factors

\begin{align}E&=\sum _{\large k_1=2}^Q\ \sum _{\large k_2=k_1+1}^Q\ldots\sum _{\large k_{p-1}\ =\\\large \ k_{p-2}+1}^Q\sum _{\large k_{p}\ =\\\large \ k_{p-1}+1}^Q a_{\large k_1-1,1}\ a_{\large k_2-1,k_1}\ldots\ a_{\large k_p-1,k_{p-1}}\ a_{\large Q,k_p}\\\\&=\sum _{\large k_1=2}^{Q-p+1}\sum _{\large k_2=k_1+1}^{Q-p+2}\ldots\sum _{\large k_{p-1}\ =\\\large \ k_{p-2}+1}^{Q-1}\sum _{\large k_{p}\ =\\\large \ k_{p-1}+1}^Q a_{\large k_1-1,1}\ a_{\large k_2-1,k_1}\ldots\ a_{\large k_p-1,k_{p-1}}\ a_{\large Q,k_p}\end{align}

E.g. when $Q=7$ and $p=4$ the products to be sumed are the $\binom{Q-1}{p}$ columns $$\begin{array}{ccccccccccccccc} a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{1,1} & a_{2,1} & a_{2,1} & a_{2,1} & a_{2,1} & a_{3,1} \\ a_{2,2} & a_{2,2} & a_{2,2} & a_{2,2} & a_{2,2} & a_{2,2} & a_{3,2} & a_{3,2} & a_{3,2} & a_{4,2} & a_{3,3} & a_{3,3} & a_{3,3} & a_{4,3} & a_{4,4} \\ a_{3,3} & a_{3,3} & a_{3,3} & a_{4,3} & a_{4,3} & a_{5,3} & a_{4,4} & a_{4,4} & a_{5,4} & a_{5,5} & a_{4,4} & a_{4,4} & a_{5,4} & a_{5,5} & a_{5,5} \\ a_{4,4} & a_{5,4} & a_{6,4} & a_{5,5} & a_{6,5} & a_{6,6} & a_{5,5} & a_{6,5} & a_{6,6} & a_{6,6} & a_{5,5} & a_{6,5} & a_{6,6} & a_{6,6} & a_{6,6} \\ a_{7,5} & a_{7,6} & a_{7,7} & a_{7,6} & a_{7,7} & a_{7,7} & a_{7,6} & a_{7,7} & a_{7,7} & a_{7,7} & a_{7,6} & a_{7,7} & a_{7,7} & a_{7,7} & a_{7,7} \\ \end{array}$$

How to define functions $f_1$ and $f_2$ that compute the indices of the $k$'th term's $j$'th factor?
I.e. such that

$$E=\sum_{k=1}^{\binom{Q-1}{p}}\prod_{j=1}^{p+1}a_{\large f_1(Q,p,k,j),f_2(Q,p,k,j)}$$

(that is, the order of terms as well as factors doesn't matter)

• IMO the original sum is easier to read as $$\sum_{\large 1 = k_0 < k_1 < \cdots < k_p < k_{p+1} = Q+1}\; \prod_{\large j=1}^{p+1} a_{k_j - 1, k_{j-1}}$$ Also the question can be simplified by noting that $f_1(Q,p,k,j) = f_2(Q,p,k,j+1)-1$ requiring only the addition of a special case $f_2(Q,p,k,p+2)=Q+1$. – Peter Taylor Jul 18 '18 at 13:02
• Replace the k's with their actual values - 2,3,4,... – William Elliot Jul 18 '18 at 19:50
• Instead of $f_1$ and $f_2$, you can write a few lines of code to find the NEXT set, based on which factor gets its index increased by $1$. – Empy2 Jul 21 '18 at 0:49

Reading from right to left, the last $a_{3,1},a_{2,1}$ and $a_{1,1}$ are in columns $1,5,15$ which are ${4\choose4},{5\choose4}$ and ${6\choose4}$. So you want the inverse function of $$f(n)={n\choose4}$$ Within each of those, the second factor comes from similar $n\choose3$ and so on. I wonder how effective is $$g(m)=\sqrt[4]{4!f(n)}+\frac32$$ Lookup tables would be effective.