Let $n$ be an integer and $a_1, \dots, a_n$ positive reals. $\forall 1 \leq i < j \leq n$ let $a_{i, j}$ be a positive number. Let $k \leq n$ be a positive integer. I would like to find an efficient way (either a closed formula, or an algorithm polynomial in $n$, $k$) to find
$ \sum_{S \subseteq \{1,\dots,n\}, |S| = k} \prod_{i \in S} a_i \prod_{i, j \in S, i < j} a_{i, j}$
EDIT:
I see that it is sufficient to find
$ \sum_{S \subseteq \{1,\dots,n\}, |S| = k} \prod_{i, j \in S, i < j} a_{i, j}$
We can multiply each $a_{i,j}$ by $\sqrt[k-1]{a_i a_j}$ and this way to get rid of $a_1,\dots,a_n$.
If you can't find a solution (possibly there is none), than any directions for how to get to this problem would be appreciated. Even an approximation algorithm is fine
Define $$f(r,m)=\sum_{S\subseteq\{1,\ldots,n\},\atop|S|=r,\max S=m}\prod_{i,j\in S,\atop i<j}a_{i,j} $$ You want $$\sum_{m=k}^nf(k,m).$$ We have the recurrence $$ f(r,m)= \sum_{r-1\le i<m}f(r-1,i)a_{i,m}$$
Thus to compute all $f(r,m)$, $1\le m\le n$, from the $f(r-1,m)$ takes $O(m^2)$ time, and to compute everything up to $r=k$ takes $O(km^2)$ time - and with suitable bookkeeping $O(n)$ space.