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.
Best Answer
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$.
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.
Now, my answer:
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