Sum of products of elements of nonempty subsets of A set

Solution 1:

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

Solution 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)$$

Solution 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}$$