# Combinatory and Calculus. Computing the sum of…

Let $S={1,2,....2015}$ all first positive integers. Let $n = 2^{2015} - 1$ for convenience and let $A_1, A_2, .... A_n$ the non-empty subsets of S. For each subset $A_k$, let $P_k$ be the product of its elements (a product of 1 number is itself). Compute the sum $Q_{2015} = P_1+P_2+...P_n$.

This what I am thinking:

1# fact: there are $n$ non empty sets formed in S.

Knowing this I count the sum of the product when $P_1$={1}, $P_2$ = {1,2} etc. Then: $P_1=1$, $P_2=2!$ , $P_3=3!$, etc And I will have the first sum $Q_1= 1+2!=3!$.... But I need to count the others sum where the set $P_2$ could be {3, 123}.

How can I do this? Have I any problem in my logic? Is there any way to compute the sum $Q_{2015} = P_1+P_2+...P_n$ ?

Hint :

Let $f(x) = (x + 1)(x + 2)...(x + 2015)$

Now the expansion of this $f$ contains all the sum you want, when you put $x = 1$ You will probably have to subtract 1 (for the empty set), so the answer is f(1) - 1 which is $2016! - 1$

Edit :

Specifically, because OP has asked for a more detailed explanation

Consider $$(x + a)(x + b)(x + c) = x^3 + (a + b + c)x^2 + (ab + bc + ca)x + abc$$ Here all the coefficients represent the set of elements in the power set, ie. {a}, {b}. {c}. {a,b}, {b,c}, {c,a} and {a,b,c} (minus the null set). Now, you are not interested in the number of elements, but specifically the products of all elements. So product of all 2 element sets is $ab,bc, ca$ and their sum is $ab + bc + ca$ which is the coefficient of $x^2$. Thus you can see that the coefficients of the $x$'s in the expansion give you the sum of the products, taken one at a time, 2 at a time and 3 at a time in this case. That covers all the non-empty elements in this power set.

Now you can see that the problem you asked, all we need is the product as shown by $f(x)$ and when you put $x = 1$ you will get everything. The additional $1$ which you subtract is the coefficient of $x^{2015}$ which corresponds to the empty set.

• You said that such f(x) contains all the sum I want, when I put x=1 and I need to subtract 1 (for the empty set), so the ans. is f(1) - 1 which is which is equal to the sum Q2015. My question is how can I explain that such a function contain every non-empty subset, in other words. For example: the product of one specific set P= 2*4*6 that came from A= {2,4,6} is in such a sum like also other P=2*5*6 that came from other set A={2,5,6}. Are both P’s considered in such a function? And if so, how? I spend some time before asking, but I cannot see how to explained. Thanks. – Electro82 Sep 24 '15 at 20:36
• @Electro82 Please see the edit. I have added an explanation. Hope that helps. – Shailesh Sep 25 '15 at 5:31