2
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Oh, well. Without a formula my work is going to be slightly harder... But, my, I never thought of applying this technique and the formulae you gave are really going to be useful. Thanks a lot! $\endgroup$
    – llualpu
    Sep 5, 2020 at 5:35
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Oh, wow. I'm not going to work at night again. Thank you for the sweet and short answer. $\endgroup$
    – llualpu
    Sep 5, 2020 at 5:23

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.