Intuition to sum of product k length elements from a list of size N

Question

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.

Answer 1

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

Answer 2

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.