0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Peter Taylor Jul 18 '18 at 13:02
  • $\begingroup$ Replace the k's with their actual values - 2,3,4,... $\endgroup$ – William Elliot Jul 18 '18 at 19:50
  • $\begingroup$ 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$. $\endgroup$ – Empy2 Jul 21 '18 at 0:49
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.