# Combinations of combinations

I want to make the combinations of two sets, but i have a little problem.

Let's says there are four variables $$x_1,x_2,x_3,x_4$$, one set are just the normal combinations of these, the other set is the set of combinations of the two-way interactions, e.i

set 1: $$\{x_1,x_2,x_3,x_4,x_1+x_2,x_1+x_3,x_1+x4,...,x_1+x_2+x_3+x_4\}$$

set 2: $$\{x_1*x_2,x_1*x_3,x_1*x_4,x_2*x_3,x_2*x_4,x_3*x_4,x_1*x_2+x_1*x_3,...,x_1*x_2+x_1*x_3+x_1*x_4+x_2*x_3+x_2*x_4+x_3*x_4\}$$

In this case there are $$2^n-1$$ combinations in set 1 and $$\sum_{i=1}^k \begin{pmatrix} k \\ i \end{pmatrix}$$ in set 2 as i see it, where $$k=\begin{pmatrix} 4 \\ 2 \end{pmatrix}$$

What i want to calculate is the number of combinations but only count it if the combination has all the main effects that are in the interaction set e.x. the combination $$x_1+x_2+x_3+x_1*x_3$$ should count as one but not $$x_1+x_2+x_3+x_1*x_4$$ as $$x_4$$ is not part of the main effects it has been combined with.

Another way to frame this is that i want to calculate how many equations there are with two-way interactions and the correspondent main effects.

What i really want is to calculate this for n variables, but thought it was easier to explain with n=4. I hope this makes sense, and someone know a way to do this.

Thanks

EDIT:

Since i can see that i was really not clear at all what i really were asking for, i have made a new example there is hopefully better than the other one.

Let's say we have three items $$\{a,b,c\}$$, set 1 is then $$\{\{a\}$$, $$\{b\}$$, $$\{c\}$$, $$\{a+b\}$$, $$\{a+c\}$$, $$\{b+c\}$$, $$\{a+b+c\}\}$$,

And set 2 will be the combinations of the items, such that set 2 becomes $$\{\{ab\}$$, $$\{ac\}$$, $$\{bc\}$$, $$\{ab+ac\}$$, $$\{ab+bc\}$$, $$\{ac+bc\}$$, $$\{ab+ac+bc\}\}$$,

What i want to do then is to calculate how many combinations are of these two sets, but only counting those if a and b are in set two then it should also be in set 1. So for this example then i would like to get:

Combinations to count: $$\{\{a+b\}$$,$$\{ab\}\}$$, $$\{\{a+c\}$$,$$\{ac\}\}$$, $$\{\{b+c\}$$,$$\{bc\}\}$$, $$\{\{a+b+c\}$$,$$\{ab\}\}$$, $$\{\{a+b+c\}$$,$$\{ac\}\}$$, $$\{\{a+b+c\}$$,$$\{bc\}\}$$, $$\{\{a+b+c\}$$,$$\{ab+ac\}\}$$, $$\{\{a+b+c\}$$,$$\{ab+bc\}\}$$, $$\{\{a+b+c\}$$,$$\{ac+bc\}\}$$, $$\{\{a+b+c\}$$,$$\{ab+ac+bc\}\}$$, So there in this specefic case is 10 combinations of the two sets. So this is not all the combinations of the two sets, but i don't know how to either subtract the once i don't want, or only count the once that i want.

I really hope this was a better way of writing what I'm interested in.

• What are "main effects"? Do you want to combine elements $a$ from set $1.$ with elements $b$ from set $2.$, only if all variables in expression $b$ are also in expression $a$? – Vepir Oct 8 at 13:19
• Not an answer (since your question is unclear) but your set 2 just have $k = {n \choose 2} = n(n-1)/2$ base objects instead of $n$ base objects. The formula is analogous: $\sum_{i=1}^k {k \choose i} = 2^k - 1$. – antkam Oct 8 at 13:50
• I can see that i was not very clear of what i wanted, i have made a new example that hopefully i was better at explaining. But Vepir yes that is what i want, only the combinations of the sets were the elements in set 2 is also in set 1. – Jacob Christensen Oct 9 at 7:43

Here's an answer via a summation, but not a closed form solution.

First, lets rewrite the setting more clearly:

Let $$G$$ be a ground set, with $$|G|=n$$ elements. You prefer to call them $$x_1, x_2, \dots, x_n$$.

Your "set 1" is equivalent to the set of non-empty subsets of $$G$$. Normally the set of all subsets of $$G$$ (aka power set of $$G$$) would be denoted $$2^G$$ or $$\mathcal{P}(G)$$ (with a "fancy" $$\mathcal{P}$$ or $$\mathbb{P}$$), but you want to exclude the empty subset case. I will arbitrarily call it:

$$\text{Your set 1} = Q(G) = \{ S \subset G: S \neq \emptyset\}$$

