10

Let $R$ be a commutative ring with unity, and let $S\subset R$ be any finite set. Then $$ \sum_{L \subset S} \prod_{x \in L} (x-1) = \prod_{x \in S} x,$$ which is easy enough to show by induction.

Does this follow from any sort of general principle? Perhaps inclusion-exclusion, in some form?

awwalker
  • 6,924

4 Answers4

9

Let $S'$ be $\{x : x-1 \in S\}$, in other words we shift $S$ by one.

The equality $$ \sum_{L \subset S} \prod_{x \in L} (x-1) = \prod_{x \in S} x$$

reduces to

$$ \sum_{L \subset S'} \prod_{x \in L} x = \prod_{x \in S'} (x+1)$$

but this is obviously distributivity: LHS is the expanded RHS.

sdcvvc
  • 10,528
1

If $S=\emptyset$, then $L=\emptyset$ is the only subset and by convention the empty product $\prod_{x\in L} (x-1)$ equals $1$. That shows $$\tag1 \sum_{L\subseteq S}\prod_{x\in L}(x-1)=\prod_{x\in S}x$$ holds at least if $S=\emptyset$. For an induction step, let $a\in S$ be any element and let $S'=S\setminus\{a\}$. By assumption, $(1)$ holds with $S'$ in place of $S$. We find $$\begin{align}\sum_{L\subseteq S}\prod_{x\in L}(x-1)&=\sum_{a\in L\subseteq S}\prod_{x\in L}(x-1)+\sum_{a\notin L\subseteq S}\prod_{x\in L}(x-1)\\ &=\sum_{L\subseteq S'}(a-1)\prod_{x\in L}(x-1)+\sum_{L\subseteq S'}\prod_{x\in L}(x-1)\\ &=a\cdot\sum_{L\subseteq S'}\prod_{x\in L}(x-1)\\ &=a\cdot \prod_{x\in S'}x = \prod_{x\in S}x.\end{align} $$

1

Clearly it suffices to show the result when $R=\mathbb Z[S]$ and $S$ is the (finite) set of indeterminates of the polynomial ring $R$ (just specialize).

Let $T$ be any nonempty subset of $S$, and let $x_T=\prod_{x\in T}x$. Given $L\subseteq S$, it follows that $x_T$ appears in the expansion of $\prod_{x\in L}(x-1)$ if and only if $L\supseteq T$, and it appears precisely with coefficient $(-1)^{|L\setminus T|}$. Therefore the coefficient of $x_T$ in $\sum_{L\subseteq S}\prod_{x\in L}(x-1)$ is precisely

$$\sum_{L\supseteq T}(-1)^{|L\setminus T|}\,.$$

If $T$ is a proper subset of $S$, then you can fix an element $z$ outside $T$. From this you can see that the sets $L$ containing $T$ come in two "flavors": those of the form $T\cup Q$, with $Q\subseteq S\setminus\bigl(T\cup\{z\}\bigr)$, and those of the form $T\cup Q\cup\{z\}$, with $Q$ as before, so your coefficient is given by

$$\sum_Q\biggl[(-1)^{\bigl|\,(Q\cup\{z\})\setminus T\,\bigr|}+(-1)^{\bigl|\,Q\setminus T\,\bigr|}\biggr]=\sum_Q0=0\,.$$

Finally, the coefficient of $x_S$ is clearly equals to $(-1)^0=1$.

0

$$\begin{array}{cl} \sum_{L \subseteq S} \prod_{x \in L} (x-1) & = \sum_{L\subset S}\sum_{M\subseteq L}(-1)^{|L\setminus M|}\prod_{x\in M}x \\ & =\sum_{M\subseteq S}\left[\sum_{M\subseteq L\subseteq S}(-1)^{|L\setminus M|}\right]\prod_{x\in M}x \\ & = \sum_{M\subseteq S}\left[\sum_{\ell=|M|}^{|S|}{|S|-| M|\choose \ell-|M|}(-1)^{\ell-|M|}\right] \prod_{x\in M}x \\ & = \sum_{M\subseteq S}\delta_{|S|,|M|}\prod_{x\in M}x \\ & = \prod_{x\in S}x. \end{array}$$

You can notice the Möbius function of the poset of subsets of $S$ in the above, so there is definitely some combinatorial inclusion-exclusion going on here.

azimut
  • 22,696
anon
  • 151,657
  • 2
    Yes, if you replace $(x-1)$ with $(1-x)$ (and add a corresponding sign before the product) and then interprete $x$ as a probability, at last the relation to the probability tag becomes clearer ... – Hagen von Eitzen Mar 12 '13 at 07:47