Double-Free Set

A double-free set is a set of positive integers such that, 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, for , 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, 0, 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 is the characteristic function defined by

(4)

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

(5)

with (Wang 1989), where is the floor function and is the ceiling function. An asymptotic formula for is given by

(6)

(Wang 1989).