Given a list N . I need to sum up products of all ${N}\choose{k}$ sublists.

It doesn't matter if two elements are same.

example N = 3

[1, 2, 2]

k = 2

[1, 2], [2, 2], [2, 1]

ans = 1*2 + 2*2 + 2*1 = 8

This was given at a math programming contest. the solution was to represent each number as 1 degree polynomial $(x+value)$ and multiply all the polynomials and the coefficient of $$(x^{N-k})$$ was the answer. But I am not able to understand how.


Hint: This is very closely tied to the binomial theorem: $(x+y)^n = {{n}\choose{k}}x^{n-k}y^k$, except here the $y$ is not constant. Instead, let $y_1,y_2,...,y_n$ be the elements of the list (not necessarily distinct, as you specified) and we are curious about the coefficient of $x^{n-k}$ in the expansion of $(x+y_1)(x+y_2)...(x+y_n)$. We find the coefficient of $x^{n-k}$ is

$$y_1 \cdot y_2 ... y_{k-1} \cdot y_k +$$ $$y_1 \cdot y_2...y_{k-1} \cdot y_{k+1} +$$ $$... +$$ $$y_{n-k+1} \cdot y_{n-k+2} ... y_{n-1} \cdot y_n$$

Each of those terms in the summation is the product of one of the combinations in ${{n}\choose{k}}$ (because the term in the polynomial is $x^{n-k}$, that means that $k$ of the $y_i$ terms were multiplied together).


Let consider 3rd degree polynomial, say $$ p(x) = (x + a)(x+b)(x+c) $$ When we expand this polynomial, we have total 8 terms, which consist of choosing one element from each term (x+something). For example, choose $x$ from $(x+a)$, choose $b$ from $(x+b)$ and choose $c$ from $(x+c)$. By combining all possibilities, we obtain the expansion of the polynomial.

Suppose we choose an element among $\{a,b,c\}$ and in the order of $a,b,c$. So at first, we decide whether the element $a$ to be chosen. This corresponds to the term $(x+a)$. If we choose $a$, we choose $a$ in the expansion of the polynomial. Unless choose $x$. And we repeat the process.

Then, for example, the coefficient of $x$ is the number of possibilities in expanding polynomial, which chooses $x$ only one time. In other words, the number of possibilities of choosing only 2 elements among $\{a,b,c\}$ in expanding polynomial.

Thus the coefficient of $x$ means that the number of sum of product of only 2 elements (among $a,b,c$), as we choose one element from each term (x+something).

Therefore, if we generalize this idea, we conclude that the coefficient of $x^{N-k}$ gives what you want.


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.