What's the fastest way to find this sum of "like multiplications"? 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.
 A: 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]$$
And
$$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$.
