1
$\begingroup$

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.

$\endgroup$
  • $\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 Oct 8 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 Oct 8 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$ – Jacob Christensen Oct 9 at 7:43
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.