<p>Let $n$ be the number of rows (in your case $n=5$) and $|O_j|$ the <a href="https://en.wikipedia.org/wiki/Cardinality" rel="nofollow noreferrer">cardinality</a> of $O_i$.</p>

<p>We can calculate the number of compatible columns as sum of the number of $O_i \subseteq O_j$, $O_j \subseteq O_i$ and $O_i, O_j$ disjoint.</p>

<p>number of $O_i \subseteq O_j$:
Here we need to find the number of supersets of our $O_i$. That means we need to find the number of sets which contain the indices in $O_i$ and for each index not in $O_i$, we have two choices: It is contained, or it is not contained in $O_j$. Therefore the number of supersets is $2^{n-|O_i|}$, which is 2 to the power of elements not in our set.</p>

<p>number of $O_i, O_j$ disjoint:
Here all elements of $O_i$ are fixed not to be in $O_j$ and for each index not in $O_i$, it can again be in $O_j$ or not. That means that the number of possible sets is again $2^{n-|O_i|}$.</p>

<p>number of $O_j \subseteq O_i$:
Here we need to find the number of subsets of $O_i$ and this is the number of elements in its power set, which is $2^{|O_i|}$.</p>

<p>So finally, this means that the number of compatible columns can be calculated as: $2^{n-|O_i|} + 2^{n-|O_i|} + 2^{|O_i|} - 2$.</p>

<p>Why -2? We have counted 2 sets twice: </p>

<ul>
<li>The empty set, which is a subset of $O_i$ and also counted in the number of disjoint sets</li>
<li>and $O_i$, which we counted in $O_i \subseteq O_j$ and in $O_j \subseteq O_i$</li>
</ul>

<p>This means for your examle, we have $16 + 2 + 2 - 2 = 18$ compatible sets.</p>

<p><strong>Note:</strong> The all zero vector (which corresponds to $O_i=\{\}$) is a special case for which the formula above does not work, as all disjunct sets and all supersets are counted twice. For this special case, the number of compatible columns is simply $2^n$.</p>

CC BY-SA 3.0
2018-01-09T10:24:03.823Z
Thanks for your answer. How do you calculate `|Oi|` ?
Mihai Alexandru-Ionut
CC BY-SA 3.0
2018-01-09T10:26:13.760Z
$|O_i|$ is the number of elements in $O_i$, so for your column $|O_i|$ is 4 because $O_i = \{1,2,3,5\}$
Bluescreen
CC BY-SA 3.0
2018-01-09T10:30:11.577Z
In my example why is not 5 ? Cardinal({1,1,1,0,1})=5
Mihai Alexandru-Ionut
CC BY-SA 3.0
2018-01-09T10:32:18.280Z
The cardinality of your column is 5. But in your definition: "Using the notation Oi to denote the collection of rows possessing a 1 in their i-th element,", $O_i$ is the set of rows with a 1. In your column there are 4 rows with a one, so the cardinality of $O_i$ = 4
Bluescreen
CC BY-SA 3.0
2018-01-09T10:33:59.593Z
Thanks a lot for your explanation.Now I understand. It means that for (0,0,0,0,0) the answer is `2^5+2^5+2^0-2 =63` ?
Mihai Alexandru-Ionut
CC BY-SA 3.0
2018-01-09T10:43:08.353Z
The number of compatible columns can not be larger than the total number of sets with 5 elements ($2^5$) :). (0,0,0,0,0) Is indeed a special case for which my rule above breaks, as all disjoint sets and all supersets are counted twice. So for This special case you have to hard code the result to $2^n$. For all other cases, the formula should work.
Bluescreen
CC BY-SA 3.0
2018-01-09T10:17:12.033Z
2018-01-09T10:50:38.860Z
2018-01-09T10:50:38.860Z
Bluescreen
<p>We have a column which has following format : (1, 1, 1, 0, 1).</p>

<p>Here is the definition of what means two columns are <strong>compatible</strong>.</p>

<blockquote>
  <p>Using the notation Oi to denote the collection of rows possessing a 1
  in their i-th element, we conclude that one of three possibilities
  must be true: Oi ⊆ Oj , Oj ⊆ Oi , or Oi and Oj are disjoint (the first
  two cases include the possibility that Oi = Oj). If columns i and j
  satisfy this condition, then we call them compatible</p>
</blockquote>

<p>The question is : <strong>How many possible columns of length 5 are compatible with the column (1, 1, 1, 0, 1)?</strong></p>

<p>You can read more <a href="http://bioinformaticsalgorithms.com/excerpt/How%20Have%20Humans%20Populated%20the%20Earth.pdf" rel="nofollow noreferrer">here</a> where problem is described in page 14-16.</p>

<p>Thanks in advance !</p>

