login
Number of maximal subsets of {1...n} with no binary containments.
9

%I #8 Jul 27 2019 14:57:51

%S 1,1,1,2,2,4,5,6,6,11,13,16,17,22,27,28

%N Number of maximal subsets of {1...n} with no binary containments.

%C 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.

%e The a(0) = 1 through a(7) = 6 maximal subsets:

%e {} {1} {1,2} {3} {3,4} {2,5} {1,6} {7}

%e {1,2} {1,2,4} {3,4} {2,5} {1,6}

%e {3,5} {3,4} {2,5}

%e {1,2,4} {1,2,4} {3,4}

%e {3,5,6} {1,2,4}

%e {3,5,6}

%t binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];

%t stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];

%t maxim[s_]:=Complement[s,Last/@Select[Tuples[s,2],UnsameQ@@#&&SubsetQ@@#&]];

%t Table[Length[maxim[Select[Subsets[Range[n]],stableQ[#,SubsetQ[binpos[#1],binpos[#2]]&]&]]],{n,0,10}]

%Y Cf. A006126, A014466, A019565, A267610.

%Y Cf. A325095, A325096, A325101, A325106, A325107, A325109, A325110.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Mar 28 2019