Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:24:03.823Z
Answers.Text: Thanks for your answer. How do you calculate `|Oi|` ?
Answers.UserDisplayName: Mihai Alexandru-Ionut
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:26:13.760Z
Answers.Text: $|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\}$
Answers.UserDisplayName: Bluescreen
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:30:11.577Z
Answers.Text: In my example why is not 5 ? Cardinal({1,1,1,0,1})=5
Answers.UserDisplayName: Mihai Alexandru-Ionut
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:32:18.280Z
Answers.Text: 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
Answers.UserDisplayName: Bluescreen
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:33:59.593Z
Answers.Text: 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` ?
Answers.UserDisplayName: Mihai Alexandru-Ionut
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:43:08.353Z
Answers.Text: 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.
Answers.UserDisplayName: Bluescreen
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-09T10:17:12.033Z
Answers.LastActivityDate: 2018-01-09T10:50:38.860Z
Answers.LastEditDate: 2018-01-09T10:50:38.860Z
Answers.UserDisplayName: Bluescreen
Body: <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>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-09T09:11:36.610Z
Comments.Text: I'm voting to close this question as off-topic because it is not a question about bioinformatics.
Comments.UserDisplayName: Alex Reynolds
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-09T09:13:22.980Z
Comments.Text: @AlexReynolds, I attached a link and you will see that is about bioinformatics.
Comments.UserDisplayName: Mihai Alexandru-Ionut
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-09T09:14:42.417Z
Comments.Text: In the document there are also algorithms for finding genes tree.
Comments.UserDisplayName: Mihai Alexandru-Ionut
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2018-01-09T11:13:17.380Z
Comments.Text: 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
Comments.UserDisplayName: llrs
Tags: <gene><genome><homework>
Title: Find number of possibilities
ThreadText: # 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**: @username_1, 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.  
  
  ---
  
  