Suppose that we have two sequences of $n$ naturals, which we'll call $a$ and $b$. We can denote the $k$th value in the sequence by the term $a_k$ and $b_k$ respectively. We can then define a like multiplication for some number $v$. To do this, we pick $j$ terms from $a$, and at the same time take the terms with the same indexes from $b$. For example, if we pick 3 terms from $a$, and they are $a_3$, $a_5$, and $a_9$, then we would also pick $b_3$, $b_5$ and $b_9$. The like multiplication is then $$(v+a_3+a_5+a_9) \cdot (v+b_3+b_5+b_9)$$

In other words, the like multiplication for $v$ is just $v$ plus some terms from $a$ multiplied by $v$ plus the same terms from $b$. I would like to know the fastest way to find the sum of all possible like multiplications for some $v$ and two equal length sequences $a$ and $b$.

This is somewhat related to this question that I asked before. In particular, we may be able to eliminate $v$ from the equations using that question's answer.

  • $\begingroup$ There's a trivial way to do this in $O(2^n)$ by exhaustively multiplying every possible combination. However, I believe that we might be able to do this in $O(n)$ by using the answer to the other question. I'm hoping that someone can confirm this with an explanation. $\endgroup$
    – Matt Groff
    Jan 6, 2012 at 14:08

1 Answer 1


For ease of proof, we'll assume you allow the empty subset of indices, as well - that is, the term $v^2$ is in your sum.

Let $N=\{1,...,n\}$. For $S\subset N$ write $a_S=\sum_{i\in S} a_i$ and $b_S$ similarly. Then you want $$\sum_S (v+a_S)(v+b_S) = \sum_S v^2 + \sum_S (a_S+b_S)v + \sum_S a_Sb_S$$

But: $$\sum_S v^2 = 2^n v^2$$ $$\sum_S (a_S+b_S)v = v 2^{n-1}(a_N+b_N)$$

The second formula comes about because for each $k\in N$, $k$ occurs in $2^{n-1}$ subsets $S$, so $a_k$ and $b_k$ each occur $2^{n-1}$ times in the sum.

So the only tricky term is $\sum_S a_Sb_S$. How many times does $a_ib_j$ occur in this sum? If $i=j$, then it occurs in the sum $2^{n-1}$ times.

If $i\neq j$, then $a_ib_j$ occurs once whenever $i,j\in S$. There are $2^{n-2}$ such $S$. Let $D\sum_{i\in N} a_ib_i$. Let $E=\sum_{i,j\in N} a_ib_j = a_Nb_N$.

Then $$\sum_S a_Sb_S = 2^{n-2}(D+a_Nb_N)$$

So, your total is:

$$2^nv^2 + v2^{n-1}(a_N+b_N) + 2^{n-2}(D+a_Nb_N)$$

Since $a_N,b_N,D$ can all be computed in $O(n)$ time, so can your total.

Note that this total can be written as:

$$2^{n-2}[4v^2 + 2v(a_N+b_N) + a_Nb_N + D]$$


$$4v^2 + 2v(a_N+b_N) + a_Nb_N = (2v+a_N)(2v+b_N)$$

So we can write your sum as:

$$2^{n-2}[(2v+a_N)(2v+b_N) + D]$$

If you don't want to include the empty set in the sum, you have to subtract $v^2$ from this result, of course.

Dividing our formula by $2^n$ gives the average of $(v+a_S)(v+b_S)$, which this formula says is:

$$(v+\frac{a_N}2)(v+\frac{b_N}2) + \frac{D}{4}$$

Note that $v+\frac{a_N}2$ is the average value of $v+a_S$ and $v+\frac{b_N}2$ is the average of $v+b_S$. So this says that the average of the product $(v+a_S)(v+b_S)$ minus the product of the average of $v+a_S$ and the average of $v+b_S$ is always $\frac{D}4$.

  • $\begingroup$ Thanks for the extra information! $\endgroup$
    – Matt Groff
    Jan 6, 2012 at 17:48

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.