Find the number of possibilities

Question

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: $O_i ⊆ O_j$ , $O_j ⊆ O_i$ , or $O_i$ and $O_j$ 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 !

Answer 1

Assume that a column contains $n$ elements. If all are zero, then the column is compatible with any other column of $n$ elements, of which there are $2^n$.

Suppose instead that a column contains $x$ ones, where $x>0$. We will now construct a compatible column next to it. There are three ways to do so:

• Write $0$ next to every one. There are $n-x$ spaces remaining, and $2^{n-x}$ ways to fill them. This is the disjoint option.
• Write $1$ next to every one. There are $n-x$ spaces remaining, and $2^{n-x}$ ways to fill them. This is the is-contained option.
• Write a mixture of $0$s and $1$s next to the ones. There are $2^x-2$ ways to do so. All remaining spaces must contain $0$. This is the contains-but-is-not-equal option.

Thus, summing, the answer is $2\cdot 2^{n-x}+2^x-2$.

In your specific case, $n=5$ and $x=4$, so the answer is $18$.