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.

  • $\begingroup$ 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. $\endgroup$ – Electro82 Sep 24 '15 at 20:36
  • $\begingroup$ @Electro82 Please see the edit. I have added an explanation. Hope that helps. $\endgroup$ – Shailesh Sep 25 '15 at 5:31

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.