text: user2088: 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 where problem is described in page 14-16.
  Thanks in advance !
  
  user2047: Let $n$ be the number of rows (in your case $n=5$) and $|O_j|$ the 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$.
  
original_text: 2088: <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>
   2047: <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>
  