A set of positive integers is double-free if, for any integer 
, the set 
(or equivalently, 
implies 
). For example, of the subsets of 
, the sets 
, 
, 
, 
, 
, and 
are double-free, while 
and 
are not.
The number 
of double-free subsets of 
can be computed using 
and the recurrence
relation
 |
(1)
|
where 
is a Fibonacci number, 1, 1, 2, 3, 5, 8, ...
(OEIS A000045), and 
is the binary carry
sequence giving the number of trailing 0s in the binary
representation of 
.
For 
,
2, ..., 
is given by 0, 1, 0, 2, 0, 1, 3, 0, 1, ... (OEIS A007814),
while the corresponding 
are 2, 3, 6, 10, 20, 30, 60, 96, 192, ... (OEIS A050291).
Define
 |
(2)
|
where 
is the cardinal number of (number of members in)
. Then for 
, 2, ..., 
is given by 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10,
... (OEIS A050292). An explicit formula for
is given by
 |
(3)
|
where
 |
(4)
|
if the characteristic function of 
(defined above), and the first few
values of 
are 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, ... (OEIS A035263).
A simple recurrence relation for 
is given by
![f(n)=[1/2n]+f(|_1/4n_|)](/images/equations/Double-FreeSet/NumberedEquation5.svg) |
(5)
|
with 
(Wang 1989), where 
is the floor function and ![[x]](/images/equations/Double-FreeSet/Inline33.svg)
is the ceiling function.
An asymptotic formula for 
is given by
 |
(6)
|
(Wang 1989).
