(Solved) Closed-form formula for a simple sum of products

Question

I'm trying to find a closed-form formula of the following expression involving a particular value. Consider a list of $n$ ones and $t$ twos $(a_1,\cdots,a_{n+t})=(1_1,\cdots,1_n,2_1,\cdots,2_t)$. For example $n=2$ and $t=4$: $(1_1,1_2,2_1,2_2,2_3,2_4)$. Define the sum over all ${n+1 \choose 2}$ unique pairs of (indexed) $1$'s and $2$'s $P=\{(a_i,a_j) \;|\; 1\le i < j \le n+t\}$ as follows: $$ S = \sum_{(a_i,a_j)\in P} a_ia_j $$ The sum can be decomposed in pairs of the form $(1,1)$, $(1,2)$ and $(2,2)$, which leads (I hope I didn't make any mistakes) to $$ S = \sum_{i=1}^n \sum_{j=i+1}^n 1 + \sum_{i=1}^n \sum_{k=1}^t 2 + \sum_{j=1}^t \sum_{k=j+1}^t 4 = \frac{n(n - 1) + 4t(n + t - 1)}{2}. $$

Is there some closed-form formula involving only the total sum of the values $\varphi=n+2t$? For example, after rearranging: $$ S = \frac{n(n - 1) + 4t(\varphi - t - 1)}{2} $$ but there are still $n$ and $t$ in the expression. Can someone provide a formula in the form I'm looking for?

Answer 1

If the desired expression were to exist, we would find that, for two $(n,t)$ pairs giving the same value of $\varphi$, we would get the same value of $S$. This doesn't happen. When $(n,t) = (2,0)$, we have $(\varphi, S) = (2, 1)$. When $(n,t) = (0,1)$, we have $(\varphi, S) = (2,0)$. So, for the same values of $\varphi$, we have different values of $S$. Therefore, $S$ does not depend only on $\varphi = n+2t$. That is, no such formula exists.

How close can we get?

Since the degree of $n+2t$ is one (for either variable), we can use polynomial division (with remainder) to see whether $$ S = 1 \cdot \frac{n(n-1)}{2} + 2 \cdot n t + 4 \cdot \frac{t(t-1)}{2} = \frac{n(n-1)+4t(n+t-1)}{2} $$ is in the ideal generated by $n+2t$. \begin{align*} && S &= \frac{n+2t-1}{2}(n+2t) - t \\ &\text{or}& \\ && S &= \frac{n+2t-2}{2}(n+2t) + \frac{n}{2} \text{,} \end{align*} where in the first line we take $n$ as the variable and in the second line, $t$. In either case, there is a remainder (that is automatically not written in terms of $n+2t$). We had to be a little careful to ensure that $n+2t$ was the combination appearing in the quotient.

Another way to get at this is to write $\varphi = n+2t$, then there are two ways to go:

• apply the replacement $n \mapsto u - 2t$ and see if all $t$ dependence falls out, or
• apply the replacement $t \mapsto \frac{u-n}{2}$ and see if all $n$ dependence falls out.

When we make these substitutions, we obtain \begin{align*} && S &= \frac{\varphi(\varphi - 1)}{2} - t &\text{or}& \\ && S &= \frac{\varphi(\varphi - 2)}{2} + \frac{n}{2} \text{.} \end{align*} (In both cases, we should be able to compare with the matching expressions using polynomial division, above.) These have the advantage that writing the quotient in terms of $\varphi$ is automatic. Here also, we discover there is no such formula, but if we allow one "corrective" term at the end, we can get a formula with only one reference to either $n$ or to $t$.

Answer 2

This is not possible. Suppose towards a contradiction a closed formula exists in the form you are asking for. Then regardless of the values of $n$ and $t$ so long as $n+2t= \varphi $ the output of this closed formula will be the same. Let $\varphi = 2$. The two possible configurations are:

1. $n = 2$, $t = 0$
2. $n = 0$, $t = 1$

In the first case, there is one unique pair that sums to 1. In the second there are no unique pairs and so the sum is 0. We have a contradiction, no close formula only in terms of $\varphi$ exists.