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.



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.

  • $\begingroup$ 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$? $\endgroup$
    – Vepir
    Commented Oct 8, 2019 at 13:19
  • $\begingroup$ 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$. $\endgroup$
    – antkam
    Commented Oct 8, 2019 at 13:50
  • $\begingroup$ 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. $\endgroup$ Commented Oct 9, 2019 at 7:43

1 Answer 1


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.

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

  • $\begingroup$ 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! $\endgroup$ Commented Oct 10, 2019 at 5:54
  • $\begingroup$ 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 \}$ $\endgroup$
    – antkam
    Commented Oct 10, 2019 at 12:16
  • $\begingroup$ 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? $\endgroup$ Commented Oct 11, 2019 at 7:34
  • $\begingroup$ You are missing the case with all 3 pairs, i.e. $\{a+b+c + ab+bc+ca\}$. :) $\endgroup$
    – antkam
    Commented Oct 11, 2019 at 11:37
  • $\begingroup$ Thanks a lot!!! Think i stared myself blind on it ;) So thanks for the beautiful solution to the problem! $\endgroup$ Commented Oct 11, 2019 at 11:55

You must log in to answer this question.

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