1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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$$

without making the signs all negative.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .