This is a problem that appeared in Algorithmic engagements 2007 and discussed by Kubica and Radoszewski 

The problem statement: 

An anti-binary set is a set of integers that does not contain two numbers of the form m and 2m. For example, the set: 

A = {2, 3, 5, 8, 11, 13} 

is anti-binary whereas the set: 

B = {2, 3, 5, 6, 8, 11, 13} 

is not, since both 3 and 6 are its elements. 

What is the largest size of an anti-binary set that is a subset of 

1. {1, … , 11} 

2. {1, … , 12} 

3. {1, … , 13} 

4. {1, … , 14} 

5. {1, … , 15} 

How many different anti-binary subsets of the same size exist? 

The Solution: 

In this case a graph like this helps: 

1 --> 2 -->4-->8 

               3-->6-->12 

                5-->10 

              7 9 11 13 

Where --> denotes an edge when elements are connected by the relation m-->2m 

The elements that don’t connect are mentioned last. 

We can select all of the elements in the last row, one element from the second last row, the first and the last element from the second row and alternate elements from the first row giving us the cardinality of 9. 

More generally, let us say that for a path of size n, the number of anti-binary subsets is An. Then the number of all anti-binary subsets of the given sequence is A1 power 4 times A2 power 1 times A3 power 1 and A4 power 1 by permutations. A1 = 2 and A2  = 3 because we say whether those anti-binary element or its combination is included or not. 

Since the pattern of picking the anti-binary set is that of picking alternate elements in the series m[Symbol]2m, we say that if an anti binary set contains the last element, it does not contain its predecessor.  Hence the number of such sets equals An-2. Given that the last element can be included or not, we establish an optimal substructure as An = An-1 + An-2 

And hence a recursive relation where A1 = 2 and A2 = 3. 

This therefore is the Fibonacci series where An = Fibonacci(n-2) 

int Fibonacci(int n)  {  

if (n <= 0 ) return 0; 

 int value = Fibonacci(n-1) + Fibonacci(n-2);  

return value;  

} 

And we can count all the subsets as follows: 

AllAntiBinarySets(A, n)  

If n == 0   Return 0  

q = 1  

int r = n %2 == 0 ? n: n+1 

For k = I to log(r) 

     If (graph-exists(A,k)) 

            q *=  Fibonacci(k)*numberofGraphs; 

  return q