CC BY-SA 3.0
2018-01-09T09:11:36.610Z
I'm voting to close this question as off-topic because it is not a question about bioinformatics.
Alex Reynolds
CC BY-SA 3.0
2018-01-09T09:13:22.980Z
@AlexReynolds, I attached a link and you will see that is about bioinformatics.
Mihai Alexandru-Ionut
CC BY-SA 3.0
2018-01-09T09:14:42.417Z
In the document there are also algorithms for finding genes tree.
Mihai Alexandru-Ionut
CC BY-SA 3.0
2018-01-09T11:13:17.380Z
That the topic it can be applied is in bioinformatics doesn't make your *question* about bioinformatics. You can edit explaining what is 1 and 0 and which is your bioinformatic question. But it seems a nice problem
llrs
<gene><genome><homework>
Find number of possibilities
# Find number of possibilities

(Asked by: username_0 on 2018-01-09)

We have a column which has following format : (1, 1, 1, 0, 1).

Here is the definition of what means two columns are **compatible**.

> Using the notation Oi to denote the collection of rows possessing a 1
> in their i-th element, we conclude that one of three possibilities
> must be true: Oi ⊆ Oj , Oj ⊆ Oi , or Oi and Oj are disjoint (the first
> two cases include the possibility that Oi = Oj). If columns i and j
> satisfy this condition, then we call them compatible

The question is : **How many possible columns of length 5 are compatible with the column (1, 1, 1, 0, 1)?**

You can read more [here](http://bioinformaticsalgorithms.com/excerpt/How%20Have%20Humans%20Populated%20the%20Earth.pdf) where problem is described in page 14-16.

Thanks in advance !

**Tags:** gene, genome, homework
> **Comments:**
> **username_1**: I'm voting to close this question as off-topic because it is not a question about bioinformatics.  
> **username_0**: @AlexReynolds, I attached a link and you will see that is about bioinformatics.  
> **username_0**: In the document there are also algorithms for finding genes tree.  
> **username_2**: That the topic it can be applied is in bioinformatics doesn't make your *question* about bioinformatics. You can edit explaining what is 1 and 0 and which is your bioinformatic question. But it seems a nice problem  

---

## 1 answers

### Answer by username_3 on 2018-01-09. Score: 2 | Accepted answer

Let $n$ be the number of rows (in your case $n=5$) and $|O\_j|$ the [cardinality](https://en.wikipedia.org/wiki/Cardinality) of $O\_i$.

We can calculate the number of compatible columns as sum of the number of $O\_i \subseteq O\_j$, $O\_j \subseteq O\_i$ and $O\_i, O\_j$ disjoint.

number of $O\_i \subseteq O\_j$:
Here we need to find the number of supersets of our $O\_i$. That means we need to find the number of sets which contain the indices in $O\_i$ and for each index not in $O\_i$, we have two choices: It is contained, or it is not contained in $O\_j$. Therefore the number of supersets is $2^{n-|O\_i|}$, which is 2 to the power of elements not in our set.

number of $O\_i, O\_j$ disjoint:
Here all elements of $O\_i$ are fixed not to be in $O\_j$ and for each index not in $O\_i$, it can again be in $O\_j$ or not. That means that the number of possible sets is again $2^{n-|O\_i|}$.

number of $O\_j \subseteq O\_i$:
Here we need to find the number of subsets of $O\_i$ and this is the number of elements in its power set, which is $2^{|O\_i|}$.

So finally, this means that the number of compatible columns can be calculated as: $2^{n-|O\_i|} + 2^{n-|O\_i|} + 2^{|O\_i|} - 2$.

Why -2? We have counted 2 sets twice:

* The empty set, which is a subset of $O\_i$ and also counted in the number of disjoint sets
* and $O\_i$, which we counted in $O\_i \subseteq O\_j$ and in $O\_j \subseteq O\_i$

This means for your examle, we have $16 + 2 + 2 - 2 = 18$ compatible sets.

**Note:** The all zero vector (which corresponds to $O\_i=\{\}$) is a special case for which the formula above does not work, as all disjunct sets and all supersets are counted twice. For this special case, the number of compatible columns is simply $2^n$.

> **Comments:**
> **username_0**: Thanks for your answer. How do you calculate `|Oi|` ?  
> **username_3**: $|O_i|$ is the number of elements in $O_i$, so for your column $|O_i|$ is 4 because $O_i = \{1,2,3,5\}$  
> **username_0**: In my example why is not 5 ? Cardinal({1,1,1,0,1})=5  
> **username_3**: The cardinality of your column is 5. But in your definition: "Using the notation Oi to denote the collection of rows possessing a 1 in their i-th element,", $O_i$ is the set of rows with a 1. In your column there are 4 rows with a one, so the cardinality of $O_i$ = 4  
> **username_0**: Thanks a lot for your explanation.Now I understand. It means that for (0,0,0,0,0) the answer is `2^5+2^5+2^0-2 =63` ?  
> **username_3**: The number of compatible columns can not be larger than the total number of sets with 5 elements ($2^5$) :). (0,0,0,0,0) Is indeed a special case for which my rule above breaks, as all disjoint sets and all supersets are counted twice. So for This special case you have to hard code the result to $2^n$. For all other cases, the formula should work.  

---

