A050291 Number of double-free subsets of {1, 2, ..., n}.

1, 2, 3, 6, 10, 20, 30, 60, 96, 192, 288, 576, 960, 1920, 2880, 5760, 9360, 18720, 28080, 56160, 93600, 187200, 280800, 561600, 898560, 1797120, 2695680, 5391360, 8985600, 17971200, 26956800, 53913600, 87091200, 174182400, 261273600, 522547200, 870912000

Offset

0,2

Comments

A set is double-free if it does not contain both x and 2x.

So these are equally "half-free" subsets. - Gus Wiseman, Jul 08 2019

References

Wang, E. T. H. ``On Double-Free Sets of Integers.'' Ars Combin. 28, 97-100, 1989.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..4030 (terms n = 1..400 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.

Formula

a(n) = a(n-1)*Fibonacci(b(2n)+2)/Fibonacci(b(2n)+1), Fibonacci = A000045, b = A007814.

a(n) = 2^n - A088808(n). - Reinhard Zumkeller, Oct 19 2003

Example

From Gus Wiseman, Jul 08 2019: (Start)
The a(0) = 1 through a(5) = 20 double-free subsets:
  {}  {}   {}   {}     {}       {}
      {1}  {1}  {1}    {1}      {1}
           {2}  {2}    {2}      {2}
                {3}    {3}      {3}
                {1,3}  {4}      {4}
                {2,3}  {1,3}    {5}
                       {1,4}    {1,3}
                       {2,3}    {1,4}
                       {3,4}    {1,5}
                       {1,3,4}  {2,3}
                                {2,5}
                                {3,4}
                                {3,5}
                                {4,5}
                                {1,3,4}
                                {1,3,5}
                                {1,4,5}
                                {2,3,5}
                                {3,4,5}
                                {1,3,4,5}
(End)

Maple

a:= proc(n) option remember; `if`(n=0, 1, (F-> (p-> a(n-1)*F(p+3)
      /F(p+2))(padic[ordp](n, 2)))(j-> (<<0|1>, <1|1>>^j)[1, 2]))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jan 16 2019

Mathematica

a[n_] := a[n] = (b = IntegerExponent[2n, 2]; a[n-1]*Fibonacci[b+2]/Fibonacci[b+1]); a[1]=2; Table[a[n], {n, 1, 34}] (* Jean-François Alcover, Oct 10 2012, from first formula *)
Table[Length[Select[Subsets[Range[n]], Intersection[#, #/2]=={}&]], {n, 0, 10}] (* Gus Wiseman, Jul 08 2019 *)

Prog

(PARI) first(n)=my(v=vector(n)); v[1]=2; for(k=2, n, v[k]=v[k-1]*fibonacci(valuation(k, 2)+3)/fibonacci(valuation(k, 2)+2)); v \\ Charles R Greathouse IV, Feb 07 2017

Crossrefs

Cf. A000045, A007814, A050292-A050296.

Cf. A007865, A103580, A120641, A308546, A320340, A323092, A326083, A326115.

Sequence in context: A346787 A113292 A342012 * A324739 A214002 A305889

Adjacent sequences: A050288 A050289 A050290 * A050292 A050293 A050294

Keyword

nonn,easy,nice

Author

Eric W. Weisstein

Extensions

Extended with formula by Christian G. Bower, Sep 15 1999

a(0)=1 prepended by Alois P. Heinz, Jan 16 2019

Status

approved