cp's OEIS Frontend

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

%I A050291 #41 Feb 16 2025 08:32:40
%S A050291 1,2,3,6,10,20,30,60,96,192,288,576,960,1920,2880,5760,9360,18720,
%T A050291 28080,56160,93600,187200,280800,561600,898560,1797120,2695680,
%U A050291 5391360,8985600,17971200,26956800,53913600,87091200,174182400,261273600,522547200,870912000
%N A050291 Number of double-free subsets of {1, 2, ..., n}.
%C A050291 A set is double-free if it does not contain both x and 2x.
%C A050291 So these are equally "half-free" subsets. - _Gus Wiseman_, Jul 08 2019
%D A050291 Wang, E. T. H. ``On Double-Free Sets of Integers.'' Ars Combin. 28, 97-100, 1989.
%H A050291 Alois P. Heinz, <a href="/A050291/b050291.txt">Table of n, a(n) for n = 0..4030</a> (terms n = 1..400 from T. D. Noe)
%H A050291 Steven R. Finch, <a href="/FinchTriple.html">Triple-Free Sets of Integers</a> [From Steven Finch, Apr 20 2019]
%H A050291 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Double-FreeSet.html">Double-Free Set.</a>
%F A050291 a(n) = a(n-1)*Fibonacci(b(2n)+2)/Fibonacci(b(2n)+1), Fibonacci = A000045, b = A007814.
%F A050291 a(n) = 2^n - A088808(n). - _Reinhard Zumkeller_, Oct 19 2003
%e A050291 From _Gus Wiseman_, Jul 08 2019: (Start)
%e A050291 The a(0) = 1 through a(5) = 20 double-free subsets:
%e A050291   {}  {}   {}   {}     {}       {}
%e A050291       {1}  {1}  {1}    {1}      {1}
%e A050291            {2}  {2}    {2}      {2}
%e A050291                 {3}    {3}      {3}
%e A050291                 {1,3}  {4}      {4}
%e A050291                 {2,3}  {1,3}    {5}
%e A050291                        {1,4}    {1,3}
%e A050291                        {2,3}    {1,4}
%e A050291                        {3,4}    {1,5}
%e A050291                        {1,3,4}  {2,3}
%e A050291                                 {2,5}
%e A050291                                 {3,4}
%e A050291                                 {3,5}
%e A050291                                 {4,5}
%e A050291                                 {1,3,4}
%e A050291                                 {1,3,5}
%e A050291                                 {1,4,5}
%e A050291                                 {2,3,5}
%e A050291                                 {3,4,5}
%e A050291                                 {1,3,4,5}
%e A050291 (End)
%p A050291 a:= proc(n) option remember; `if`(n=0, 1, (F-> (p-> a(n-1)*F(p+3)
%p A050291       /F(p+2))(padic[ordp](n, 2)))(j-> (<<0|1>, <1|1>>^j)[1, 2]))
%p A050291     end:
%p A050291 seq(a(n), n=0..50);  # _Alois P. Heinz_, Jan 16 2019
%t A050291 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 *)
%t A050291 Table[Length[Select[Subsets[Range[n]],Intersection[#,#/2]=={}&]],{n,0,10}] (* _Gus Wiseman_, Jul 08 2019 *)
%o A050291 (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
%Y A050291 Cf. A000045, A007814, A050292-A050296.
%Y A050291 Cf. A007865, A103580, A120641, A308546, A320340, A323092, A326083, A326115.
%K A050291 nonn,easy,nice
%O A050291 0,2
%A A050291 _Eric W. Weisstein_
%E A050291 Extended with formula by _Christian G. Bower_, Sep 15 1999
%E A050291 a(0)=1 prepended by _Alois P. Heinz_, Jan 16 2019