# All unique combinations of intersects and difference of $n$ sets

Given a number $$n>1$$ of sets $$x_i...x_n$$, I would like to figure out all the different combinations of intersects and differences of all the sets.

To try and model this I have listed combinations of all the $$x_i$$ written as equations to represent intersections and differences, where

• $$x_j-x_k$$ represents the difference of $$x_j$$ with $$x_k$$ (i.e. elements in $$x_j$$ that are not in $$x_k$$)
• $$x_j+x_k$$ represents the intersect of $$x_j$$ and $$x_k$$ (i.e. elements in both $$x_j$$ and $$x_k$$)

I assumed that there must also be the additional constraint that at least one $$x_i$$ must be positive in each equation.

For example, for two sets:

$$x_1 \hspace{0.5cm} +ve$$ $$x_2 \hspace{0.5cm}+ve$$
$$x_1+x_2$$ $$x_2+x_1$$
$$x_1-x_2$$ $$x_2-x_1$$

Now $$x_1+x_2=x_2+x_1$$ which leaves us with 3 unique combinations.

My thinking: For $$x_i...x_n$$, taking the first $$x_i$$ to be positive leaves us with $$2^{n-1}$$ choices ($$n-1$$ sets left, each can be positive or negative). Permuting and doing this for each $$x_i$$ gives $$n2^{n-1}$$.

Now I can see that there will always be $$n$$ equations where each $$x_i$$ is positive, so we will have here $$n-1$$ repititions. I.e. for $$n=3$$ $$x_1+x_2+x_3\\ x_2+x_3+x_1\\ x_3+x_2+x_1$$

Which gets me to $$n2^{n-1}-(n-1)$$

Now considering $$n>2$$, we also are going to get repetitions when permuting equations where there is more than one $$x_i$$ of the same sign, e.g.

$$x_a+x_b+x_c-x_d=\color{green}{x_b+x_c-x_d+x_a}=\color{blue}{x_c-x_d+x_a+x_b}$$

I think we can ignore this using a sum of combinations, i.e.

$$\sum_{i=2}^{n-1}{C^{n}_{i}}$$

Here we go from $$i=2$$, since we are looking for equations where there are at least 2 sets with the same sign, up to $$n-1$$, (not $$n$$ since we impose that there must always be one positive set and we have already eliminated all-positive repititions with the $$(n-1)$$ term).

altogether resulting in

$$n2^{n-1} - (n-1) - \left[\sum_{i=2}^{n-1}{C^{n}_{i}}\right]^{i\gt2}$$

which I believe holds for $$n=3$$, i.e.

$$3\times2^{2} -2 - C^{3}_{2}\\ \implies 12 - 2 - 3 = 7$$

$$x_1 +ve$$ $$x_2 +ve$$ $$x_3 +ve$$
$$x_1+x_2+x_3$$ $$\require{cancel}\cancel{x_2+x_3+x_1}$$ $$\cancel{x_3+x_1+x_2}$$
$$\color{blue}{\cancel{x_1+x_2-x_3}}$$ $$\color{red}{\cancel{x_2+x_3-x_1}}$$ $$\color{green}{\cancel{x_3+x_1-x_2}}$$
$$\color{green}{x_1-x_2+x_3}$$ $$\color{blue}{x_2-x_3+x_1}$$ $$\color{red}{x_3-x_1+x_2}$$
$$x_1-x_2-x_3$$ $$x_2-x_3-x_1$$ $$x_3-x_1-x_2$$

However, I'm not sure if this is actually correct and will hold for greater values of n and whether there is an easier way to deduce this.

I think the answer you want is actually just $$2^n-1$$, corresponding to the number of ways you can assign plus and minus signs to the expression
$$\pm x_1\pm x_2\cdots\pm x_n$$