# Help with combinations

The sum of all the different ways to multiply together $a,b,c,d,\ldots$ is equal to $$(a+1)(b+1)(c+1)(d+1)\cdots$$ right?

If this is true? why is it true?

-
You might have a look at Elementary Symmetric Polynomials... – draks ... Dec 16 '12 at 22:24

Let $A$ be a finite set of real numbers. Then $$\sum_{S\subseteq A}\prod S=\prod_{a\in A}(a+1)\;.\tag{1}$$

For instance, if $A=\{a,b,c\}$, then the subsets and their products are:

$$\begin{array}{c} \text{Subset}&\text{Product}\\ \hline \varnothing&1\\ \{a\}&a\\ \{b\}&b\\ \{c\}&c\\ \{a,b\}&ab\\ \{a,c\}&ac\\ \{b,c\}&bc\\ \{a,b,c\}&abc \end{array}$$

And the sum is $$abc+ab+ac+bc+a+b+c+1=(a+1)(b+1)(c+1)\;.$$

To see why this works, let $A=\{a_1,\dots,a_n\}$, and consider the product $\prod_{k=1}^n(a_k+1)$. This is a product of $n$ binomials, so it has $2^n$ terms when you multiply it out fully. In the example above, for instance, you get

$$a\cdot b\cdot c+a\cdot b\cdot1+a\cdot1\cdot c+1\cdot b\cdot c+a\cdot 1\cdot 1+1\cdot b\cdot 1+1\cdot 1\cdot c+1\cdot 1\cdot 1\;.$$

Each term $t$ is a product of $n$ factors, one from each of the $n$ binomials. Thus, a typical term has the form $t=x_1x_2\dots x_n$, where each $x_k$ is either $a_k$ or $1$. Let $S_t=\{a_k:x_k=a_k\}$; then $t=\prod S_t$, since the other factors in the term $t$ are all $1$. Each term of the product is therefore of the form $\prod S$ for some $S\subseteq A$, and it’s not hard to see that each $S\subseteq A$ gives rise to a term in the product $\prod_{k=1}^n(a_k+1)$.

In other words, when you multiply out the righthand side of $(1)$, you get precisely the lefthand side: each term of the muliplied-out product is one of the terms $\prod S$ for $S\subseteq A$, and each $S\subseteq A$ gives rise to one of the terms in ther product on the righthand side of $(1)$.

-

Yes it is true, give it a try...

Ok, sorry. Here's a little more detail:

We have the identity $$\prod_{j=1}^n ( \lambda-X_j)=\lambda^n-e_1(X_1,\ldots,X_n)\lambda^{n-1}+e_2(X_1,\ldots,X_n)\lambda^{n-2}-\cdots+(-1)^n e_n(X_1,\ldots,X_n).$$ $\biggr[$use $\lambda=-1$ to get $\prod_{j=1}^n ( -1-X_j)=(-1)^n\prod_{j=1}^n ( 1+X_j)$$\biggr]$

I really thought that giving it a try would show some inside.