A088808 Number of subsets of {1, ..., n} that are not double-free.

0, 0, 1, 2, 6, 12, 34, 68, 160, 320, 736, 1472, 3136, 6272, 13504, 27008, 56176, 112352, 234064, 468128, 954976, 1909952, 3913504, 7827008, 15878656, 31757312, 64413184, 128826368, 259449856, 518899712, 1046785024, 2093570048, 4207876096, 8415752192

Offset: 0

Author

Reinhard Zumkeller, Oct 19 2003

Keywords

• nonn

Comments

a(n) = 2^n - A050291(n); a(2*k+1) = a(2*k)*2;

a non-double-free subset contains at least one subset {x,y} with y=2*x.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3321 (first 401 terms from T. D. Noe)
• Steven R. Finch, Triple-Free Sets of Integers [From Steven Finch, Apr 20 2019]
• Eric Weisstein's World of Mathematics, Double-Free Set
• Reinhard Zumkeller, Illustration of initial terms

Crossrefs

Cf. A000079, A050291.

Programs

Mathematica

A050291[n_] := A050291[n] = If[n == 1, 2, With[{b = IntegerExponent[2n, 2]}, A050291[n - 1] Fibonacci[b + 2]/Fibonacci[b + 1]]];
a[n_] := If[n == 0, 0, 2^n - A050291[n]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Nov 10 2021 *)