How can this combination of factors be described in terms of combinations or permutations?

Question

If one has $x_1x_2x_3+x_2x_3x_4+x_1x_3x_4+x_1x_2x_4$ it seems like that could be described with some kind of sum of permutations, but how? It should be noted that the order doesn't matter, once one possible combination is used up, it's used up.

Answer 1

I'm not totally sure what you are aiming for but let me give some insight into this:

What you have written is an example of the $n^{\text{th}}$ elementary symmetric polynomial in $k$ indeterminates $x_i$ for $i=1,\ldots ,k$.

In this case $n=3$ and $k=4$:

$$e_3=x_1x_2x_3+x_2x_3x_4+x_1x_3x_4+x_1x_2x_4$$

The generating function for $e_n$ is fairly easy to construct by remembering that the binomial expansion has, as its $z^n$ coefficient, the count for the number of choices of $n$ "things" from $k$ "things".

The expansion is:

$$(1+z)^k=\sum_{n=0}^{k}\binom{k}{n}z^n$$

If, instead of a count, we now want a list of the choices of $x_i$'s for each coefficient of $z^n$ we must tag $z$ in each $(1+z)$ factor with one of the $x_i$ indeterminates, viz:

$$E_k(z)=(1+x_1z)(1+x_2z)\cdots (1+x_kz)=\sum_{n=0}^{k}e_nz^n$$

$E_k(z)$ is our required generating function for these lists.

In our case:

$$E_4(z)=(1+x_1z)(1+x_2z)(1+x_3z)(1+x_4z)=e_0+e_1z+e_2z^2+e_3z^3+e_4z^4$$

and therefore:

$$\begin{align}&e_0=1\\ &e_1=x_1+x_2+x_3+x_3\\ &e_2=x_1x_2+x_1x_3+x_1x_3+x_2x_3+x_2x_4+x_3x_4\\ &e_3=x_1x_2x_3+x_2x_3x_4+x_1x_3x_4+x_1x_2x_4\\ &e_4=x_1x_2x_3x_4\end{align}$$

so we could use the "find the coefficient of $z^n$" operator "$[z^n]$" to represent your polynomial:

$$e_3=[z^3]\prod_{i=1}^{4}(1+x_iz)$$

However this is all just notation, but the binomial expansion does help us visualise $e_3$ as one of a set of polynomials $\{e_n\}$ that list $n$-choices from the $x_i$'s.