cp's OEIS Frontend

A325107 Number of subsets of {1...n} with no binary containments.

%I A325107 #28 Dec 12 2020 04:30:36
%S A325107 1,2,4,5,10,13,18,19,38,52,77,83,133,147,166,167,334,482,764,848,1465,
%T A325107 1680,1987,2007,3699,4413,5488,5572,7264,7412,7579,7580,15160,22573,
%U A325107 37251,42824,77387,92863,116453,118461,227502,286775,382573,392246,555661,574113
%N A325107 Number of subsets of {1...n} with no binary containments.
%C A325107 A pair of positive integers is a binary containment if the positions of 1's in the reversed binary expansion of the first are a subset of the positions of 1's in the reversed binary expansion of the second.
%H A325107 Fausto A. C. Cariboni, <a href="/A325107/b325107.txt">Table of n, a(n) for n = 0..129</a>, (terms up to a(71) from Alois P. Heinz)
%F A325107 a(2^n - 1) = A014466(n).
%e A325107 The a(0) = 1 through a(6) = 18 subsets:
%e A325107   {}  {}   {}     {}     {}       {}       {}
%e A325107       {1}  {1}    {1}    {1}      {1}      {1}
%e A325107            {2}    {2}    {2}      {2}      {2}
%e A325107            {1,2}  {3}    {3}      {3}      {3}
%e A325107                   {1,2}  {4}      {4}      {4}
%e A325107                          {1,2}    {5}      {5}
%e A325107                          {1,4}    {1,2}    {6}
%e A325107                          {2,4}    {1,4}    {1,2}
%e A325107                          {3,4}    {2,4}    {1,4}
%e A325107                          {1,2,4}  {2,5}    {1,6}
%e A325107                                   {3,4}    {2,4}
%e A325107                                   {3,5}    {2,5}
%e A325107                                   {1,2,4}  {3,4}
%e A325107                                            {3,5}
%e A325107                                            {3,6}
%e A325107                                            {5,6}
%e A325107                                            {1,2,4}
%e A325107                                            {3,5,6}
%p A325107 c:= proc() option remember; local i, x, y;
%p A325107       x, y:= map(n-> Bits[Split](n), [args])[];
%p A325107       for i to nops(x) do
%p A325107         if x[i]=1 and y[i]=0 then return false fi
%p A325107       od; true
%p A325107     end:
%p A325107 b:= proc(n, s) option remember; `if`(n=0, 1, b(n-1, s)+
%p A325107      `if`(ormap(i-> c(n, i), s), 0, b(n-1, s union {n})))
%p A325107     end:
%p A325107 a:= n-> b(n, {}):
%p A325107 seq(a(n), n=0..34);  # _Alois P. Heinz_, Mar 28 2019
%t A325107 binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A325107 stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
%t A325107 Table[Length[Select[Subsets[Range[n]],stableQ[#,SubsetQ[binpos[#1],binpos[#2]]&]&]],{n,0,13}]
%Y A325107 Cf. A006126, A014466, A019565, A267610.
%Y A325107 Cf. A325095, A325096, A325101, A325105, A325106, A325108, A325109, A325110.
%K A325107 nonn
%O A325107 0,2
%A A325107 _Gus Wiseman_, Mar 28 2019
%E A325107 a(16)-a(45) from _Alois P. Heinz_, Mar 28 2019