Sum of products of elements of nonempty subsets of A set

Question

Let $A_1, A_2, \ldots , A_{63}$ be the 63 nonempty subsets of $\{ 1,2,3,4,5,6 \}$. For each of these sets $A_i$, let $\pi(A_i)$ denote the product of all the elements in $A_i$. Then what is the value of $\pi(A_1)+\pi(A_2)+\cdots+\pi(A_{63})$?

Here is the solution

For size 1: sum of the elements, which is 21 For size 2: $ 1 \cdot (2 + 3 + 4 + 5 + 6) = 20 $, $ 2 \cdot (3 + 4 + 5 + 6) = 36 $, $ 3 \cdot (4 + 5 + 6) = 45 $, $ 4 \cdot (5 + 6) = 44 $, $ 5 \cdot 6 = 30 $. Sum is 175. For size 3: Those with least element 1: $ 6, 8, 10, 12, 12, 15, 18, 20, 24, 30 = 155 $. Those with least element 2: $ 24, 30, 36, 40, 48, 60 = 238 $. Those with least element 3: $ 60 + 72 + 90 = 222 $. Those with least element 4: only one possible subset, which is $ \{4, 5, 6\} $, the $ \pi $ of which is 120. The total sum here is 735. For size 4: Least element 1: $ 24 + 30 + 36 + 40 + 48 + 60 + 60 + 72 + 90 + 120 = 580 $; least element 2: $ 120 + 144 + 180 + 240 + 360 = 1044 $; least element 3: only one, which is $ 3 \cdot 4 \cdot 5 \cdot 6 = 360 $. The total sum here is 1984. For size 5: Exclude each one individually to get $ 720 + 360 + 240 + 180 + 144 + 120 = 1764 $ For size 6: $ 6! = 720 $

The final answer is $ 21 + 175 + 735 + 1984 + 1764 + 720 = \boxed{5399} $

Is there any shorter way for doing this ?

Thank a lot

Answer 1

It's just one less than the product $$(1+1)(1+2)(1+3)(1+4)(1+5)(1+6)$$ Equivalently, it's $f(1)-1$ where $$f(x) = (x+1)(x+2)(x+3)(x+4)(x+5)(x+6)$$ By Vieta's formulas, the coefficients of all powers of $x$, other than $x^6,\;$in the expanded form of $f(x)$ are the sums of products that you want.

More precisely, for $1 \le k \le 6$, the coefficient of $x^{6-k}$ in the expanded form of $f(x)$ is the sum of all products of $k$ elements of $\{1,2,3,4,5,6\}$.

But summing those coefficients is the same as substituting $x=1$ into $f(x)$, except that you need to subtract $1$ to correct for the extra summand from the term $x^6$.

Answer 2

I have a way of doing it, but for some reason I don't get the same result that you've got.

Generally, if you have a finite set $A$ of numbers, and you want $\sum_{X\subseteq A}\prod_{x\in X}x$, the result will be $\prod_{x\in A}(x+1)$.

In your case it will be $(1+1)(2+1)(3+1)(4+1)(5+1)(6+1)=2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7=5040$: take away the empty product for $X=\emptyset, \prod_{x\in\emptyset}x=1$ and you will get the final result $5039$.

Proof: Induction on $n=|A|$. For $n=0$ the equality holds trivially. Assume it holds for all sets of size $n$. Let $A$ be a set of size $n+1$ and let $a\in A$ and $B=A\setminus\{a\}$. Now, we can break up all subsets of $A$ into those that contain $a$ and those that don't:

$$\sum_{X\subseteq A}\prod_{x\in X}x=\sum_{X\subseteq B}\prod_{x\in X}x+\sum_{X\subseteq B}a\prod_{x\in X}x=(a+1)\sum_{X\subseteq B}\prod_{x\in X}x=(a+1)\prod_{x\in B}(x+1)\text{ (inductive hypothesis) }=\prod_{x\in A}(x+1)$$

Answer 3

Let $X$ be a set containing $6$ geese a-laying, $5$ gold rings, $4$ calling birds, $3$ French hens, $2$ turtle doves and $1$ partidge in a pear tree.

For a fixed $A \subseteq \{ 1, 2, 3, 4, 5, 6 \}$, the value $\pi(A)$ is the number of ways of picking one of each of the animals (or rings, I guess) from $X$ as indicated by $A$. For example, $\pi(\{2,5\})$ is the number of ways of picking one turtle dove and one gold ring from $X$.

So $\sum_{A \subseteq X} \pi(A)$ is the number of ways of (i) selecting a subset of $[6]$ and (ii) selecting one of each animal/ring as indicated by that subset.

This value can also be calculated by, for each $k \in [6]$, deciding if you will choose an animal/ring as indicated by $k$ and, if so, selecting one. If an animal/ring is chosen, there are $k$ choices for which one to pick; if not, there is only $1$ choice (pick nothing). Thus $$\sum_{A \subseteq X} \pi(A) = \prod_{k=1}^6 (k+1) = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7$$

This takes into account the possibility of selecting nothing, so we must subtract one, to obtain $$\sum_{i=1}^{63} \pi(A_i) = \sum_{\varnothing \ne A \subseteq X} \pi(A) = 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 - 1 = \boxed{5039}$$

Answer 4

Include the empty set in the sum (we can subtract at the end)

The contribution from each of the subsets will correspond to a term in the following product \begin{eqnarray*} (1+1)(1+2)(1+3)(1+4)(1+5)(1+6) \end{eqnarray*} So the answer is $\color{red}{5039}$.

In your question the values should be $21,175,735,\color{red}{1624},1764,720$.

Answer 5

The answer is 5039 just because, if you add 1 (let 1 be the product of the elements of the empty set) you must get $7!$.

This is a general property: if $\pi(A)$ is the product of the elements of $A$ (with the convention $\pi(\emptyset)=1$), and $[n] = \{1,2,\dots, n\}$, then for every natural $n$ $$ \sum_{A\subseteq [n]} \pi(A) = (n+1)!\,. $$ It is an equivalent fact that $$ \sum_{A\subseteq [n]} \frac 1 {\pi(A)} = n+1\,, $$ as we see by dividing each term by $n!$ (every term $\pi(A)$ becomes $1/\pi(A^c)$).

Both of them are very easily proved by induction, but an alternative proof and a nice probabilistic interpretation of the second one is as follows:

We are at the $(n+1)$-th floor, and we take a lift to get down to the ground floor. But every time we press the button the lift will stop at a random level on the way, with uniform probability.

Let $A$ be the set of levels (floors) where the lift stops before we are downstairs. If we get there in the first step then $A=\emptyset$. When we are at the $k$-th floor, we have $k$ different possible stops in the next stage. Hence the probability of any $A$ as the set of intermediate points is $1/\big((n+1)\,\pi(A)\big)$, and summing up for all $A$ we get $$ 1 = \frac 1 {n+1} \,\sum_{A\subseteq [n]} \frac 1 {\pi(A)}\,. $$