Each element $$S \in Q(G)$$ is a non-empty subset of $$G$$, say $$S = \{x_1, x_3, x_7\}$$. Instead of using set-theoretic notation you prefer to write it as a linear combination, e.g. $$S = x_1 + x_3 + x_7$$, but these are clearly equivalent to subsets - assuming the standard convention that $$+$$ is commutative (i.e. ordering doesn't matter). Also, we have $$|Q(G)| =2^n - 1$$.

Given any $$G$$, define $$H(G)$$ to be the set of all unordered pairs of elements of $$G$$:

$$H(G) = \{ \{x_i, x_j\} : x_i \in G, x_j \in G, x_i \neq x_j \}$$

Instead of writing each pair in the set-theoretic way $$\{x_i, x_j\}$$ you prefer to write it as a product $$x_i x_j$$. Again these are clearly equivalent to unordered pairs - assuming your multiplication is also commutative, i.e. $$x_i x_j = x_j x_i$$. Also, we have $$|H(G)| = {n \choose 2} = n(n-1)/2$$.

Your "set 2" is simply the set of non-empty subsets of $$H(G)$$:

$$\text{Your set 2} = Q(H(G)) = \{T \subset H(G): T \neq \emptyset\}$$

Again, every element of $$T \in Q(H(G))$$ is a non-empty set consisting of pairs, and you prefer to write it as a linear combination: e.g. $$T = \{ \{x_1, x_3\}, \{x_1, x_7\} \} = x_1 x_3 + x_1 x_7$$. Also we have $$|Q(H(G))| = 2^{|H(G)|} - 1 = 2^{n(n-1)/2} - 1$$.

Then you want to count the number of "allowed" pairs of the form $$(S, T)$$ where:

• $$S \in Q(G)$$ i.e. your set 1

• $$T \in Q(H(G))$$ i.e. your set 2

• For every pair $$\{a, b\} \in T$$, we require $$a \in S, b\in S$$.

• This requirement rules out e.g. $$x_1 + x_2 + x_3 + x_1 x_4$$ because $$x_4$$ appears in a pair but not as a "singleton".

There is no requirement that the "other direction" is satisfied, i.e. there can be $$x \in S$$ which appears in no pairs $$\in T$$. E.g. $$x_1 + x_2 + x_3 + x_1 x_2$$ is allowed (and must be counted) even though $$x_3$$ does not appear in any pair.

Consider a subset $$S \subset G$$ of size $$k$$. For each such subset, you can form $${k \choose 2} = k(k-1)/2$$ pairs from the elements of $$S$$, and any non-empty collection of such pairs is allowed. I.e. the number of allowed pairs of $$(S,T)$$ for this specific $$S$$, is

$$2^{k(k-1)/2} - 1$$

Now of course there are $${n \choose k}$$ subsets of $$G$$ of size $$k$$, so you just need to sum over them:

$$\text{total no. of allowed pairs} = f(n) = \sum_{k=2}^n {n \choose k} (2^{k(k-1)/2} - 1)$$

Sorry I don't know how to simplify this further. Anyway, the values starting from $$f(2)=1, f(3)=10$$ are:

$$1, 10, 97, 1418, 40005, 2350474, 286192257 \dots$$

and I don't think this is in OEIS

• Thank you for writing this in a more clear mathematical way! As i see it this is spot on what I'm looking for. It's correct that what I'm looking for is the first requriement i.e. {a,b}∈T, we require a∈S,b∈S, but not the other way round. So having a combination that yields $x_1+x_2+x_3+x_1x_2$ is still a combination that i want to count. Again thank you for writing this up in a more understanble way! – Jacob Christensen Oct 10 at 5:54
• sure you're welcome. I will give this some more thought, but in the meantime pls update your last $a,b,c$ example to include e.g. $\{ a+b+c, ab \}$ – antkam Oct 10 at 12:16
• Thanks a lot for this! I tried to write n=4 out, but i get a problem with k=3. When i manualy do it i get that the number of valid combinations are 24 and not 28. As this is multiple with the numbers there are in the first set, so here is just what i wrote out for one of them: $\{x_1,x_2,x_3\}$,$\{x_1x_2\}$, $\{x_1,x_2,x_3\}$$\{x_1x_3\} \{x_1,x_2,x_3\}$$\{x_2x_3\}$ $\{x_1,x_2,x_3\}$$\{x_1x_2,x_1x_3\} \{x_1,x_2,x_3\}$$\{x_1x_2,x_2x_3\}$ $\{x_1,x_2,x_3\}$$\{x_1x_3,x_2x_3\}$ Is it because I'm missing one from this list, because then it adds up? – Jacob Christensen Oct 11 at 7:34
• You are missing the case with all 3 pairs, i.e. $\{a+b+c + ab+bc+ca\}$. :) – antkam Oct 11 at 11:37
• Thanks a lot!!! Think i stared myself blind on it ;) So thanks for the beautiful solution to the problem! – Jacob Christensen Oct 11 at 11:55