Is there a clean way to write the expansion of:

$$\prod_{k=1}^n (1 + x_k) = (1 + x_1)(1 + x_2)\dots(1 + x_n)$$

The expansion may be written:

$$1+\sum_{1\le i \le n} x_i +\sum_{i \le n}\sum_{j\lt i} x_j x_i + \sum_{i \le n}\sum_{j\lt i}\sum_{k\lt j} x_kx_jx_i+\cdots+ x_1x_2\cdots x_n$$

But it would be nice if there were a more compact way of writing this. I tried making use of the Levi-Civita tensor over an indexed set:

$$1 + \sum_{k=1}^n \sum_{(i_j)_{j \in \{1 \dots k\}} \in \{1 \dots n\}} \frac{1}{2} |\epsilon_{i_1 \dots i_k}| \prod_{j=1}^k x_{i_j}$$

But that seems a little messy.


As explained in Richard Stanley book we have: $$\prod_{k=1}^n (1 + x_k) = (1 + x_1)(1 + x_2)\dots(1 + x_n) =\sum_{A\subseteq [n]}\prod_{i\in A}x_i$$

where $\displaystyle{\prod_{i\in\varnothing}x_{i}:=1}$ as Ethan remarks.

More generally, you can consider even the multiset case:

$$\prod_{k=1}^n (1 + x_k+x_k^{2}+\cdots) = (1 + x_1+x_1^{2}+\cdots)(1 + x_2+x_2^{2}+\cdots)\dots(1 + x_n+x_n^{2}+\cdots)$$ $$=\sum_{(M,\,\mu)\subseteq [n]}\prod_{i\in (M,\mu)}x_i^{\mu(i)}$$

where $(M,\mu)$ is a multi-subset of $[n]=\{1,2,\ldots,n\}.$


I'd probably use elementary symmetric polynomials. However, here is an equivalent representation more generally for any (possibly non-commutative) semi-ring equipped with $+,\times$ and an identity $I$ Namely if we denote the family of all order perserving injections from $\{1,2,\ldots, k\}$ to $\{1,2,\ldots, n\}$ by the set $[n,k]$ so that we get:

$$\varphi\in [n,k]\iff \left[\varphi:\{1,\ldots, k\}\to \{1,\ldots, n\} \text{ is injective}\right]\land \left[k<n\implies \varphi(k)<\varphi(k+1)\right]$$

Then we can express the following product explicitly:


Noting that $\left\{\text{rng}(\varphi):\varphi\in [n,k]\right\}$ is the set of all $k$ element subsets of $n$ therefore $|[n,k]|=\binom{n}{k}$.

If multiplication is commutative, the indices reduce to subsets of $\{1,2,3,\ldots, n\}$ so we can write:

$$\prod_{k=1}^n(I+a_k)=I+\sum_{\substack{S\subseteq \{1,2,\ldots, n\}\\ S\neq \emptyset}}\prod_{a\in S}a$$


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.