login
Number of minimal subsets of {2..n} such that it is not possible to choose a different binary index of each element.
6

%I #6 Mar 11 2024 18:06:04

%S 0,0,0,0,0,1,4,13,13,26,56,126,243,471,812,1438

%N Number of minimal subsets of {2..n} such that it is not possible to choose a different binary index of each element.

%C A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

%e The a(0) = 0 through a(7) = 13 subsets:

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

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

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

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

%e {2,3,5,7}

%e {2,3,6,7}

%e {2,4,5,7}

%e {2,5,6,7}

%e {3,4,5,6}

%e {3,4,5,7}

%e {3,4,6,7}

%e {3,5,6,7}

%e {4,5,6,7}

%e The a(0) = 0 through a(7) = 13 set-systems:

%e . . . . . {2}{12}{3}{13} {2}{3}{23} {2}{3}{23}

%e {2}{12}{3}{13} {2}{12}{3}{13}

%e {12}{3}{13}{23} {12}{3}{13}{23}

%e {2}{12}{13}{23} {2}{12}{13}{23}

%e {2}{12}{3}{123}

%e {2}{3}{13}{123}

%e {12}{3}{13}{123}

%e {12}{3}{23}{123}

%e {2}{12}{13}{123}

%e {2}{12}{23}{123}

%e {2}{13}{23}{123}

%e {3}{13}{23}{123}

%e {12}{13}{23}{123}

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

%t fasmin[y_]:=Complement[y,Union@@Table[Union[s,#]& /@ Rest[Subsets[Complement[Union@@y,s]]],{s,y}]];

%t Table[Length[fasmin[Select[Subsets[Range[2,n]], Select[Tuples[bpe/@#],UnsameQ@@#&]=={}&]]],{n,0,10}]

%Y The version with ones allowed is A370642, minimal case of A370637.

%Y This is the minimal case of A370643.

%Y A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.

%Y A070939 gives length of binary expansion.

%Y A096111 gives product of binary indices.

%Y A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.

%Y A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.

%Y A370585 counts maximal choosable sets.

%Y Cf. A072639, A140637, A326031, A355529, A367905, A368109, A370589, A370591, A370636, A370639, A370640.

%K nonn,more

%O 0,7

%A _Gus Wiseman_, Mar 11 2024